Java - HashMap原理分析

前言

HashMap一直是我们老生常谈的东西了，它可以说是Java里面最常用的一种集合了。虽然这块的内容比较基础，我也看过很多博主的文章，只不过这次，我希望能自己整理一下，并分享给各位读者。

我相信，这种学习方式是非常有用的：

• 第一遍：从别人那学习。
• 第二遍：自己整理一遍。
• 第三遍：将心得分享一遍。例如写成文章。

一. HashMap的结构

对于HashMap的结构而言，我们的刻板印象都是：数组+链表+红黑树，如图：

上图中红色框中所示的就是一个单向链表，每一个节点就是一个Node。它存储着我们往HashMap中塞入的具体的值和相关属性。HashMap类中，就有这么一个静态内部类Node，我们来看下它的结构组成：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;// 当前插入的键的hash值
    final K key;// 对应的键
    V value;// 对应的value
    Node<K,V> next;// 因为是单链表，因此每个Node节点都有一个指向下一个节点的指针next
    // ... 省略
}
1
2
3
4
5
6
7

那么，为什么HashMap要使用数组+链表的形式呢？（红黑树在后面再说）这就引申了两个问题：

• 哈希冲突。
• 数组和哈希表的优劣势。

我们一个个来说。

1.1 数组和哈希表的优劣势

从内存的分配来看：

• 数组： 元素的保存在一块连续的内存地址上。有着一定的顺序。
• 哈希表：由于是根据元素的Key来计算对应的哈希值，因此无法按照顺序来遍历元素。空间利用率比较低。

元素访问上：

• 数组：可以通过下标来访问元素，元素查找比较慢。对于插入/删除动作，还需要去维护数组的索引。需要占用一定的资源。
• 哈希表：元素的访问、插入、删除速度都很快。都是O(1)操作。

HashMap中就采取了哈希表（散列表）来存储元素，而其具体的展示形式就是上文提到的：数组+链表。

对于散列表而言，一个数组中的每个位置都相当于一个桶，即哈希桶。用于存放插入的元素，插入的步骤大致分为两步：

1. 计算这个元素的哈希值：hash(key)。
2. 根据这个元素的哈希值，计算出该元素应该放到哪个桶下：index(hash, N+1)

那么随着元素的数量越来越多，可能会发生哈希冲突。

1.2 哈希冲突

哈希冲突即：

1. 两个元素完全不一样，比如：key和value都不同。
2. 但是经过某种哈希算法得出的key的哈希值却是一样的。
3. 那么他们将会被放入到同一个哈希桶中。也就是所谓的哈希冲突。

那么当元素数量越来越多的时候，不可避免的会发生不同key但相同哈希值的情况，因此引入链表结构，每个哈希桶对应一条链表：同一个哈希桶中的所有元素则根据链表的形式来连接。因此这条链表也叫做哈希冲突链。

我们再来从HashMap的源码角度来看这个问题：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
	transient Node<K,V>[] table;
}
1
2
3

这个table就对应着所谓的哈希桶数组，每个桶中就是一个链表，也就是Node对象。上文也提到过，Node里面有着next指针，因此他可以作为链表来使用。

1.3 生日悖论

假设HashMap中的table数组，长度只有2，并且有一个桶中已经有一个元素了。那么在插入下一条元素的时候，发生哈希碰撞（哈希冲突）的概率就是50%。那么问题来了：table数组长度越长，发生哈希碰撞的概率是不是就越低了呢？

其实并不是这样的，这里用一个悖论来解释这个问题：生日悖论。

生日悖论是指在不少于 23 个人中至少有两人生日相同的概率大于 50%

这个看起来非常的荒谬，几乎不可能，一年365天呢，这概率怎么来的？但是你看下面的分析你就会知道，为什么它叫做悖论了。

1. 一年365天，那么第一个人和其他人生日不同的概率是：365/365。
2. 第二个人和其他人生日不同的概率是：365/365 * 364/365。因为此时第一个人的生日已知了。
3. 第三个人和其他人生日不同的概率是：365/365 * 364/365 * 363/365。因为此时第一、第二个人的生日已知了。
4. 以此类推：当我们计算到第23个人的时候：
   
5. 这个概率，是23个人生日不同的概率，那么23个人生日可能发生相同的概率就是1 - 0.49=0.51

再说下为什么从365/365开始算。我个人认为，这是因为这里的概率指的是：n个人中，生日不相同的概率。那么只有1个人的时候，这个人没有可比较的对象，那么他和其他人（0人）生日不同的概率就是1了。

到这里为止有点扯远了，回到本小节的重点：从生日悖论角度来说，我们可以知道，通过扩大哈希桶数组长度来降低哈希碰撞的概率，这种做法是没有意义的。也因此，用链表来将冲突的元素来连接起来。

1.4 HashMap 中的几个重要成员变量

// 默认初始化容量为16，默认的初始容量必须是2的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 默认的一个加载因子，可以理解为超过 容量 * 因子 大小的元素数量时，就发生扩容。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转化为红黑树的元素阈值。当至少有这么多时链表转换为树。该值必须大于2，并且应该至少为8。
static final int TREEIFY_THRESHOLD = 8;
// 默认值64，对于这个值可以理解为：如果元素数组长度小于这个值，没有必要去进行结构转换。即转化为红黑树也不是随随便便就执行的
static final int MIN_TREEIFY_CAPACITY = 64;
// 在扩容的时候，对红黑树进行拆分，如果拆分后的子树节点数<=6，就放弃树化，转为链表结构。
static final int UNTREEIFY_THRESHOLD = 6;
1
2
3
4
5
6
7
8
9
10

二. HashMap的插入流程

我们来看下源码：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
           boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1.添加元素之前，先判断当前哈希桶数组的大小，是否是null或者空
    if ((tab = table) == null || (n = tab.length) == 0)
    	// 如果是，那么需要将数组扩容，这样才能存储元素呀。
        n = (tab = resize()).length;
    // 2. (n - 1) & hash ：计算这个key对应的哈希桶下标
    // 若此时对应的哈希桶中没有存储任何元素，即为null，就是没有发生碰撞，直接创建一个新的Node链表即可。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
    	// 3.否则发生碰撞
        Node<K,V> e; K k;
        // 如果当前位置的数据，即链表的首节点，就是要找的，那么进行值的替换，
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果key不一样，那么就需要进行判断，判断当前节点是否是红黑树结构
        else if (p instanceof TreeNode)
        	// 如果是，那么就需要根据红黑树的逻辑来添加一个新节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        	// 如果不是红黑树，那么就是链表，遍历整个哈希冲突链，看看是否有重复的key
            for (int binCount = 0; ; ++binCount) {
            	// 如果没有找到重复的，就在链表的末尾添加一个新元素
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 插入完成之后，再判断是否需要转化为红黑树，即链表长度是否超过阈值
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果找到了重复的key，就替换数据
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果找到的节点不是null，就将旧值替换为新值
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 插入完成之后，增加元素数量。判断是否需要扩容。
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

其中我们关注下转化为红黑树的代码。

2.1 转化为红黑树 treeifyBin

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果数组为null，或者数组长度小于默认的64。优先扩容，而不是进行链表转化为红黑树的操作。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 否则，此时应该进行链表结构的转换，根据hash值和数组长度进行取模运算后，得到链表的首节点
    else if ((e = tab[index = (n - 1) & hash]) != null) {
    	// 定义首、尾节点
        TreeNode<K,V> hd = null, tl = null;
        // 总的操作就是将单Node对象转化为TreeNode对象
        // 向单向链表转化为双向链表
        do {
        	// 将当前节点转换为树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // 如果尾节点为空，说明还没有根节点
            if (tl == null)
            	// 首节点（根节点）指向当前节点
                hd = p;
            else {
            	// 否则，尾节点不为空，当前节点的前一个节点指向尾节点
                p.prev = tl;
                // 尾结点的后继节点指向当前节点。
                tl.next = p;
            }
            // 当前节点指向尾结点
            tl = p;
        } while ((e = e.next) != null);
        // 将转换后的双向链表替换原本位置的单向链表
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

这里可以做个总结，转化为红黑树的主要操作就是：

1. 将Node节点转化为TreeNode节点。
2. 将单向链表转化为双向链表。

2.2 扩容操作 resize

首先要对源码中的几个变量做出解释：

• oldTab：扩容前的，原Node数组。
• oldThr：扩容前的，原扩容阀值。
• oldCap：扩容前的，原数组的长度。
• newTab：扩容后的，新数组。
• newThr：扩容后的，新扩容阀值。
• newCap：扩容后的，新数组的长度。

我们来分析下源码：主要分为两个部分：

• 对扩容后的数组相关的参数进行计算：阈值、容量。
• 扩容操作。

2.2.1 计算部分

final Node<K,V>[] resize() {
	// 初始化扩容前的数组变量、以及扩容前的阈值、数组长度。
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // threshold是用户在初始化Map的时候，传入的容量参数。默认是0
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果原数组长度>0
    if (oldCap > 0) {
    	// 判定Node数组是否已达到极限大小，如果超过极限，直接将原Node数组返回。即2的30次方。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 否则，看新数组长度（扩容是2倍）是否超过了极限，并且原数组长度需要 >=数组初始化的大小
        // DEFAULT_INITIAL_CAPACITY:1 << 4,即16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 如果满足条件，可以扩容2倍。
            newThr = oldThr << 1; 
    }
    // 如果初始化的时候用户传入了容量参数，将其复制给newCap参数
    else if (oldThr > 0) 
        newCap = oldThr;
    else { 
    	// 如果初始化的时候，什么参数都没有，那么新的容量和阈值，都用默认值。              
        newCap = DEFAULT_INITIAL_CAPACITY;// 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 16 * 0.75
    }
    // 如果初始化的时候用户传入了容量参数和负载因子或者只传入了容量参数
    if (newThr == 0) {
    	// 将用户传入的容量参数 * 用户传入的负载因子 作为loadFactor
        float ft = (float)newCap * loadFactor;
        // 将计算结果赋值给newThr，即新的扩容阀值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // ...第二部分
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    return newTab;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

总结下就是：

1. 初始化了新数组的容量、阈值等必要属性。
2. 根据初始化的阈值和容量，创建出一个新数组。

2.2.2 扩容部分

final Node<K,V>[] resize() {
	// ...第一部分
    table = newTab;
    // 如果原数组不是null
    if (oldTab != null) {
    	// 那么遍历数组元素，即哈希桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果当前元素的后继节点是null，说明当前元素没有新节点也没有新的树节点TreeNode
                if (e.next == null)
                	// 则将该Node元素直接存于新Node数组的指定位置
                    newTab[e.hash & (newCap - 1)] = e;
                // 否则如果该Node节点是一个红黑树
                else if (e instanceof TreeNode)
                	// 那么在新的Node数组中，将该红黑树进行拆分
                	// 并且如果拆分后的子树太小了，节点数<=6的话，就转化为链表，取消红黑树结构
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 如果是链表的情况下，则进行下面的链表数据转移的操作
                else { 
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 对链表进行遍历，因为新数组中对于元素的存储而言，可能有两种情况
                    // 一种是该元素不需要移动到其他的哈希桶中。即下标不变，一种是下标发生改变
                    do {
                        next = e.next;
                        // 如果下标不需要改变
                        if ((e.hash & oldCap) == 0) {
                        	// 说明该链表没有头节点，即哈希桶为null，那么把当前节点作为链表的头节点。
                            if (loTail == null)
                                loHead = e;
                            else
                            	// 否则将新节点放在该链表的底部
                                loTail.next = e;
                            loTail = e;
                        }
                        // 如果下标需要改变，后续逻辑就和上面一样
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 该Node节点所对应的数组下标不需要改变，直接把数组下标对应的节点指向新Node数组下标位置链表的头节点
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 该Node节点所对应的数组下标需要改变，重新计算出所对应的数组下标值，然后指向新Node数组下标位置链表的头节点
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

总结下就是：

1. 只有原数组不是空的情况下，才会进行扩容操作。
2. 如果遍历的元素Node没有后继节点，那么直接将该元素存放于新数组的指定位置即可。
3. 如果当前元素后面跟着一个红黑树结构，那么在新数组中，还需要对红黑树进行拆分。当然，如果拆分后的子树太小了，节点数量<=6个的话，就会取消红黑树，转化为链表结构。
4. 如果当前元素后面跟着一个链表的话，就对链表进行遍历。对每个Node进行重新计算，然后迁移到对应的新数组中。这个过程会重新计算hash值。

2.2.3 JDK1.8的优化

我们知道JDK1.7在高并发的情况下扩容容易造成链表成环，从而死循环。原因是因为头插法。而JDK1.8中，则对这个问题进行了修改，即尾插法。我们来根据上述代码来讲解下。

首先是JDK1.7：我们贴出扩容中的一段关键代码：

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

下面这段代码就是重点，也就是头插法：同一个位置的新元素，总是会放到链表的头部位置。

e.next = newTable[i];
newTable[i] = e;
e = next;
1
2
3

这里我拿别人的图来演示下大概流程：

1.假设线程A进行扩容的时候被挂起，线程B开始扩容，原数组大小只有2：

2.此时扩容完毕：nodeA和nodeB的引用方向可能转换了。重新hash计算后，两个Node节点依旧在同一个哈希桶下。

3.此时线程A结束挂起状态，继续扩容，遍历的时候发现：nodeB的next已经被线程B在扩容时改成了nodeA。就发生了环。

而在JDK1.8中，是尾插法。即新元素总会插入到链表的尾部，原本是什么顺序，后面也是什么顺序（前提在resize后，两个Node节点依旧在同一个桶中） 相关代码我截个图：

因此也避免的头插法在高并发情况下容易造成死循环的问题。

2.3 总结

2.3.1 为什么加载因子是0.75？

这个问题，是一个概率问题。首先我们知道的是：

• 加载因子越大：填满的元素越多，空间利用率越高，但发生冲突的概率也就越高。
• 加载因子越小：填满的元素也就越少，空间利用率降低，但是发生冲突的概率也就越低。但是会提高resize的次数。

这里做个总结（对于0.75的选择不要深挖）：

1. 首先选择0.75完全是时间和空间成本上寻求的一种折衷选择。
2. 其次0.75是根据泊松分布公式的一个计算，算出的一个最合理的值。
   公式如下：
   

当HashMap中的哈希桶中的链表长度为8的时候，这个发生概率为0.00000006，概率非常小，附上其他长度的概率：

冲突链长度    概率
0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
1
2
3
4
5
6
7
8
9
10

因此HashMap默认使用0.75作为加载因子。

2.3.2 为什么扩容是2倍？

首先我们看下上文中关于HashMap中，定位哈希桶下标的部分代码：

if ((p = tab[i = (n - 1) & hash]) == null)
1

这里的n指的是数组的长度，hash就是当前key对应的哈希码。

---

首先我们来说下，为什么要做出(n - 1) & hash的操作呢？（实际上就是取余数）直接用哈希码不好嘛？

回答：

1. Hash值的取值范围是 -2^31 到 2^31-1。前后加起来大概40亿的映射空间。
2. 其次我们HashMap中往往用不着这么大的映射空间，同时内存还不一定满足这个条件。
3. 因此Hash值不可以直接拿来用，我们需要做取余操作。

---

其次，对于取余操作，如果除数是2的幂次则等价于 与其除数减1再进行&操作。 也就是说：

(2的幂次 - 1) & hash === hash % 2的幂次
1

除此之外，%这个运算在Java中实际上跑的时候，也是会转化为&操作来进行，位运算的效率要更高。

---

最后，扩容为2的倍数，可以降低哈希碰撞的概率。

• 如果容量是奇数，那么减1后就是偶数，对应二进制的末尾始终是0。0&n，结果都是0.当容量越大，那么大量位上的&运算的结果都是0。哈希碰撞的概率大大提升。
• 如果容量是偶数，那么减1后就是奇数，对应的二进制末尾就是1，1&n 的结果，取决于数字 n 本身。

举个例子：当HashMap的容量为16的时候（2的倍数），(n-1)对应的二进制位01111，和不同hash值计算的结果如下：4个值都不同。

当HashMap的容量为10的时候，(n-1)对应的二进制位01001，和不同hash值计算的结果如下：4个结果中，3个值相同，那么就有3个元素会放到同一个哈希桶中，哈希碰撞的概率为75%。

2.3.3 put 操作的整体流程

1. 添加元素之前，如果HashMap还没初始化，那么resize一下扩容。
2. 通过(n-1)&hash，计算出插入元素M将要插入到的哈希桶的下标Index。
3. 如果对应哈希桶中没有任何元素，那么当前元素直接插入，作为链表的头结点。
4. 否则就是产生了哈希碰撞。

如果发生哈希碰撞：

1. 若当前链表的头结点和当前插入元素的key重复了，那么直接替换。
2. 否则判断当前节点是否为红黑树结构。是的话则添加一个树节点。
3. 如果不是红黑树，那么就是链表，则遍历链表。

遍历链表的过程中：

1. 如果发现key重复，则终止遍历。在后续进行替换值操作。
2. 否则，将当前插入元素添加到链表的末尾。
3. 插入之后，还要判断是否需要转化为红黑树。

整个元素插入完毕后，再判断是否超过了规定的阈值，若超过了，则进行扩容操作。

2.3.4 HashMap相关的几个重要知识点

• HashMap默认的初始容量是16，加载因子是0.75，因此扩容的阈值是16*0.75=12，超过这个值之后，发生扩容，扩容两倍。
• 当哈希桶中的链表长度超过了8，倘若超过了8，并且HashMap中的数组长度超过了规定的64，则将链表转化为红黑树结构。若不满足数组长度，则优先扩容。
• 在扩容的时候，如果是哈希桶中的结构是红黑树，那么会对红黑树进行拆分，如果子树的元素个数<=6，则会将红黑树退化为链表。
• HashMap在JDK1.8的时候，采用尾插法，扩容的时候，新元素总是放到链表尾部，避免高并发情况下形成环（JDK1.7中采用头插法，就有这个问题）。
• HashMap中的数组长度上限是2^30。同时，并不是数组长度越大，哈希碰撞的概率就越小，可以参考生日悖论。
• 其他的几个点就是总结的前几个部分了。然后关于HashMap的get操作，其实没啥好说的，本文不赘述了。