Java容器分析--Map

    作者：Flyingis

标准的Java类库中包含了几种类型的Map，它们都拥有同样的基本接口Map，但是行为特性各不相同，主要表现在效率、键值对的保存、元素呈现次序、对象的保存周期和判定键是否等价的策略等方面。<!----><o:p></o:p>

1.Map的功能方法<o:p></o:p>

Map(interface): 维护label和value的关联性，使得可以通过label查找value。<o:p></o:p>

HashMap: Map基于散列表的实现，取代了Hashtable。插入和查询label/value的开销是固定的，并且可以通过构造器设置容量和负载因子，以调整容器的性能。<o:p></o:p>

LinkedHashMap: 在HashMap的基础上做了一些改进，在迭代遍历它时，取得label/value的顺序是其插入的次序，或者是最近最少使用(LRU)的次序，速度上比HashMap要慢一点，但在迭代访问时速度会更快，主要原因是它使用了链表维护内部次序。<o:p></o:p>

TreeMap: 查看label或label/value时，元素会被排序，其次序由Comparable或Comparator决定，因此查询所得到的结果是经过排序的。另外，它是唯一带有subMap()方法的Map具体类，即返回一个子树。它也是SortedMap接口的唯一实现，subMap()方法也是从该接口继承的。<o:p></o:p>

WeakHashMap: Weak Key映射，允许释放映射所指向的对象。当映射之外没有引用指向某个label时，此label可以被垃圾收集器回收。<o:p></o:p>

IdentityHashMap: 使用==代替equals()对label进行比较的散列映射。<o:p></o:p>

2.hashCode()<o:p></o:p>

         当使用标准库中的类Integer作为HashMap的label时，程序能够正常运行，但是使用自己创建的类作为HashMap的label时，通常犯一个错误。<o:p></o:p>

         在HashMap中通过label查找value时，实际上是计算label对象地址的散列码来确定value的。一般情况下，我们是使用基类Object的方法hashCode()来生成散列码，它默认是使用对象的地址来计算的，因此由第一个对象new Apple(5)和第二个对象new Apple(5)生成的散列码是不同的，不能完成正确的查找。通常，我们可以编写自己的hashCode()方法来覆盖基类的原始方法，但与此同时，我们必须同时实现equals()方法来判断当前的label是否与表中存在的label相同。正确的equals()方法满足五个条件：<o:p></o:p>

(1)     自反性。对于任意的x，x.equals(x)一定返回true。<o:p></o:p>

(2)     对称性。对于任意的x和y，如果y.equals(x)返回true，则x.equals(y)也返回true。<o:p></o:p>

(3)     传递性。对于任意的x、y、z，如果有x.equals(y)返回true，y.equals(z)返回true，则x.equals(z)一定返回true。<o:p></o:p>

(4)     一致性。对于任意的x和y，如果对象中用于等价比较的信息没有改变，那么无论调用x.equals(y)多少次，返回的结果应该保持一致，要么一直是true，要么一直是false。<o:p></o:p>

(5)     对任何不是null的x，x.equals(null)一定返回false。<o:p></o:p>

equals()比较的是对象的地址，如果要使用自己的类作为HashMap的label，必须同时重载hashCode()和equals()方法。<o:p></o:p>

使用散列的目的：想要使用一个对象来查找另一个对象。使用TreeSet或TreeMap也能实现此目的。另外，还可以自己实现一个Map，此时，必须提供Map.entrySet()方法来生成Map.Entry对象的Set。<o:p></o:p>

使用散列的价值：速度，散列使得查询可以快速进行。散列将label保存载数组中方便快速查询，因为存储一组元素最快的数据结构是数组，用它来表示label的信息(后面有信息的描述)，而不是label本身。通过label对象计算得到一个数字，作为数组的下标，这个数字就是散列码(即前面所述的信息)。该散列码具体是通过定义在基类Object中，可能由程序员自定义的类覆盖的hashCode()方法，即散列函数生成。为了解决数组容量带来的限制，可以使不同的label生成相同的下标，保存在一个链表list中，每一个链表就是数组的一个元素。查询label时就可以通过对list中的信息进行查找，当散列函数比较好，数组的每个位置中的list长度较短，则可以快速查找到数组元素list中的某个位置，提高了整体速度。<o:p></o:p>

散列表中的slot通常称为bucket，为了使散列分步均匀，bucket的值一般取质数。但事实证明，质数实际上并不是散列bucket的理想容量，近来Java散列实现都使用2的幂，具体如何验证以后再续。<o:p></o:p>

3.HashMap的性能因子<o:p></o:p>

容量(capacity): 散列表中bucket的数量。<o:p></o:p>

初始化容量(initial capacity): 创建散列表时bucket的数量。可以在构造方法中指定HashMap和HashSet的初始化容量。<o:p></o:p>

尺寸(size): 散列表中记录的数量。(数组的元素个数，非list中元素总和)<o:p></o:p>

负载因子(load factor): 尺寸/容量。负载因子为0，表示空的散列表，0.5表示半满的散列表。轻负载的散列表具有冲突少，适宜插入与查询的特点，但是使用迭代器遍历会比较慢。较高的负载会减少所需空间大小。当负载达到指定值时，容器会自动成倍地增加容量，并将原有的对象重新分配，存入新的bucket中，这个过程称为“重散列”。<o:p></o:p>

4.重写hashCode()的关键<o:p></o:p>

(1)     对同一个对象调用hashCode()都应该生成同样的值。<o:p></o:p>

(2)     hashCode()方法不要依赖于对象中易变的数据，当数据发生变化时，hashCode()就会生成一个不同的散列码，即产生了一个不同的label。<o:p></o:p>

(3)     hashCode()不应依赖于具有唯一性的对象信息，例如对象地址。<o:p></o:p>

(4)     散列码应该更关心速度，而不是唯一性，因为散列码不必是唯一的。<o:p></o:p>

(5)     好的hashCode()应该产生分步均匀的散列码。在Effective Java(Addison-Wesley 2001)中，Joshua Bloch给hashCode()给出了设计指导，可以参考。<o:p></o:p>

编写正确高效的hashCode()和equals()可以参考Apache的Jakarta Commons项目中的工具。

其它相关内容：
Java容器分析--数组
Java容器分析--List和Set