HashMap 源码分析（JDK1.8）

HashMap 是 Java 和 Android 程序员的基本功， JDK1.8 对 HashMap 进行了优化， 你真正理解它了吗？

考虑如下问题：

1、哈希基本原理？（答：散列表、hash 碰撞、链表、红黑树）

2、hashmap 查询的时间复杂度， 影响因素和原理？ （答：最好 O（1），最差 O（n）， 如果是红黑 O（logn））

3、resize 如何实现的， 记住已经没有 rehash 了！！！（答：拉链 entry 根据高位 bit 散列到当前位置 i 和 size+i 位置）

4、为什么获取下标时用按位与 &，而不是取模 %？ （答：不只是 &速度更快哦， 我觉得你能答上来便真正理解 hashmap 了）

5、什么时机执行 resize？

答：hashmap 实例里的元素个数大于 threshold 时执行 resize(即桶数量扩容为 2 倍并散列原来的 Entry)。 PS：threshold=桶数量*负载因子

 1final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 2               boolean evict) { 3    Node<K,V>[] tab; Node<K,V> p; int n, i; 4    if ((tab = table) == null || (n = tab.length) == 0) 5        n = (tab = resize()).length;   //初始化桶，默认16个元素 6    if ((p = tab[i = (n - 1) & hash]) == null)   //如果第i个桶为空，创建Node实例 7        tab[i] = newNode(hash, key, value, null); 8    else { //哈希碰撞的情况， 即(n-1)&hash相等 9        Node<K,V> e; K k;10        if (p.hash == hash &&11            ((k = p.key) == key || (key != null && key.equals(k))))12            e = p;   //key相同，后面会覆盖value13        else if (p instanceof TreeNode)14            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //红黑树添加当前node15        else {16            for (int binCount = 0; ; ++binCount) {17                if ((e = p.next) == null) {18                    p.next = newNode(hash, key, value, null);  //链表添加当前元素19                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st20                        treeifyBin(tab, hash);  //当链表个数大于等于7时，将链表改造为红黑树21                    break;22                }23                if (e.hash == hash &&24                    ((k = e.key) == key || (key != null && key.equals(k))))25                    break;26                p = e;27            }28        }29        if (e != null) { // existing mapping for key30            V oldValue = e.value;31            if (!onlyIfAbsent || oldValue == null)32                e.value = value;33            afterNodeAccess(e);34            return oldValue;            //覆盖key相同的value并return， 即不会执行++size35        }36    }37    ++modCount;38    if (++size > threshold)    //key不相同时，每次插入一条数据自增1. 当size大于threshold时resize39        resize();40    afterNodeInsertion(evict);41    return null;42 }

6、为什么负载因子默认为 0.75f ？ 能不能变为 0.1、0.9、2、3 等等呢？

答：0.75 是平衡了时间和空间等因素； 负载因子越小桶的数量越多，读写的时间复杂度越低（极限情况 O(1), 哈希碰撞的可能性越小）； 负载因子越大桶的数量越少，读写的时间复杂度越高(极限情况 O(n), 哈希碰撞可能性越高)。 0.1，0.9，2，3 等都是合法值。

7、影响 HashMap 性能的因素？

(1) 负载因子；

(2) 哈希值；理想情况是均匀的散列到各个桶。 一般 HashMap 使用 String 类型作为 key，而 String 类重写了 hashCode 函数。

1static final int hash(Object key) {2        int h;3        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);4}

8、HashMap 的 key 需要满足什么条件？

答：必须重写 hashCode 和 equals 方法， 常用的 String 类实现了这两个方法。

9、HashMap 允许 key/value 为 null， 但最多只有一个。 为什么？

答： 如果 key 为 null 会放在第一个桶（即下标 0）位置， 而且是在链表最前面（即第一个位置）。

JDK1.8 的 HashMap 源码：http://www.grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#HashMap

我的习惯是先看注释再看源码并调试， 先翻译一下源码注释吧， 不准之处请指正哈。

Hash table based implementation of the Map interface. This implementation provides all of the optional map

HashTable 实现了 Map 接口类， 这些接口实现了所有可选的 map 功能， 包括允许空值和空 key。

operations, and permits null values and thenull key. (TheHashMap class is roughly equivalent toHashtable, 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.

HashMap 和 HashTable 基本一致， 区别是 HashMap 是线程不同步的且允许空 key。 HashMap 不保证 map 的顺序， 而且顺序是可变的。

This implementation provides constant-time performance for the basic operations (get andput), assuming the hash function disperses the elements properly among the buckets.

如果将数据适当的分散到桶里， HashMap 的添加、查询函数的执行周期是常量值。

Iteration over collection views requires time proportional to the “capacity” of theHashMap 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.

使用迭代器遍历所有数据的性能跟 HashMap 的桶（bucket）数量有直接关系， 为了提高遍历的性能， 不能设置比较大的桶数量或者负载因子过低。

An instance of HashMap has two parameters that affect its performance:initial capacity andload factor. Thecapacity 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.

HashMap 实例有 2 个重要参数影响它的性能： 初始容量和负载因子。 初始容量是指在哈希表里的桶总数， 一般在创建 HashMap 实例时设置初始容量。

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 isrehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

当哈希表的数据个数超过负载因子和当前容量的乘积时， 哈希表要再做一次哈希（重建内部数据结构）， 哈希表每次扩容为原来的 2 倍。

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 theHashMap class, including get and put).

负载因子的默认值是 0.75， 它平衡了时间和空间复杂度。 负载因子越大会降低空间使用率，但提高了查询性能（表现在哈希表的大多数操作是读取和查询）

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.

考虑哈希表的性能问题， 要设置合适的初始容量，从而减少 rehash 的次数。 当哈希表中 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 arejava.lang.Comparable, this class may use comparison order among keys to help break ties.

如果有很多值要存储到 HashMap 实例中， 在创建 HashMap 实例时要设置足够大的初始容量， 避免自动扩容时 rehash。 如果很多关键字的哈希值相同， 会降低哈希表的性能。 为了降低这个影响， 当关键字支持 java.lang.Comparable 时， 可以对关键字做次排序以降低影响。

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, itmust be synchronized externally. (A structural modification

哈希表是非线程安全的， 如果多线程同时访问哈希表， 且至少一个线程修改了哈希表的结构， 那么必须在访问 hashmap 前设置同步锁。（修改结构是指添加或者删除一个或多个 entry， 修改键值不算是修改结构。）

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.

一般在多线程操作哈希表时， 要使用同步对象封装 map。

If no such object exists, the map should be “wrapped” using theCollections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

如果不封装 Hashmap， 可以使用 Collections.synchronizedMap 方法调用 HashMap 实例。 在创建 HashMap 实例时避免其他线程操作该实例， 即保证了线程安全。

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

JDK1.8 对哈希碰撞后的拉链算法进行了优化， 当拉链上 entry 数量太多（超过 8 个）时，将链表重构为红黑树。 下面是源码相关的注释：

This map usually acts as a binned (bucketed) hash table, but

when bins get too large, they are transformed into bins of

TreeNodes, each structured similarly to those in

java.util.TreeMap. Most methods try to use normal bins, but

relay to TreeNode methods when applicable (simply by checking

instanceof a node). Bins of TreeNodes may be traversed and

used like any others, but additionally support faster lookup

when overpopulated. However, since the vast majority of bins in

normal use are not overpopulated, checking for existence of

tree bins may be delayed in the course of table methods

看看 HashMap 的几个重要成员变量：

//The default initial capacity - MUST be a power of two.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //为什么不写成 16？？？ 大师是想用这种写法告诉你只能是 2 的幂

HashMap 的初始容量是 16 个， 而且容量只能是 2 的幂。 每次扩容时都是变成原来的 2 倍。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的负载因子是 0.75f， 16*0.75=12。即默认的 HashMap 实例在插入第 13 个数据时，会扩容为 32。

The bin count threshold for using a tree rather than list for a bin. Bins are converted to trees when adding an element to a bin with at least this many nodes. The value must be greater than 2 and should be at least 8 to mesh with assumptions in tree removal about conversion back to plain bins upon shrinkage.

static final int TREEIFY_THRESHOLD = 8;

注意：这是 JDK1.8 对 HashMap 的优化， 哈希碰撞后的链表上达到 8 个节点时要将链表重构为红黑树， 查询的时间复杂度变为 O(logN)。

The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two. (We also tolerate length zero in some operations to allow bootstrapping mechanics that are currently not needed.)

transient Node[] table; //HashMap 的桶， 如果没有哈希碰撞， HashMap 就是个数组，我说的是如果吐舌头。 数组的查询时间复杂度是 O(1)，所以 HashMap 理想时间复杂度是 O(1)；如果所有数据都在同一个下标位置， 即 N 个数据组成链表，时间复杂度为 O(n)， 所以 HashMap 的最差时间复杂度为 O(n)。如果链表达到 8 个元素时重构为红黑树，而红黑树的查询时间复杂度为 O(logN), 所以这时 HashMap 的时间复杂度为 O(logN)。

Holds cached entrySet(). Note that AbstractMap fields are used for keySet() and values().

transient Set<map.entry> entrySet; //HashMap 所有的值，因为用了 Set， 所以 HashMap 不会有 key、value 都相同的数据。</map.entry

1、 哈希碰撞的原因和解决方法：

哈希碰撞是不同的 key 值找到相同的下标， 对应 HashMap 里 hashcode 和容量的模相同。

源码 629 行 if ((p = tab[i = (n - 1) & hash]) == null)， 其中 n 是容量值， 即用哈希值和容量相与得到要保存的位置。 如果不同 Key 的(n - 1) & hash 相同， 那么要存储到同一个数组下标位置， 这个现象就叫哈希碰撞。

 1final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { 2      if ((p = tab[i = (n - 1) & hash]) == null)     //如果该下标没值，则存储到该下标位置 3             tab[i] = newNode(hash, key, value, null);       4         else { 5             Node<K,V> e; K k; 6             if (p.hash == hash && 7                 ((k = p.key) == key || (key != null && key.equals(k)))) 8                 e = p;      //如果哈希值相同而且key相同， 则更新键值 9             else if (p instanceof TreeNode)10                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //如果下标数据是TreeNode类型，则将新数据添加到红黑树中。11             else {12                 for (int binCount = 0; ; ++binCount) {13                     if ((e = p.next) == null) {14                         p.next = newNode(hash, key, value, null);   //将新Node添加到链表末尾15                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st16                             treeifyBin(tab, hash);    //如果链表个数达到8个时，将链表修改为红黑树结构17                         break;18                     }     19           //省略若干行代码          20 }

2、JDK1.8 对 HashMap 最大的优化是 resize 函数， 在扩容时不再需要 rehash 了， 下面就看看大师是怎么实现的。

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

初始化数组或者扩容为 2 倍， 初值为空时，则根据初始容量开辟空间来创建数组。否则， 因为我们使用 2 的幂定义数组大小，数据要么待在原来的下标， 或者移动到新数组的高位下标。 （举例： 初始数组是 16 个，假如有 2 个数据存储在下标为 1 的位置， 扩容后这 2 个数据可以存在下标为 1 或者 16+1 的位置）

 1final Node<K,V>[] resize() { 2   newThr = oldThr << 1; // double threshold,   大小扩大为2倍，出于性能考虑和者告诉使用者它是2的幂， 这里用的是位移， 而不是*2， 3   if (e.next == null) 4      newTab[e.hash & (newCap - 1)] = e;  //如果该下标只有一个数据，则散列到当前位置或者高位对应位置（以第一次resize为例，原来在第4个位置，resize后会存储到第4个或者第4+16个位置） 5  else if (e instanceof TreeNode) 6     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  //红黑树重构 7  else { 8     do { 9        next = e.next;10        if ((e.hash & oldCap) == 0) {    11            if (loTail == null)12               loHead = e;13            else14            loTail.next = e;15            loTail = e;16        } else {17            if (hiTail == null)18               hiHead = e;19            else20               hiTail.next = e;21               hiTail = e;22         }23      } while ((e = next) != null);24      if (loTail != null) {25          loTail.next = null;26          newTab[j] = loHead;   //下标不变27      }28      if (hiTail != null) {29          hiTail.next = null;30          newTab[j + oldCap] = hiHead; //下标位置移动原来容量大小31      }

(e.hash & oldCap) == 0 写的很赞！！！ 它将原来的链表数据散列到 2 个下标位置， 概率是当前位置 50%，高位位置 50%。 你可能有点懵比， 下面举例说明。 上边图中第 0 个下标有 496 和 896， 假设它俩的 hashcode(int 型，占 4 个字节)是

resize 前：

496 的 hashcode: 00000000 00000000 00000000 00000000

896 的 hashcode: 01010000 01100000 10000000 00100000

oldCap 是 16: ###00000000 00000000 00000000 00010000

496 和 896 对应的 e.hash & oldCap 的值为 0， 即下标都是第 0 个。

resize 后：

496 的 hashcode: 00000000 00000000 00000000 00000000

896 的 hashcode: 01010000 01100000 10000000 00100000

oldCap 是 32: ###00000000 00000000 00000000 00100000

496 和 896 对应的****的值为 0 和 1， 即下标都是第 0 个和第 16 个。

看明白了吗？ 因为 hashcode 的第 n 位是 0/1 的概率相同， 理论上链表的数据会均匀分布到当前下标或高位数组对应下标。

回顾 JDK1.7 的 HashMap，在扩容时会 rehash 即每个 entry 的位置都要再计算一遍， 性能不好呀， 所以 JDK1.8 做了这个优化。

再回到文章最开始的问题， HashMap 为什么用 &得到下标，而不是 %？ 如果使用了取模 %， 那么在容量变为 2 倍时， 需要 rehash 确定每个链表元素的位置。

作者介绍：

高瑞，贝壳找房 Android 工程师，目前负责贝壳找房 app 安卓端研发工作。

本文转载自公众号贝壳产品技术（ID：gh_9afeb423f390）。

原文链接：

https://mp.weixin.qq.com/s/3iAVIzr2IS5ytDEjTVKoWA