HashMap

发表于 分类于
HashMap 源码与总结

顾名思义，HashMap 就是以 hash 值为 key 的 Map 集合

HashMap 是以 数组 作为容器的

1
transient Node<K,V>[] table;

Node 是 HashMap 内部实现了 Map.Entry 的类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    // 链表要用到
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    /**
     * 其他 balabala 鬼东西
     */
}

HashMap 就是以 hash 值为 key

put 方法：

1
2
3
4
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)

而 putVal 第一个参数就是 hash 值，再看看 hash 方法：

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

可以看到，如果 key 为 null，hash 值为 0；否则：

  • hash 值为 hashCode() 做一次 16 位右位移异或

为什么这样做，是因为 扰动函数，具体请看：知乎传送门

下面提到的 putVal 也有讲

必识的变量

biss：最讨厌看这些静态常量了，每个字母都是大写

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
65
66
67
68
69
70
71
/**
* 默认的容量
* default_initial_capacity
* 为什么是 16 ，且为什么推荐 2 的幂次方，看下面的 putVal 方法
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

/**
* 最大容量上限
* maximun_capacity
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 在构造函数中未指定时使用的负载系数
* 负载因子
* default_load_factor
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 链表转换为树的阈值，超过这个长度的链表会被转换为红黑树
* treeify_threshold
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 当进行resize操作时，小于这个长度的树会被转换为链表
* untreeify_threshold
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 链表被转换成树形的最小容量，如果没有达到这个容量只会执行 resize 进行扩容
* 应该至少为4 * treeify_threshold，以避免大小调整和树化阈值之间发生冲突
* 链表超过 8 时，且数组长度大于等于 64，转为红黑树，如果数组长度小于 64，就进行扩容
* min_treeify_capacity
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 存储元素的实体数组
 */
transient Node<K,V>[] table;

/**
 * set 数组，用于迭代元素
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 存放元素的个数，但不等于数组的长度
 */
transient int size;

/**
 * 修改的次数
 * 与快速失败有关
 */
transient int modCount;

/**
 * 临界值  如果实际大小超过临界值，就会进行扩容
 * threshold = 负载因子 * 容量
 */
int threshold;

/**
 * 加载因子、负载因子
 */
final float loadFactor;

resize

resize 方法不仅用来调整大小，还用来进行 初始化 配置：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 如果已经初始化
    if (oldCap > 0) {
        // 如果目前 table 的容量大于最大容量的上限，则不会进行扩容，并设置临界值为最大
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 先对容量进行两倍扩容
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 如果扩大两倍没超过上限，并且原来的容量大于等于16( DEFAULT_INITIAL_CAPACITY 16 )
            // 就会对临界值( threshold )也进行两倍扩容
            newThr = oldThr << 1; // double threshold
    }
    
   
    // 如果没有初始化
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 这个分支针对的指定初始化容量的构造方法
        newCap = oldThr;
    else {
        // 这个分支是针对默认构造函数的分支，对 newCap 和 newThr 进行赋值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 临界值 = 容量 * 负载因子
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 设置 threshold
    threshold = newThr;
    
    // 新数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    
    
    
    // 扩容完毕，需要把原来的元素逐一拷贝到新数组中去
    if (oldTab != null) {
        // 遍历原数组的元素
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //将原来的置为 null，方便垃圾回收器进行回收
                oldTab[j] = null;
                // 如果e.next为null，表示此链表是单节点
                // 直接根据 e.hash & (newCap - 1) 得到新的位置进行赋值即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 如果是红黑树节点，则调用红黑树的方法
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // 链表的复制
                    // 确定链表里面的元素在数组中的位置
                    // 元素有些不动，有些动
                    // 动的不是根据 hash 算法生成新的位置
                    // 而是采用 原始位置 + 原始容量 得到 新的位置
                    
                    // 表示一条链表，该链表在新数组中的下标不变
                    Node<K,V> loHead = null, loTail = null;
                    // 表示一条链表，该链表在新数组中的下标比原来增加 oldCap
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 判断：元素的在数组中的位置是否需要移动
                        // (e.hash & oldCap)结果为 0 就代表没有变化，否则就是有变化( 看下面 )
                        
                        // 这些是在新数组中位置不变的节点
                        if ((e.hash & oldCap) == 0) {
                            // 将符合条件的元素进行新的链表拼接
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 这些是在新数组中位置 = 原位置 + oldCap 的节点
                        else {
                            // 和上面同理
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                        // 只要链表元素有下一个元素就循环进行拼接
                    } while ((e = next) != null);
                    // 添加到新数组
                    // 位置不变
                    if (loTail != null) {
                        // 将链表的尾部的 next 置为空
                        loTail.next = null;
                        // 直接将这个链插到新数组
                        newTab[j] = loHead;
                    }
                    // 位置 + oldCap
                    if (hiTail != null) {
                        // 将链表的尾部的 next 置为空
                        hiTail.next = null;
                        // + 原始容量
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容后链表元素的位置

直接判断 (e.hash & oldCap) ，结果为 0 就代表与之前的位置相比 没有变化，否则就是有变化

为什么要这样来决定？

我们知道( 如果不知道，看下面的 putVal )，(n - 1) & hash 是元素在数组的位置( n 是容量大小 )

假设 oldCap 为 16，也就是 2^4

n - 1 = 15，即 0000 0000 …… 1111

而 & hash 就是取 hash 的低 4 位，设为 xxxx

此时数组扩容是2倍，也就是 2 * oldCap = 32 = 2^5，& hash 后就是取 hash 的低 5 位

对于低 5 位，对于同一个元素，无非就是

  • 1xxxx
  • 0xxxx

0xxxx 和 没扩容前的低 4 位一样

1xxxx = 原来的低 4 位 + oldCap

但是怎么才能知道是 0 还是 1？

直接 (e.hash & oldCap) 即 hash & 0000 0000 …… 1 0000 不就行了！！

如果 (e.hash & oldCap) = 0 那就是说元素在新数组的位置还是之前的，不变；

如果 (e.hash & oldCap) = 1 那就是说元素在新数组的位置 = 原来的位置 + oldCap

参考文章

putVal

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// 参数 onlyIfAbsent 表示是否替换原值
// true: 不替换，false: 替换
// 参数 evict 我们可以忽略它，它主要用来区别通过 put 添加还是创建时初始化数据的
// 如果为 false，该 table 处于创建阶段
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果 table 数组为空 或 长度为 0，则对其进行初始化，分配内存空间
    if ((tab = table) == null || (n = tab.length) == 0)
        // resize()不仅用来调整大小，还用来进行初始化配置
        // 这里就用到 resize 初始化
        n = (tab = resize()).length;
    
    // 当 put 的 key 在数组中不存在时，直接 new 一个 Node 元素放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        // (n - 1) & hash 就是把 hash & ( 数组长度 - 1 )
        // 为什么要 n - 1 呢，这里正好解释了为什么 HashMap 的数组长度要取 2 的整次幂
        
        // n - 1 正好相对于做了一个"低位掩码"
        // & 操作的结果就是散列值的高位全部归零
        // 只保留低位值，用来做数组下标访问
        
        // 以初始长度 16 为例，16 - 1 = 15
        // 二进制就是 0000 …… 1111
        // 和 hash & 后，就是取低 4 位
        //   0000 0000 0000 0000 0000 1111
        // & 0000 0001 0100 1010 1010 0101
        // = 0000 0000 0000 0000 0000 0101 高位归零，只保留末四位
        
        // 但是只取末四位碰撞也很严重
        // 所有就有了 hash(Object key) 这个扰动函数，putVal 的参数 hash 要先搞扰动
        // 再进来 hash(Object key)
        // hashCode() 获取哈希值 h，然后 h >>> 16，右位移 16 位，正好是 32 位一半
        // 然后把自己的高半区和低半区异或(^)
        // ( 为了加大低位的随机性，而且混合后低位掺杂了高位的部分特征，这样高位的信息变相保留了下来 )
           
            
        // 简单版
        // 先通过 hashcode 拿到最初的 hash 值，也就是 32 位的内存地址
        // 然后高 16 位右移和原来的 hash 异或( 两个不同就为真 )
        // 这时候低 16 位就保留了高低位的信息
        // 然后再和( 数组大小 - 1 )与( & )，拿到低位
        // 而数组大小建议是 2 的幂次方，这样减 1 后低位就是 000...1111，和已经扰动的 hash 值与( & )一下就拿到低位
        // 这样这个低位就有很大的随机性，这个低位来充当数组下标，能更有效的避免哈希碰撞

        // 这里就是看下在 hash 位置有没有元素，实际位置是 hash % (length - 1)
        // 将元素直接插进去
        tab[i] = newNode(hash, key, value, null);
    else { // 如果元素在集合中已存在
        // 这时就需要链表或红黑树了
        // e 是用来查看是不是待插入的元素已经有了，有就替换
        Node<K,V> e; K k;
        // p 是存储在当前位置的元素
        // 如果 tab[(n - 1) & hash] 位置的第一个元素的 key 和要保存的 key 相等
        // 这说明目的是修改值
        // 将 p 的值赋给 e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果是红黑树节点，则调用其put方法
        else if (p instanceof TreeNode)
            // 把节点添加到树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 不是替换第一个节点，也不是红黑树节点，那就是链表了
        // 循环每一个元素
        else {
            // 这时候就是链表结构了，使用尾插法!!!
            for (int binCount = 0; ; ++binCount) {
                // 如果找找找，也没有找到一样的 key，且 p 没有下一个了
                // 就直接 new
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果超过树的阈值，就要变成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 由于初始即为 p.next，所以当插入第 8 个元素才会树化
                        // -1 for 1st 如果链表的长度超过 8，则进行红黑树进行转换。
                        // 1.8后追加：链表查询的复杂度是 O(n)，而红黑树是 O(log(n))，
                        // 但是如果 hash 不均匀会极大的影响性能
                        // 此方法里面会判断，如果数组长度大于等于 64，转为红黑树，
                        // 如果数组长度小于 64，就进行扩容 resize
                        treeifyBin(tab, hash); 
                    break;
                }
                // 找到了对应元素，就可以停止了
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    //此时 e 就是找到的相同 key 的，要替换的节点
                    break;
                // 继续向后循环
                p = e;
            }
        }
        // 此时 e 就是找到的相同 key 的，要替换的节点
        if (e != null) {
            // 原值
            V oldValue = e.value;
            // 如果 onlyIfAbsent 为 false，或者原值为 null，就是要替换
            if (!onlyIfAbsent || oldValue == null)
                // 改
                e.value = value;
            // afterNodeAccess 默认为空实现，允许我们修改完成后做一些操作
            // 它由 LinkedHashMap 的实现，并调用
            afterNodeAccess(e);
            // 返回，这里是返回已经更新的值，这是引用
            return oldValue;
        }
    }
    // 操作数 + 1
    ++modCount;
    // 如果 size 大于扩容阀值 threshold，则进行扩容操作
    if (++size > threshold)
        resize();
    // 由 LinkedHashMap 的实现，并调用
    // 作用：在执行一次插入操作都会执行的操作
    // 主要就是对 LRU 算法的支持
    // 是否移动最早的元素。、但是 LinkedHashMap 中总是返回 false，所以在这里没什么用
    // 回调移除最早放入 Map 的对象
    // 默认也是空实现，允许我们插入完成后做一些操作
    afterNodeInsertion(evict);
    return null;
}

尾插法

1.8 之前插入元素是使用头插法，可能觉得新来的被访问的可能性高

但是 1.8 之后却使用尾插法

简单来说：头插法，多线程 插入时，会在扩容的时候造成 Infinite Loop ，即 A 指向 B，B 指向 A

具体是为什么请看：参考文章

总结

首先 HashMap 是实现了 Map 接口的，所以是它的每个元素都是以键值对的形式存放

而这个键值对 是实现了 Map 接口定义的 Node 类，它的成员变量有 hash、key、value，还有下一个节点 next

而存放这些键值对元素的底层就是 Node 数组

当第一次发生插入时，首先是初始化，即使用 resize 方法

插入

1、下标

而插入的时候，数组下标是 key 的 hash 值 & ( 数组长度 - 1 )

这个 hash 值是经过扰动得来的，先通过 hashcode 拿到最初的 hash 值，也就是 32 位的内存地址

然后高 16 位右移和原来的 hash 异或^( 两个不同就为真 )

这时候低 16 位就保留了高低位的信息

然后再和( 数组大小 - 1 )与( & )，拿到低位作为数组下标

而数组大小建议是 2 的幂次方，这样减 1 后低位就是 000…1111，和已经扰动的 hash 值与( & )一下就拿到低位

这样这个低位就有很大的随机性，这个低位来充当数组下标，能更有效的避免哈希碰撞

2、插入

如果这个下标没有元素，就直接赋值

如果有元素

  • 且 key 相同而且 hash 相同，就替换嘛

  • 如果 key 不同或者 hash 不同，那就类型判断( instanceof )，看看原来这个位置的节点是不是红黑树( TreeNode )

    • 如果是红黑树就执行红黑树的插入
    • 如果不是，那就是执行链表的插入
      • 如果 next 为空，直接new节点( newNode方法 )，尾插法( jdk 1.8 )
        • 而且它有一个计数的变量( binCount )，如果个数超过了设置的红黑树阈值( TREEIFY_THRESHOLD )( 默认 8 )，就执行链表转红黑树方法( treeifyBin )
      • 如果 next 不为空
        • 但 key 不同或者 hash 不同，就继续迭代链表
        • 且 hash 相同，key 也相同，这时候就看 put 方法的参数有没有说如果遇到 key 和 hash 一样的，是否要保留原值，再进行操作

插入结束后，会自增 map 的 size，如果实际大小超过临界值( threshold )，就会进行扩容( threshold = 负载因子 * 容量 )，执行 resize 方法

3、尾插法

1.8 之前插入元素是使用头插法，可能觉得新来的被访问的可能性高。

但是1.8 及以后却使用尾插法。

简单来说：头插法，多线程 插入时，会在扩容的时候造成 Infinite Loop( 无限循环、死循环 ) ，形成 环形链表，即 A 指向 B，B 指向 A

扩容或初始化

1、初始化

如果是第一次插入，那么需要进行初始化，而初始化是在 resize 方法里面

在 resize 方法里面，因为 HashMap new 的时候只是初始化了负载因子，是 0.75f，而 resize 方法会对容量和临界值( threshold )赋值

如果在构造函数里已经有具体的容量参数，就直接用

如果没有，就用默认的

2、扩容

如果已经初始化

如果目前现在的的容量大于最大容量的上限( MAXIMUM_CAPACITY )，则不会进行扩容，并且设置临界值( threshold )为最大( Integer.MAX_VALUE )

如果现在的容量没到达上限，就会对容量进行 两倍扩容( << 1 )

  • 而且再扩大两倍还没超过上限，并且原来的容量大于默认的容量( DEFAULT_INITIAL_CAPACITY 16 )
    • 就会对临界值( threshold )也进行 两倍扩容( << 1 )

完成后，再进行元素的重新放置

它会开一个新容量的数组，按照老数组的下标来遍历，把元素都拷进去

  • 如果元素 next 为 null，表示此元素是单个的，直接根据 hash & ( 容量 - 1 ) 得到新的位置进行赋值
  • 如果元素 next 不为 null，再判断是不是红黑树节点
    • 如果是，就按红黑树转
    • 如果不是，那就是链表了
      • 新的链表头的下标不是根据 hash & ( 容量 - 1 ) 得到新的位置
      • 而是根据判断( e.hash & oldCap )是不是等于 0，来决定是 采用( 原始位置 + 原始容量 )得到 新的位置，还是位置不变
        • 它会维护两个链表，一个存着位置不变的元素链，一个存着位置为( 原始位置 + 原始容量 )的元素链
        • 至于为什么根据( e.hash & oldCap )来判断

其他常用的易忘的

1
2
3
4
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}