JDK 1.7 HashMap 解析
HashMap 可以算是 Java 中最常用的几个集合类之一。这一篇文章将在代码层面上详细解释 HashMap 的工作原理及实现方式。为了能够更清晰的说明问题，这篇文章并不会按照源码中的顺序进行讲解，而是按照“添加-->查找-->修改-->删除”的顺序进行，并且也不会讲解所有源码，只会涉及其中的主要部分。
在阅读这篇文章之前，你也可以先阅读《散列表的基本原理》，该文章从理论层面介绍了散列表的基本原理。
1. 类结构
可以通过大纲视图（Outline），先大致了解一下在 JDK 1.7 中 HashMap 大致有哪些内容。
图 1
从图 1 中可以看出，HashMap 中有 9 个内部类，其中类型 Entry<K, V> 就是容纳元素以及其对应键的对象类型，其类型结构如图 2 所示。而其他的几个类型，除 Holder 外，其他的几个类型都是用于遍历元素的容器以及其对应的迭代器，并不是这篇文章讨论的重点。
图 2
Entry 有 4 个成员，value 是 HashMap 的元素；key 是 value 所对应的键；hash 用于保存 key 的散列值，这样在使用的时候，就不需要反复计算 key 的散列值；next 指向那些与此记录发生散列冲突的其他记录。图 3 将展示 HashMap 的成员。
图 3
HashMap 有 7 个成员（非静态成员），entrySet 用于提供方法 entrySet() 返回值的缓存；hashSeed 是当前 HashMap 对象的散列值计算种子；loadFactor 是加载因子；modCount 是 HashMap 的变化标记数，为相关迭代器的快速失败 [1] 提供依据；size 是记录当前 HashMap 中元素的数量；table 就是 HashMap 中的“散列表的表”；threshold 是扩容阈值，当元素数量大于此值时可能发生扩容。
这一节大致介绍了 HashMap 的类型结构，至于它们如何相互协作，将在接下来的小节中详细讨论。在开始接下来的章节之前，先看一下 HashMap 的构造方法。
图 4
图 4 中是开发过程中最常用的 HashMap 无参构造方法，它只做了一件事情，就是将常量 DEFAULT_INITIAL_CAPACITY 和常量 DEFAULT_LOAD_FACTOR 作为参数调用了自身的另一个构造方法 HashMap(int, float)。常量 DEFAULT_INITIAL_CAPACITY 是默认表长，值为 16；常量 DEFAULT_LOAD_FACTOR 是默认加载因子，值为 0.75。如图 5。
图 5
接下来我们看构造方法 HashMap(int, float)。如图 6。
图 6
HashMap(int, float) 就做了许多事情。首先，检查参数 initialCapacity 是否小于 0 ，如果小于 0 就抛出异常。initialCapacity 是 HashMap 初始表长， 自然不能小于 0 。然后检查参数 initialCapacity 是否大于常量 MAXIMUM_CAPACITY，如果大于 MAXIMUM_CAPACITY，就将其等于 MAXIMUM_CAPACITY。MAXIMUM_CAPACITY 是 HashMap 的最大表长，值为 2 ^ 30。如图 7。
图 7
再然后检查 loadFactor 是否是小于等于 0 或为 NaN [2]，如果是，将抛出异常。接下来就将 HashMap 的成员 loadFactor 赋值为参数 loadFactor，将成员 threshold 赋值为 initialCapacity。最后调用方法 init()。init() 是一个空方法，什么也不做，那么问题就来了，HashMap 有 7 个非静态成员，为什么这里只处理了 2 个？在解答这个问题之前，先看一下 HashMap 成员的初始值，如图 8 。
图 8
可以看到，几个 int 类型的成员要么写了初始值为 0，要么没有写初始值，那么这些成员初始都为 0 。table 被赋值为常量 EMPTY_TABLE，在下面的小节中会说明 EMPTY_TABLE 是什么。entrySet 初始值为 null。至此，HashMap 的 7 个非静态成员在构造时的初始值就明确了。
2. 添加元素
从这一节开始，我们将一步一步的分析并理解 HashMap 的实现。首先分析 HashMap 添加元素的方法 put(K, V)。
图 9
图 9 中方法 put(K, V) 的我们再熟悉不过了，就不再介绍两个参数，直接从方法体开始。方法先检查当前对象的 table 是否与 EMPTY_TABLE 为同一个对象，那么 EMPTY_TABLE 是什么呢？它长图 10 这样。
图 10
在上一节中，介绍了 HashMap 构造时，会指定 table 的初始值为 EMPTY_TABLE 而不是创建一个空数组，原因就是如果每次 HashMap 创建了一个新对象但是不使用的话，那么这个 table 的数组仍然会被白白的创建出来。但是，如果 HashMap 在创建一个新对象的时候，并不创建这个数组，而是指向一个全局的、不使用的常量，那么即使创建了许多不使用的 HashMap 对象，也是不会白白创建许多用不到的数组来浪费内存。现在回到方法 put(K,V) 中。
图 11
方法 put(K,V) 中第一个表达式如果为真，就将 HashMap 的成员 threshold 作为参数调用方法 inflateTable(int)。inflateTable(int) 方法如图 12 。
图 12
inflateTable(int) 方法首先将 toSize 作为参数调用方法 roundUpToPowerOf2(int) [3]，并将得到的结果赋值给 capacity [4]。然后，取 capacity * loadFactor 和 MAXIMUM_CAPACITY + 1 中较小的值作为新的扩容阈值，目的在于防止加载因子过大而使得 HashMap 无法扩容。接下来，HashMap 才真正创建 table，其长度为刚刚得到的 capacity。最后，调用 initHashSeedAsNeeded(int) [5] 获取一个散列种子。
现在又回到方法 put(K, V) 中，继续往下看。
图 13
图 13 的是方法 put(K, V) 中的第二个条件表达式，检查 key 是否为 null，如果为 null，把 value 作为参数调用方法 putForNullKey(K)，并将其返回的结果作为自身的结果直接返回。方法 putForNullKey(K) 如图 14。
图 14
方法 putForNullKey(K) 中的 for 语句做了这么一件事情，它将检查 table[0] 中的所有记录，如果有某个记录的 key 也是 null，将用参数 value 替换原来记录的 value，然后调用被替换 value 的记录的方法 recordAccess(HashMap) [6] 后，最后将原来的 value 值返回。从这里可以看出，HashMap 总是会将 key 为 null 的记录放置于 table[0] 的位置。
如果 for 语句执行完后，此方法没有被返回，说明在这个 HashMap 中并不存在 key 为 null 的记录，因此需要新建一条记录。在使 modCount 自增 1 后，将 0、null、value 和 0 作为参数调用方法 addEntry(int, K, V, int) 以添加一个新的记录。addEntry(int, K, V, int) 如图 15。
图 15
方法 addEntry(int, K, V, int) 首先将检查当前 HashMap 中的元素数量是否超过扩容阈值并且 table 指定的位置上是否发生散列冲突，如果是这样，HashMap 将进行扩容。扩容在第 5 节详细讨论。不论是否发生了扩容，都会将 hash、key、value、bucketIndex 作为参数调用方法 createEntry(int, K, V, int) 以创建一个新的记录。方法 createEntry(int, K, V, int) 如图 16。
图 16
方法 createEntry(int, K, V, int) 做的事情就比较简单了，它先取出当前 table[buketIndex] 中的记录，如果原来没有记录，这里就得到 null。然后将 hash、key、value 和这个取出的记录作为参数，构造一个新的记录 [7]，并将这个新纪录放置于 table[buketIndex] 中。最后把 size 自增 1 以表示添加了一个元素。方法 createEntry(int, K, V, int) 执行完成后，key 为 null 的添加流程就结束了。接下来，回到方法 put(K, V) 继续分析 key 不为 null 时的添加流程。
如果方法 put(K, V) 在第二个分支语句中并没有被返回，则表示添加的元素的键并不是 null，那么将把 key 作为参数调用方法 hash(Object) 得到这个 key 的散列值。
图 17
方法 hash(Object) 如图 18 。
图 18
方法 hash(Object) 首先将检查参数 k 是否是一个 String 类型对象，如果是，将调用方法 stringHash32(String) [8] 以计算这个 String 对象的散列值。如果不是，先调用参数 k 的方法 hashCode() 获取原始散列值，将这个原始散列值与自身的散列种子做异或运算得到一个粗加工的散列值，然后分段折叠这个粗加工的散列值，最终得到一个新散列值。
这里的算法将异或运算视作二进制串的“特征合并”，因为 HashMap 在根据散列值得到 table 对应索引的算法中，只会使用与 table 长度对应的二进制串所对等的位，那么当 table 长度较短时，并不会使用到二进制串的高位，所以将二进制串的高位的“特征”通过异或运算“合并”到二进制串的低位中，可以减少因高位不同低位相同的二进制串导致的散列冲突。继续回到方法 put(K, V) 中。
图 19
在得到了 key 的新散列值之后，将得到的散列值和 table 的长度作为参数调用方法 indexFor(int, int) 。方法 indexFor(int, int) 只有一句话，如图 20。
图 20
方法 put(K, V) 接下来的流程，与方法 putForNullKey(K) 图 14 类似，区别仅在于 key 不再是一个 null 值，因此在判断相等时，先检查两个 key 的散列值是否相等，然后检查两个 key 是否是同一个对象，再调用 key 的方法 equals(Object) 进行比较。
图 21
至此，HashMap 的添加流程就已经结束。
3. 查找元素
这一节中，将分析查找元素的方法 get(Object) [9]。
图 22
方法 get(Object) 首先检查 key 是否为 null，如果为 null ，就执行方法 getForNullKey()，并将其返回值作为自身方法的返回值返回。方法 getForNullKey() 如图 23。
图 23
还记得添加元素时对 key 为 null 的元素的操作吗？HashMap 总是将 key 为 null 的元素放置于 table[0] 的位置，那么方法 getForNullKey() 也会在 table[0] 的位置中去找对应的元素。首先，检查当前 HashMap 的元素数量是否为 0 ，如果为 0 ，那么表示没有任何元素，直接返回 null。否则，检查 table[0] 中链式结构的所有记录，如果有某个记录的 key 为 null，就将其 value 值返回。如果循环结束后仍然没有找到对应的记录，返回 null。
方法 getForNullKey() 执行完后，key 为 null 的查找流程就结束了。接下来，回到方法 get(Object) 中，继续分析 key 不为 null 时的查找流程。
如果方法 get(Object) 没有在第一个分支语句中被返回，接下来它将把 key 作为参数执行方法 getEntry(Object)。如果方法 getEntry(Object) 得到了一个记录，表示查找成功，返回这个记录的 value；如果得到 null，表示查找不到指定的元素，返回 null。方法 getEntry(Object) 如图24。
图 24
方法 getEntry(Object) 同样会先检查当前 HashMap 的元素数量是否为 0 ，如果为 0 ，那么表示没有任何元素，直接返回 null。否则，先把 key 作为参数调用方法 hash(K)，以得到一个新的散列值。接下来的 for 语句中，根据得到的新散列值和 table 的长度获取这个新散列值对应于 table 的索引，然后一次遍历这个位置上的链式结构中的每一个记录，进行与添加流程类似的 key 匹配检查，如果找到匹配的记录，返回这个记录，否则返回 null。
4. 删除元素
这一节中，将分析删除元素的方法 remove(Object)。
图 25
方法 remove(Object) 比较简单，它先将 key 作为参数调用方法 removeEntryForKey(Object)，如果方法 removeEntryForKey(Object) 移除了一个记录，将把移除的记录作为返回值返回，如果返回 null，表示没有记录被移除。方法 removeEntryForKey(Object) 如图 26。
图 26
方法 removeEntryForKey(Object) 虽然很长，但是如果理解了添加、查找流程，理解删除流程也不困难。方法 removeEntryForKey(Object) 仍然会先检查当前 HashMap 的元素数量是否为 0，如果为 0 ，那么表示没有任何元素，直接返回 null。如果元素数量不为 0，和其他流程类似的，先通过方法 hash(Object) 得到 key 的新散列值，然后调用方法 indexFor(int, int) 得到这个新散列值对应 table 中的位置。接下来的 while 语句实际上和添加、查找流程中的记录查找类似，不同的地方是，如果找到的对应的记录，先将 modCount 自增，然后使 size 自减，再检查这个移除的记录是否是其所在链式结构的第一个节点，如果不是，将被移除的节点的上一节点的 next 指向被移除的节点的下一节点，如果是，则将 table 中对应位置指向移除节点的下一节点。最后再调用被移除的记录的方法 recordRemove(HashMap) [10] ，最后返回被移除的记录。
5. 扩容
现在回到添加流程中，看看 HashMap 如何在添加的过程中进行扩容的。在方法 addEntry(int, K, V, int) 中有如图 27 的一段代码。
图 27
这段代码的逻辑是检查当前 HashMap 中的元素数量是否超过扩容阈值并且在 table 指定的位置上发生了散列冲突，如果是这样，HashMap 将进行扩容。
如果进行扩容，将把当前 table 的长度乘 2 后作为参数调用方法 resize(int) 进行扩容，扩容完成后，由于 table 的长度变化了，所以需要重新计算散列值和 table 对应的索引后才能继续添加流程。方法 resize(int) 如图 28。
图 28
方法 resize(int) 首先检查当前 table 的长度是否已经到达 HashMap 的最大 table 长度，如果是，则将扩容阈值设置为整数最大值后直接返回，这样将不再触发扩容。如果不是，接下来将创建一个新的数组，长度为参数 newCapacity 指定，将这个值作为参数调用方法 transfer(Entry[], boolean) 以扩容，完成之后将这个新的数组作为 HashMap 的 table，并计算出新的扩容阈值。方法 transfer(Entry[], boolean) 如图 29。
图 29
方法 transfer(Entry[], boolean) 遍历当前 table 中的所有记录，根据每一个记录的散列值和新的 table 长度计算出对应于新的数组位置后，将记录按照添加流程中的方式添加到新的数组中，完成扩容。
读完这篇文章，你应该基本明白了 HashMap 的基本原理以及实现方式，甚至可以自己实现一个。
[1] 迭代器的快速失败是指：容器在每次元素结构发生变化（添加或删除）时，都会使自身的一个标记值发生改变，这个标记值在创建迭代器的时候，会被复制到迭代器中，迭代器每次迭代时，都会检查自身的这个标记值和被迭代的容器中的标记值是否一致，如果不一致，将抛出异常阻止迭代的继续。这种方式能够在一定程度上阻止由于迭代过程中，被迭代的容器结构发生变化而使的迭代器行为不可控。
[2] Java 中的 float 和 double 都是浮点型，有表示为 NaN 的格式。具体参见《浮点型数据的格式》。
[3] 方法 roundUpToPowerOf2(int) 将返回一个比参数大的且一定是 2 的 N 次幂的整数。这个方法不在这篇文章的讨论范围内。
[4] 这里就是为什么 HashMap 的 table 的长度总是 2 的 N 次幂的原因：capacity 得到值是方法 roundUpToPowerOf2(int) 返回的，并且第一次是使用 threshold 作为参数，threshold 默认为 16。所以第一次得到结果就是 16。
[5] 方法initHashSeedAsNeeded(int) 将根据当前的 hashSeed 和指定的 capacity 计算是否需要获取下一个随机的散列值种子。这个方法不在这篇文章的讨论范围内。
[6] 方法 recordAccess(HashMap) 是 Entry 中的方法，默认是一个空方法。这个方法不在这篇文章的讨论范围内。
[7] Entry 的构造方法直接将 4 个参数直接赋值到自身对应的成员，并没有做其他处理。
[8] 方法 sun.misc.Hashing.stringHash32(String) 将获取一个 String 的散列值， JDK 1.8 的 HashMap 中不再使用。这个方法不在这篇文章的讨论范围内。
[9] 方法 get(Object) 的参数类型为什么不是 K 而是 Object？是为了在使用过程中不需要进行类型转换，并且某些不同类型的等价对象也可以进行键的匹配。
[10] 方法 recordRemove(HashMap) 是 Entry 中的方法，默认是一个空方法。这个方法不在这篇文章的讨论范围内。
