HashMap源码解析！

HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树。

其中当链表的长度大于等于 8 时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表。

常见属性

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
//初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//桶上的链表长度大于等于8时，链表转化成红黑树
static final int TREEIFY_THRESHOLD = 8;

//桶上的红黑树大小小于等于6时，红黑树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;

//当数组容量大于 64 时，链表才会转化成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;

//记录迭代过程中 HashMap 结构是否发生变化，如果有变化，迭代时会 fail-fast
transient int modCount;

//HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)
transient int size;

//存放数据的数组
transient Node<K,V>[] table;

// 扩容的门槛，有两种情况
// 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方，比如你给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方。
// 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75
int threshold;

//链表的节点
static class Node<K,V> implements Map.Entry<K,V> {

//红黑树的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {

新增

1、空数组有无初始化，没有的话初始化。

2、如果通过 key 的 hash 能够直接找到值，跳转到 6，否则到 3。

3、如果 hash 冲突，两种解决方案：链表 or 红黑树。

4、如果是链表，递归循环，把新元素追加到队尾。

5、如果是红黑树，调用红黑树新增的方法。

6、通过 2、4、5 将新元素追加成功，再根据 onlyIfAbsent 判断是否需要覆盖。

7、判断是否需要扩容，需要扩容进行扩容，结束。

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
64
// 入参 hash：通过 hash 算法计算出来的值。
// 入参 onlyIfAbsent：false 表示即使 key 已经存在了，仍然会用新值覆盖原来的值，默认为 false
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // n 表示数组的长度，i 为数组索引下标，p 为 i 下标位置的 Node 值
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果数组为空，使用 resize 方法初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果当前索引位置是空的，直接生成新的节点在当前索引位置上
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果当前索引位置有值的处理方法，即我们常说的如何解决 hash 冲突
    else {
        // e 当前节点的临时变量
        Node<K,V> e; K k;
        // 如果 key 的 hash 和值都相等，直接把当前下标位置的 Node 值赋值给临时变量
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果是红黑树，使用红黑树的方式新增
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 是个链表，把新节点放到链表的尾端
        else {
            // 自旋
            for (int binCount = 0; ; ++binCount) {
                // e = p.next 表示从头开始，遍历链表
                // p.next == null 表明 p 是链表的尾节点
                if ((e = p.next) == null) {
                    // 把新节点放到链表的尾部 
                    p.next = newNode(hash, key, value, null);
                    // 当链表的长度大于等于 8 时，链表转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 链表遍历过程中，发现有元素和新增的元素相等，结束循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //更改循环的当前元素，使 p 在遍历过程中，一直往后移动。
                p = e;
            }
        }
        // 说明新节点的新增位置已经找到了
        if (e != null) {
            V oldValue = e.value;
            // 当 onlyIfAbsent 为 false 时，才会覆盖值 
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 返回老值
            return oldValue;
        }
    }
    // 记录 HashMap 的数据结构发生了变化
    ++modCount;
    //如果 HashMap 的实际大小大于扩容的门槛，开始扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

链表的新增

当链表长度大于等于 8 时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin。

此方法有一个判断，当链表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树。

  • 当数组大小小于 64 时，只会触发扩容，不会转化成红黑树。

JDK1.7中链表插入采用的是头插法，JDK1.8中插入使用的是尾插法。

  • 头插法：扩容时，扩容的逻辑会导致节点互相引用，导致死循环。

为什么是8？

链表查询的时间复杂度是 O(n)，红黑树的查询复杂度是 O(log(n))。

在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树。

但红黑树需要的占用空间是链表的 2 倍，考虑到转化时间和空间损耗。

在考虑设计 8 这个值的时候，参考了泊松分布概率函数，由泊松分布中得出结论，链表各个长度的命中概率为：

1
2
3
4
5
6
7
8
9
* 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

当链表的长度是 8 的时候，出现的概率是 0.00000006，不到千万分之一。

所以说正常情况下，链表的长度不可能到达 8 ，而一旦到达 8 时，肯定是 hash 算法出了问题。

所以在这种情况下，为了让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树。

红黑树新增节点过程

1、首先判断新增的节点在红黑树上是不是已经存在：

  • 如果节点没有实现 Comparable 接口，使用 equals 进行判断。

  • 如果节点自己实现了 Comparable 接口，使用 compareTo 进行判断。

2、新增的节点如果已经在红黑树上，直接返回。

  • 不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大。

3、自旋递归 1 和 2 步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点。

4、把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系。

5、进行着色和旋转，结束。

扩容机制

扩容阈值:

  • 阈值 = 容量 x 负载因子，假设当前 HashMap的容量是 16，负载因子是默认值 0.75。
  • 当 size 到达 16 x 0.75= 12 的时候，就会触发扩容。

查找

根据 hash 算法定位数组的索引位置，equals 判断当前节点是否是我们需要寻找的 key，是的话直接返回，不是的话往下。

判断当前节点有无 next 节点，有的话判断是链表类型，还是红黑树类型。

分别走链表和红黑树不同类型的查找方法。

1
2
3
4
5
6
7
8
9
// 采用自旋方式从链表中查找 key，e 初始为为链表的头节点
do {
    // 如果当前节点 hash 等于 key 的 hash，并且 equals 相等，当前节点就是我们要找的节点
    // 当 hash 冲突时，同一个 hash 值上是一个链表的时候，我们是通过 equals 方法来比较 key 是否相等的
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
    // 否则，把当前节点的下一个节点拿出来继续寻找
} while ((e = e.next) != null);

HashMap为什么是线程不安全的

同时 put 碰撞导致数据丢失。

  • 多个线程同时使用 put 来添加元素，而且两个 put 的 key 是一样的，它们发生了碰撞，这样最终就只会保留一个数据。

可见性问题无法保证。

  • 如果线程 1 给某个 key 放入了一个新值，那么线程 2 在获取对应的 key 的值的时候，它的可见性是无法保证的。

死循环造成 CPU 100%：

  • 扩容的时候，会反转散列桶中的节点顺序。
  • 当有多个线程同时进行扩容的时候，如果两个线程同时反转的话，便可能形成一个循环。