Java程序设计-快速掌握HashMap类

java.util.Hash Map＜K，V＞类是Map接口最常用的实现类。Hash Map底层采用哈希表来存储数据，要求键不能重复，如果发生重复，新值将替换掉该键的旧值。Hash Map类底层实现决定了它在查找、删除、修改等方面的效率都非常高。

1.Hash Map集合的元素Entry＜K，V＞对象

以JDK 1.7为例，我们分析java.util.Hash Map＜K，V＞类中的内部静态类Entry＜K，V＞，该类实现了Map.Entry＜K，V＞接口的所有抽象方法。相关源代码如图9-7所示。

图9-7　Hash Map＜K，V＞类的内部静态类Entry＜K，V＞部分代码

Hash Map集合中存储的元素是Entry＜K，V＞对象，每一个Entry＜K，V＞对象存储有4个成员变量，分别为：

（1）final K key：键对象，final修饰的变量。

（2）V value：值对象。

（3）Entry＜K，V＞next：Entry＜K，V＞对象的引用，指向下一个Entry＜K，V＞对象元素。

（4）int hash：键对象key经过计算得到的hash值。

可见，每一个Entry＜K，V＞对象除了存储键key和值value的映射关系外，还保存了键key的hash值，以及指向下一个Entry＜K，V＞对象的next引用。

2.Entry＜K，V＞对象成员变量hash的计算

Entry＜K，V＞对象中计算成员变量hash值的源代码如图9-8所示。

图9-8　hash方法源代码

hash方法计算Object k的hash值时，对k.hashCode（）方法得到的值进行了多次处理，其目的是使不同k的hash值分布更均匀，减少碰撞概率。

3.Hash Map集合的数据结构

Hash Map实际上是一个“链表散列”的数据结构，即数组和链表的结合体，这样的结构结合了链表在增删方面的高效和数组在寻址上的优势。

查看Hash Map类的源代码，Hash Map类中定义了一个数组，如图9-9所示。

图9-9　Hash Map类的table成员变量

新建一个Hash Map集合时，就会初始化一个给定容量大小、存储Entry＜K，V＞对象引用的table数组。这个table数组中的每个元素的值初始均为null，当向该集合中存储元素时，table数组中的对应位置的元素就会保存Entry＜K，V＞对象的引用。而Entry＜K，V＞对象的数据结构都有一个next引用变量，它指向下一个Entry＜K，V＞对象。因此，我们可以得出Hash Map集合的数据结构如图9-10所示。

图9-10　Hash Map集合的数据结构

实际上，Hash Map集合的数据结构中，table数组的每一项值要么为null，要么指向一个Entry＜K，V＞对象，形成单向链表。Hash Map的这种数据结构可以大大提高查询效率。简单地说，查找一个集合元素，首先根据元素特征定位到数组的下标索引，然后在该位置的单向链表中依次查找即可，这大大缩小了查找范围。

具体地说，根据Entry＜K，V＞对象的键key的hash值定位到对应的数组下标索引位置，后续只需查找数组下标索引所在链表的元素，这大大缩小了查询范围。

put方法是在Hash Map集合中设置键和值的映射关系，如果Hash Map集合中存在一个该键的映射关系（即Entry＜K，V＞对象），则旧值被新值替换，如果没有，则新增该映射关系（即Entry＜K，V＞对象）。注意，Hash Map的key，value可以取null。

4.向Hash Map集合存储数据

在了解了Hash Map的基本结构后，需要深入学习如何向Hash Map集合中存储Entry＜K，V＞对象，这就是Hash Map方法public V put（K key，V value）方法。以JDK 1.7为例，put方法源代码如图9-11所示。

图9-11　put方法源代码

（1）程序第471行调用hash（key）方法（参看图9-8源代码）得到键key对应的hash值。

（2）程序第472行调用index For（hash，table.length）方法，得到hash值对应table数组的位置i（即数组table的下标索引i）。index For方法源代码如图9-12所示。

图9-12　indexFor方法源代码

index For方法是hash值h跟table数组长度length做位运算，返回［0，length-1］区间的一个值i，正好对应table的下标索引范围。

早期的index For方法采用的是hash值对数组长度取模运算（即h%length），这样一来，元素的分布相对来说是比较均匀的。由于模运算的效率较低，现在采用hash值同“数组的长度-1”做一次“与”运算（&）即可。为了达到和取模运算一样的分散效果，前提是数组的长度length必须为2的整数次幂。举例来说，数组长度length取2的4次方，即为16，则length-1即为15，换算成二进制即为1111，将h也换算成二进制，那么h&（length-1）计算的结果就等于换算成二进制形式后的h的低4位（其余高位和0相与结果都为0），共有16种可能取值，分布在［0，length-1］区间，和取模运算效果一致。但是，如果length值不是2的整数次幂，例如15，那么length-1后为14，换算成二进制后为1110，那么h&（length-1）计算的结果就只有8种可能（因为length-1的二进制中有3个1），其余7个数组下标索引永远选不到，后续存储时table数组空间浪费大，且碰撞概率增加，也会降低查询效率。

Entry＜K，V＞对象结果经过index For方法计算后，就知道它在table数组中的位置i（即下标索引i）。

（3）程序第473～481行的for循环是指如果数组table［i］的值不为空，则需要遍历该位置i（即下标索引i）所在的单向链表。遍历该链表上每一个Entry＜K，V＞对象，判断预计要插入对象的键key是否重复。判断的条件参见程序第475行if语句的布尔表达式“e.hash==hash&&（（k=e.key）==key||key.equals（k））”。

如果预计要插入对象的键key在链表上重复了，于是用新值value覆盖原有Entry＜K，V＞对象的old Value旧值，然后将该key关联的旧值old Value返回。put方法结束。

（4）如果预计要插入对象的键key没有重复，则调用程序第484行add Entry（hash，key，value，i）方法将新的Entry＜K，V＞对象插入数组table［i］所在位置（或其链表）中。addEntry方法源代码如图9-13所示。

图9-13　addEntry方法源代码

当Hash Map集合中的元素越来越多时，碰撞的概率也就越来越高（因为数组的长度是固定的），为了提高查询的效率，就可能要对Hash Map集合的数组进行扩容。

增加新元素之前，程序add Entry方法首先判断是否需要扩容（程序第850行）。当Hash Map集合中的元素个数（size）超过threshold门限阈值（等于数组容量×加载因子load Factor），并且table［bucketIndex］不为null时，Hash Map集合就会调用resize方法进行扩容，传入的新容量参数是旧容量的2倍，即要求扩大一倍。例如，一个数组大小为16、loadFactor默认值为0.75的Hash Map集合，当集合中的元素个数超过16×0.75=12时，就满足“size＞=threshold”条件。

resize方法源代码如图9-14所示。

图9-14　resize方法源代码

程序第554～557行表示如果数组容量到达最大容量，则不扩容，直接返回。

程序第559行根据传入的新容量（即2倍的旧容量）创建一个新的数组Entry［］new Table=new Entry［new Capacity］。

程序第564行调用transfer（new Table，rehash）方法将Hash Map集合原有数据从Entry数组table转移到新的Entry数组new Table里。这是一个非常消耗性能的操作，由于新数组长度变了，对原table里的每一个Entry＜K，V＞对象都需要调用index For方法重新计算其在新数组new Table中的位置索引。因此，构造Hash Map集合时设置较准确的初始容量能有效提高性能。transfer方法源代码如图9-15所示。

图9-15　transfer方法源代码

程序第565行表示扩容完毕后将new Table值赋给table，table指向新的数组空间。

程序第566行重新设置扩容门限threshold。

addEntry方法在处理完扩容问题后（如果不扩容，则跳过），调用createEntry（hash，key，value，bucketIndex）完成真正的插入Entry＜K，V＞对象工作。createEntry方法源代码如图9-16所示。

图9-16　createEntry方法源代码

程序第868行表示将table［bucketIndex］的值赋给局部变量e，如果不为null，e指向该数组位置bucketIndex所在链表的第一个Entry＜K，V＞对象。

程序第869行表示调用有参构造方法创建了一个新的Entry＜K，V＞对象，该对象的next值为e，接着将新创建的Entry＜K，V＞对象的地址赋给table［bucketIndex］。由此可见，新创建的Entry＜K，V＞对象从该链表的头部插入，同一位置上新元素总会被放在链表的头部位置。

（5）回头看put方法的第469行和第470行，表示Hash Map中允许插入键key为null的元素，此时会调用put For Null Key方法。put For Null Key方法源代码如图9-17所示。

图9-17　putForNullKey方法源代码(www.xing528.com)

键key为null，hash值为0，对应的数组table位置为0，put For Null Key方法遍历table［0］所在的Entry＜K，V＞对象链表，寻找e.key==null的Entry＜K，V＞对象，如果存在，则保存键null对应的值到old Value，然后用新值value覆盖原值，并返回old Value。如果不存在键key为null的元素，则程序第501行调用add Entry方法添加。

总结一下，Hash Map添加数据的过程示意图如图9-18所示。

图9-18　Hash Map添加数据过程示意图

5.从Hash Map集合读取数据

Hash Map读取数据的过程，对应Hash Map的get方法。public V get（Object key）方法返回指定键key所映射的值，如果对于该键来说，此映射不包含任何映射关系，则返回null。

注意：

返回null值并不一定表明该映射不包含该键的映射关系，也可能该映射将该键显式地映射为null。此时，可使用public boolean contains Key（Object key）方法来区分这两种情况，如果此映射包含对于指定键的映射关系，则返回true。

get方法源代码如图9-19所示。

图9-19　get方法源代码

（1）程序第403、404行，当键key为null时，get方法调用get For Null Key方法。get For Null Key方法源代码如图9-20所示。

图9-20　getFor Null Key方法源代码

key为null，getFor Null Key方法在table［0］所在链表遍历。如果找到key为null的映射关系，则返回e.value；否则表示没找到key为null的映射关系，返回null。

（2）程序第405行，表示键key不为null时，get方法将调用get Entry方法。get Entry方法源代码如图9-21所示。

图9-21　getEntry方法源代码

程序第443行得到键key的hash值，通过index For（hash，table.length）方法，定位该hash值对应的table数组位置（下标索引），通过for循环遍历该数组索引所在链表上的每个元素，比较它们的键是否满足第448、449行的if条件，如果满足，表示和查询条件键key匹配成功，返回该Entry＜K，V＞对象，否则表示根据键key查询失败，返回null。

（3）程序第407行判断第405行调用getEntry（key）的返回值，如果为null，表示根据key没有找到映射关系，返回null，否则，表示查询key成功，返回该Entry＜K，V＞对象的value。

6.Hash Map构造方法

（1）public Hash Map（）：构造一个具有默认初始容量（16）和默认加载因子（0.75）的空Hash Map。

（2）public Hash Map（int initialCapacity）：构造一个带指定初始容量和默认加载因子（0.75）的空Hash Map。该构造方法实际调用的是Hash Map（initialCapacity，DEFAULT_LOAD_FACTOR）。

（3）public Hash Map（int initialCapacity，float load Factor）：构造一个带指定初始容量和加载因子的空Hash Map。

如果指定的初始容量不是2的整数次幂，构造方法也使用刚好不小于指定初始容量的2的整数次幂来初始化。部分源代码如图9-22所示。

图9-22　构造方法部分源代码

7.Hash Map集合的遍历

【例9-4】

以Hash Map集合为例演示Map集合的遍历。

首先在项目chapter9下新建cn.linaw.chapter9.demo03包，在包里定义一个测试类Hash Map Traversal Test。Hash Map Traversal Test类源代码如图9-23所示。

图9-23　Map集合的遍历

（1）程序第9行采用无参构造方法创建Hash Map＜K，V＞集合，键的类型指定为String，值的类型也指定为String。

（2）程序第10～13行通过调用Map的put方法向集合添加元素。注意，第13行键重复了，则在该键值对中新值会覆盖旧值。

（3）程序第14～22行是遍历Map集合的第一种方法。这种方法先得到Map集合的键对象Set，Set集合是一个单列集合，可以利用Iterator迭代遍历键对象Set，然后根据每一个键得到对应的值。

（4）程序第23～28行是遍历Map集合的第二种方法。和方法1类似，也要先得到Map集合的键对象Set，再从键得到值。不过方法2对键对象Set的遍历采用的是增强for循环这种简写方式。

（5）程序第29～38行是遍历Map集合的第三种方法。这种方法首先通过调用Map集合的entrySet（）方法，该方法返回包含所有Entry＜K，V＞对象的Set，这是单列集合，可以通过Iterator迭代器迭代。注意程序第33行，遍历的每一个元素是Map.Entry＜K，V＞对象，再通过该对象的get Key和get Value方法获取该键和值。

（6）程序第39～44行是遍历Map集合的第四种方法。这种方法是对第三种方法的变形，通过增强for循环简化书写。

8.键对象hash Code方法和equals方法的重写

Hash Map集合存取数据时，讲到了这两个方法。以get方法为例，要利用键对象的hashCode方法最终生成键对象的hash值，然后通过Hash Map的index For方法找到该键对象在数组table的位置（下标索引），接着查找该位置的链表，判断该链表上是否存在要查询的键对象，比较两个键对象是否相等时就要用到键对象的equals方法。

Hash Map中的键对象可以是任何类型的对象，键对象不能重复，但两个具有相同属性（指参与比较的）的键对象必须有相同的hash值，因此需要重写hashCode方法（该方法继承自Object类），相应地，键对象的equals方法也要重写（该方法继承自Object类），两个方法使用的依据要保持一致。

通过改写键对象的hashCode方法和equals方法，我们可以将任意类型的对象作为Map的键。在例9-4中使用String对象作为键对象，而String类已经重写了这两个方法，在Map中通常使用String对象作为键，但是，如果使用自定义的类对象作为键，则必须自己重写hashCode方法和equals方法。

【例9-5】

自定义一个类作为Hash Map的键类型，并测试效果。

步骤1：在cn.linaw.chapter9.demo03包里定义一个雇员Employee类，用它的实例作为键对象。Employee类有两个属性，一个是工号id，一个是姓名name。通常，只要工号id不同，即使姓名重复，Employee对象也是不同的，因此，参与比较的成员属性是工号id。编写Employee类，定义成员属性，并提供一个带参构造方法。

步骤2：通过Eclipse工具重写hashCode方法和equals方法。定义好Employee类的属性后，在Eclipse代码区点击鼠标右键，选择【Source】项目下的【Generate hashCode（）and equals（）】子项目，如图9-24所示。

图9-24　选择【Generate hashCode（）and equals（）】

在弹出的对话框中，勾选重写hashCode（）和equals（）方法时需比较的属性，这里只选择id，如图9-25所示。

图9-25　选择重写hashCode（）和equals（）方法时依据的属性

点击【OK】按钮便自动生成代码。

步骤3：为了测试打印Employee对象内容，需重写toString（）方法。Employee类代码最终如图9-26所示。

图9-26　Employee类

步骤4：通过测试类Hash Map Test来验证以Employee对象作为Hash Map的键，如图9-27所示。

图9-27　验证自定义Employee类作为键类型

（1）程序第9行创建的键对象“new Employee（2，＂李四＂）”根据hash值找到数组位置，然后开始遍历，在该链表上已经有一个元素（第8行添加的），通过重写的equals（）方法，判断这两个键对象是相同的，因此，第9行的新值“3”会替换掉键new Employee（2，＂王五＂）对应的旧值“2”。

（2）第10行创建的键对象（new Employee（3，＂张三＂）），即使name属性值和第7行创建的键对象重复了，但由于id不同，它们的hash值计算出来不相同，就会通过equals方法认定它们两个是不同的对象，一定会添加到该集合里。

大家可以尝试下，如果Employee类里不重写hashCode和equals方法，那么测试类Hash Map Test运行结果会显示4个元素都添加进去了。分析一下为什么。