浅入浅出 1.7和1.8的 HashMap

前言

HashMap 是我们最最最常用的东西了，它就是我们在大学中学习数据结构的时候，学到的哈希表这种数据结构。面试中，HashMap 的问题也是常客，现在卷到必须答出来了，是必须会的知识。
我在学习 HashMap 的过程中，也遇到了不少问题，从概念到使用，整个过程都大大小小有些疑惑，然而我这些疑惑是因为我在某个知识环节上出了问题，导致不能理解，当我看了网上各种关于 HashMap 的有关博客以及 HashMap 的源码后，大致是理解了，但是我又不确定我是否是真的理解了，决定把 HashMap 的基本必须会的知识全部梳理下来，势必得搞定它！

从最开始只是会使用它的 API 进行数据的存取，到决定要搞定疑惑、搞懂它的底层原理！

本篇文章，将从 0 浅入，从什么是哈希表讲起，然后再说 Java 是怎样实现哈希表的。整个梳理过程，将通过源码这个第一手的资料进行梳理分析，吸收知识、解决疑问，一步一步进行梳理，如果你是对 HashMap 懵懵懂懂的同学，那么欢迎跟着我的节奏一起来梳理！
阅读完本篇文章，你将收获：

• 认识哈希表、哈希冲突、冲突解决方法...
  
• 明白 Java 中哈希表是怎样实现的...
  
• table 数组的意思、哈希桶的意思、Entry 的意思、Node 的意思...
  
• 1.7 的 HashMap 源码分析流程...
  
• 明白为什么已经有了 hashCode() 方法了，为什么还需要 hash() 方法
  
• 整个 put、get、扩容的过程...
  
• 1.8 的 HashMap 与 1.7 的不同的地方...
  
• 1.8 的扩容和 1.7 的扩容不一样的地方...
  

总之，我相信屏幕前的你读完肯定是有收获的，当然，最大的收获目前是我自己哈哈哈。
全文1万2000多字，欢迎慢慢食用！由于本人水平有限，文中肯定还有许多不足之处，欢迎大家指出！
学习 HashMap 之前，我们需要知道什么？

我们知道 HashMap 就是 Java 中对哈希表这种数据结构的实现，倘若你不知道什么是哈希表，那么自然学习 HashMap 就会有大大的困难，倘若你知道哈希表，但仅仅是懵懵懂懂，有个简单了解，那自然困难会降低许多。
所以，在学习 HashMap 之前，我们自然需要先知道什么是哈希表，当然还需要知道链表，不过本篇文章仅对哈希表作出说明。下面将开始讲讲哈希表这种抽象的数据结构，之所以说抽象，是因为下面只说哈希表应该具备的功能，但是不会给出具体实现，比如说我们可以简单地使用数组来实现哈希表，是吧，但是 Java 中的哈希表的实现就不是单单一个数组就实现了的。
好了，废话少说，开搞！

什么是哈希表？

哈希表（Hash Table，也有另一个称呼：散列表）。
哈希表是一种可以通过键（Key）直接访问存储在某个位置上的值（Value）的数据结构。
Hash 被翻译成「哈希」、「散列」。Key 被翻译成「键」、「关键字」
哈希表可以用来干嘛？

很简单，和我们以前学习的数据结构一样，可以用来存储数据。
这不是废话嘛？确实是废话。
好吧，那么都可以存储数据，为什么还会出现哈希表？直接用以前的顺序表、链表、栈、队列，这些数据结构来存储不行吗？这个问题问得好，确实，反正都是存储，为什么还要哈希表？
要回答这个问题，就得说说为什么要有数据结构了，之所以需要数据结构，有一个目的就是：更有效地进行数据的存储，不同的数据结构有不同的特性，顺序表可以通过下标快速的查找出数据、链表可以不需要占用一整片连续的存储空间进行存储等等。哈希表也是一样。
哈希表如何存储数据？

哈希表存储数据，给定一个 Key，存储一个 Value。这里就需要用到一个哈希函数（散列函数）。
以数学中的「函数」来理解，就是有一个函数是这样的 $f(x) = y$，一个 $x$ 通过函数 $f$ 映射成值 $y$ 。
那么哈希函数也可以这样理解：$hash(key) = address$
即键通过哈希函数映射成了一个地址，这个地址可以是数组下标、内存地址等。
所以呢，存储就是，通过哈希函数，把 Key 映射到某个地址，然后将 Value 存储到这个地址上。
那么存储后如何获取，如何查找到这个 Value 呢？还是一样，通过哈希函数获得 Key 映射的地址，然后从这个地址取出 Value 。理想的情况下，在哈希表中查找数据，查找的时间复杂度是 $O(1)$ 。
所谓的「哈希」，就是 Key 通过哈希函数得到一个函数值（哈希值、哈希地址）的过程。
什么是哈希冲突？

在数学上，函数的映射可以是一对一，也可以是多对一的，也就是说一个 $x$ 可以映射一个 $y$ ，也可以多个 $x$ 映射到同一个 $y$ 上。
哈希函数也一样，它有可能出现多对一的情况，即多个不同的 Key，通过哈希函数得到同一个地址（哈希值）。
这就出现问题了，这种情况，就称为「哈希冲突」。

哈希冲突完整定义：哈希函数可能把两个或两个以上的不同关键字映射到同一个地址，这种情况称为冲突。发生冲突的不同关键字称为同义词。

你想一下，如果两个不同的 Key，比方说 Key1 和 Key2，通过哈希函数得到同一个地址，那么你不解决这个冲突，直接进行存储，那么就是这样的：

• Key1 先存储，Key2 后存储，自然只保存了 Key2
  
• Key2 先存储，Key1 后存储，自然只保存了 Key1
  

这种情况是我们不想看到的，所以我们必须解决冲突。
如何解决冲突？

在解决冲突之前，我们应该尽量减少冲突的发生，这就需要设计得OK的哈希函数。当然冲突是必然的，是逃不掉的，当数据量够多的时候，必然会发生冲突，所以就需要设计好解决冲突的方法。
哈希函数的设计注意点：

• 函数的定义域必须包含所有的 Key，函数的值域必须包含所有的 Value。其中值域是跟哈希表的大小有关的。
  
• 函数计算出来的地址（哈希值）应该能够均匀分布在哈希表的内存地址空间上，从而减少冲突的发生。
  
• 函数能够简单就简单实现，这样计算会很快。
  

解决冲突的方法：
解决冲突的思想就是为冲突的 Key 找下一个没有被占用的地址。

• 开放定址法
  
• 拉链法
  

这里就只说这个拉链法。
拉链法

把所有发生冲突的 Key 存储在一个线性链表中，这个链表由 Key 哈希过后得到的地址（哈希地址）唯一标识，这就是拉链法，适用于经常插入和删除的情况。
哈希表查找效率

平均查找长度（ASL-Average Search Length），可衡量哈希表的查找效率。
ASL依赖于哈希表的「装填因子（负载因子）」
$$
装填因子的定义：α = \frac{哈希表中的元素个数}{哈希表的长度}​
$$
装填因子越大，那么冲突的可能就越大，反之亦然。
1.7 版 HashMap


现在知道什么是哈希表了，那么接下来就看看 Java 中对哈希表的实现——HashMap
再次初识 1.7 的 HashMap

我们先看看文档是怎样说的，同时我进行了大体的翻译。（这些说明可以从源码的开头找到）

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

哈希表是通过实现 Map 接口实现的，因为 Map 接口提供了所有的映射操作，并且允许空值和空键（HashMap这个类可以简单的看作是 HashTable 类，与之不同是，HashMap 是非同步且允许存储空数据的）。HashMap 这个类不保证映射的顺序，特别是不保证这个顺序会随着时间的改变而保持不变。

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

当哈希函数恰当地将元素映射到哈希桶（the buckets）中，那么就具有常量时间里的基本操作（get 和 put）性能。遍历 HashMap 这个集合的时候，遍历的时间与 HashMap 实例的容量（哈希桶的数量）加上它的大小（Key和Value的映射数量，即键值对的数量）成正比，因此，不要设置初始的容量太高，或者负载因子太低，这是非常重要的。

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

HashMap 的实例，有两个参数会影响它的性能：初始容量和负载因子。
初始容量就是哈希表中的哈希桶的数量，所谓哈希桶，就是一个个的数组元素所占的坑位，我们可以称整个数组为 table 数组，然后里面的一个个元素位置（table）就是哈希桶。你给定一个初始容量，那么这个容量就会在 table 数组创建的时候，作为这个 table 数组的容量，即其长度、大小。
负载因子是衡量在当前 HashMap 自动扩容前，有多少个哈希桶是可以被获取到的。当哈希表中的 Entry 对象（键值对）的数量超过了负载因子和当前容量的乘积时（load factor × capacity），那么哈希表就会进行重新哈希（rehashed，重构整个哈希表），table 数组就变为原来的两倍大，即扩容两倍。

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

通常来说，默认的负载因子是 0.75，它是一个很好的平衡，平衡了时间以及空间，这个值过高，虽然会降低空间的开销，但是会增加更多的时间来查找。当设置 HashMap 的初始容量时，应该。考虑好预期的 Entry 数量以及负载因子，以此减少 rehash 的次数。如果哈希表的初始容量（table 数组的长度）大于 Entry 数量除以负载因子，则不会发生 rehash 操作。

If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table. Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.

如果需要使用 HashMap 实例来存储许多的映射，那么就需要创建一个够大容量的 HashMap 实例，这样效率是最大的，比起你搞一个小容量的 HashMap，然后让它自己 rehash、table 数组翻倍。注意，使用许多有着相同 hashCode() 的 Key 的话，那肯定是会降低哈希表的性能的，因为冲突多了，为了降低这种影响，当这些 Key 是可比较的情况下，那么哈希表旧可以使用比较的方式去解决。

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

1. Map m = Collections.synchronizedMap(new HashMap(...));

复制代码

上面的意思就是说，需要注意 HashMap 是不同步的，也就是非线程安全的，在多线程并发的情况下对 HashMap 进行操作（添加、删除、映射），就会发生线程安全问题，导致数据不一致，如果想在多线程的情况下使用 HashMap，那么可以使用 Collections.synchronizedMap 方法将普通的 HashMap 包装成同步的 HashMap。不过不推荐这样使用，我们推荐使用 ConcurrentHashMap。

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

迭代器快速失败（fail-fast）：如果 Map 在迭代器进行迭代的时候，Map 中的数据被修改了，那么迭代器就会抛出一个异常：ConcurrentModificationException。因为怕有不确定的行为风险，主要来说就是怕数据不一致，怕线程不安全。
看完了文档的说明，现在可以知道，HashMap 大概有这样的东西

• 哈希表的键值对（Entry）是存储在一个名为 table 的数组中的。Entry 的话，是把 Key、Value、hash 值，封装为 Entry 对象。
  
• table 数组里面的一个个元素位置（table）就是哈希桶。
  
• 哈希桶存储的就是 Entry，也就是说一个个的哈希桶，存储着一个个的 Entry 对象。
  
• 哈希表的初始容量指的就是 table 数组的长度。
  
• 哈希表的容量指的是 table 数组的长度；哈希表的大小指的是 Key 和 Value 映射的数量，即键值对的数量。这个很重要，需要搞清楚哈希表的「容量」和「容量」，别搞混了。
  
• 当 Entry 对象的数量 > load factor × capacity 时，就会自动扩容，table 数组扩容为原来的两倍。
  
• 哈希表是线程不安全的。
  

看到这里，可能还是有些抽象，没事，接下来我们看下源码。
HashMap 中的成员变量

首先先看看 HashMap 定义的成员变量：

1. public class HashMap<K,V>
2.     extends AbstractMap<K,V>
3.     implements Map<K,V>, Cloneable, Serializable
4. {
5.     /**
6.      * The default initial capacity - MUST be a power of two.
7.      * 默认的初始化容量大小为16，这个大小必须为2次幂
8.      */
9.     static final int DEFAULT_INITIAL_CAPACITY = 16;
10.    
11.     /**
12.      * The maximum capacity, used if a higher value is implicitly specified
13.      * by either of the constructors with arguments.
14.      * MUST be a power of two <= 1<<30.
15.      * 最大的容量，如果任意带参构造函数传入的值大于这个最大容量，就使用这个最大容量
16.      * 1 左移 30位，即 2的30次方
17.      */
18.     static final int MAXIMUM_CAPACITY = 1 << 30;
19.    
20.     /**
21.      * The load factor used when none specified in constructor.
22.      * 默认负载因子 0.75
23.      */
24.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
25.    
26.     /**
27.      * The table, resized as necessary. Length MUST Always be a power of two.
28.      * table 数组，必要时就可以重置大小，长度必须总是2次幂，注意这里的数组类型的 Entry
29.      * Entry 是一个内部类，下面就可以看到了
30.      */
31.     transient Entry[] table;
32.     ...
33.     /**
34.      * Entry 类，主要作为一个存储 Key 和 Value 的节点，同时保存当前的通过哈希函数计算出来的 hash
35.      * next 指针，主要用于发生冲突时，使用拉链法解决冲突，指向链表下一个 Entry 节点的
36.      */
37.     static class Entry<K,V> implements Map.Entry<K,V> {
38.         final K key;         // 键
39.         V value;                 // 值
40.         Entry<K,V> next; // 指向下一个节点 ，从而形成解决冲突的链表
41.         final int hash;  // 哈希值
42.         ...
43.     }
44.    
45.     /**
46.      * The number of key-value mappings contained in this map.
47.      * size 代表的就是当前存储在 map 中的 Key-Value 映射的数量，即 Entry 的数量
48.      */
49.     transient int size;
50.    
51.     /**
52.      * The next size value at which to resize (capacity * load factor).
53.      * @serial
54.      * table 重置大小的阈值，这个阈值就是之前说的 load factor * capacity
55.      */
56.     int threshold;
57.    
58.     /**
59.      * The load factor for the hash table.
60.      *
61.      * @serial
62.      * 负载因子
63.      */
64.     final float loadFactor;
65.    
66.      /**
67.      * The number of times this HashMap has been structurally modified
68.      * Structural modifications are those that change the number of mappings in
69.      * the HashMap or otherwise modify its internal structure (e.g.,
70.      * rehash).  This field is used to make iterators on Collection-views of
71.      * the HashMap fail-fast.  (See ConcurrentModificationException).
72.      * 这个变量主要与 fail-fast 快速失败 有关，后面再说，先留个印象。
73.      */
74.     transient int modCount;
75.     ...
76. }

复制代码

Node 数组

1.     /**
2.      * Constructs an empty <tt>HashMap</tt> with the specified initial
3.      * capacity and load factor.
4.      *
5.      * @param  initialCapacity the initial capacity
6.      * @param  loadFactor      the load factor
7.      * @throws IllegalArgumentException if the initial capacity is negative
8.      *         or the load factor is nonpositive
9.      */
10.     public HashMap(int initialCapacity, float loadFactor) {
11.         // 下面3个if，是保证代码的健壮性，不是主要内容
12.         // 初始容量小于0，那么抛出非法参数异常
13.         if (initialCapacity < 0)
14.             throw new IllegalArgumentException("Illegal initial capacity: " +
15.                                                initialCapacity);
16.         // 初始容量大于最大容量（2^30），直接将2^30作为初始容量
17.         if (initialCapacity > MAXIMUM_CAPACITY)
18.             initialCapacity = MAXIMUM_CAPACITY;
19.         // 如果负载因子小于等于0，或者负载因子有问题，抛出异常
20.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
21.             throw new IllegalArgumentException("Illegal load factor: " +
22.                                                loadFactor);
23.                 // 主要内容在这里
24.         // Find a power of 2 >= initialCapacity
25.         // 找到一个二次幂的数，如果当前输入的初始容量刚好的二次幂，就不用找了
26.         int capacity = 1;
27.         while (capacity < initialCapacity)
28.             capacity <<= 1;
29.                
30.         this.loadFactor = loadFactor;                                // 初始化，赋值
31.         threshold = (int)(capacity * loadFactor);        // 自动扩容的阈值
32.         table = new Entry[capacity];                                // 创建大小为capacity的Entry数组
33.         init();        // 一个空方法，有什么用？这个先不管，之后再说，目前知道上面的就足够了。
34.     }

复制代码

扰动函数

hash()，扰动函数发生了变化，1.8 源码是这样的：
让 Key 的 hashCode 与上 hashCode 无符号右移 16 位，最终与运算的结果就是最终的 hash 值。

1.         public HashMap(int initialCapacity) {
2.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
3.     }

复制代码

而 1.7 的是这样的：

1.         public HashMap() {
2.         this.loadFactor = DEFAULT_LOAD_FACTOR;
3.         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
4.         table = new Entry[DEFAULT_INITIAL_CAPACITY];
5.         init();
6.     }

复制代码

构造方法

构造方法也有变化，但是主要的过程还是一样的，主要的区别就是，此时的 table 数组还没有被创建出来。
[code]    /**     * Returns a power of two size for the given target capacity.     */    static final int tableSizeFor(int cap) {        int n = cap - 1;        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    }        public HashMap(int initialCapacity, float loadFactor) {        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        if (loadFactor