数据结构（一）： 键值对 Map

Map基本介绍

Map 也称为：映射表／关联数组，基本思想就是键值对的关联，可以用键来查找值。

Java标准的类库包含了Map的几种基本的实现，包括：HashMap，TreeMap，LinkedHashMap，WeakHashMap，ConcurrentHashMap，IdentityHashmap。它们都有同样的基本接口Map，但是在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定“键”等价的策略等方面。

Map最大的作用就是能够将对象映射到其他对象，基本的用法在这里就不做过多的说明了。需要说明的是，Map与数组和其他的Collection一样，可以很容易扩展到多维，我们只需要将其value值设置为Map（这些Map的value可以是其他容器，甚至是其他Map）。因此我们可以很容易的将容器组合起来，从而快速地生成强大的数据结构。

性能

性能是Map的一个重要指标，当在get()方法使用线性搜索的时候，执行速度会相当的慢。Map不同的实现方式，其性能表现也是不相同的。

其中HashMap能够提高搜索的执行速度，因为HashMap使用了特殊的值，称做散列码，来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值，它通过将该对象的某些信息进行转换而生成的。hashCode()是根类Object中的方法，因此所有的Java对象都能产生散列码，HashMap就是使用对象的hashCode（）进行快速查询的，此方法能够显著提高性能。

不同Map实现的对比

下面是基本的Map实现，如果没有其他的限制，应该默认使用HashMap，因为它对速度进行了优化。其他的强调了其他方面的特性，所有都不如HashMap快。

• HashMap ：Map基于散列表的实现，插入和查询的开销是固定的。可以通过构造函数设置容量和内容的类型，以提高性能。
• LinkedHashMap：类似于HashMap，但是迭代遍历的时候，取得的“键值对”的顺序是其插入的次序，或者是最近最少使用(LRU)的次序，只比HashMap慢一点。而在迭代访问时反而更快，因为它使用链表维护内部次序。
• TreeMap：基于红黑树实现的。查看“键”或“键值对”时，它们会被排序。TreeMap的特点在于，所得到的结果是经过排序的。TreeMap是唯一带有subMap()方法的Map，它可以返回一个子树。
• WeakHashMap：弱键映射，允许释放映射所指向的对象。这是为了解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾回收器回收。
• ConcurrentHashMap： 一种线程安全的Map，它不涉及同步加锁，
• IdentityHashMap：使用==代替equal()对“键”进行比较的散列映射。转为解决特殊问题而设计的。