7.Java SDK源码分析系列笔记-JDK1.8 HashMap

目录

• 1. 是什么
  
• 2. 如何使用
  
• 3. 原理分析
  
  
  
  • 3.1. uml
    
  • 3.2. 构造方法
    
  • 3.3. put方法
    
    
    
    • 3.3.1. 计算key的hash值
      
    • 3.3.2. 第一次进来table肯定为空，那么扩容
      
    • 3.3.3. 使用hash值&数组长度1计算改数据存放的位置i
      
    • 3.3.4. 第二次进来如果位置i为空，那么用（key，value）存入该位置
      
    • 3.3.5. 第三次进来如果位置i不为空，那么遍历链表或红黑树找到key相等的节点替换value
      
      
      
      • 3.3.5.1. 怎么转换成红黑树的
        
        
        
        • 3.3.5.1.1. Node->TreeNode
          
        • 3.3.5.1.2. 树化
          
        
        
      
      
    
    
  • 3.4. get方法
    
    
    
    • 3.4.1. 计算key的hash值
      
    • 3.4.2. 使用hash值&数组长度-1计算改数据存放的位置i
      
    • 3.4.3. 第一个节点就是要找的节点
      
    • 3.4.4. 转调树或红黑树的查找操作找到节点
      
    • 3.4.5. 没有找到返回null
      
    
    
  • 3.5. containsKey方法
    
  • 3.6. remove方法
    
    
    
    • 3.6.1. 计算key的hash值
      
    • 3.6.2. 使用hash值&数组长度1计算改数据存放的位置i
      
    • 3.6.3. 调用链表或是红黑树的查找操作找到key相等的节点
      
    • 3.6.4. 调用链表或红黑树的删除操作
      
    
    
  • 3.7. containsValue
    
  
  
• 4. 问题
  
  
  
  • 4.1. 相对于JDK1.7的区别
    
  • 4.2. 如何解决并发resize时的死循环问题
    
  • 4.3. 什么时候扩容
    
  • 4.4. 怎么扩容的
    
  
  
• 5. 参考
  

1. 是什么

实现O(1)存取效率的key-value对数据结构
2. 如何使用

1. public class HashMapTest
2. {
3.     public static void main(String[] args)
4.     {
5.         HashMap<String, Object> map = new HashMap<>();
6.         map.put("key1", "value1");
8.         System.out.println(map.get("key1"));
9.         map.remove("key1");
11.         map.containsKey("key1");
12.     }
13. }

复制代码

3. 原理分析

3.1. uml

可克隆，可序列化，实现了Map
3.2. 构造方法

1. public class HashMap<K,V> extends AbstractMap<K,V>
2.     implements Map<K,V>, Cloneable, Serializable {
3.     //使用Node数组实现，使用链地址法解决Hash冲突
4.     transient Node<K,V>[] table;
5.     //默认的初始容量
6.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
7.     //最大容量
8.     static final int MAXIMUM_CAPACITY = 1 << 30;
9.     //默认的加载因子
10.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
11.     //链表转树的长度
12.     static final int TREEIFY_THRESHOLD = 8;
13.     //树转回链表的长度
14.     static final int UNTREEIFY_THRESHOLD = 6;
16.     static final int MIN_TREEIFY_CAPACITY = 64;
18.     public HashMap() {
19.     //设置默认加载因子
20.     //table中已有的元素个数/table所有元素的个数，当这个比值>=0.75的时候需要扩容
21.     //或者说使用的容量到达16*0.75=12时需要扩容
22.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
23.     }
24. }

复制代码

• putVal
  

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

复制代码

3.3.2. 第一次进来table肯定为空，那么扩容

• resize方法
  

1. //hash函数
2. static final int hash(Object key) {
3.     int h;
4.     //hashCode 异或 hashCode 右移16bit
5.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
6. }

复制代码

3.3.3. 使用hash值&数组长度1计算改数据存放的位置i

1. final 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.         //table为空或者长度为0
5.     if ((tab = table) == null || (n = tab.length) == 0)
6.             //第一次扩容
7.         n = (tab = resize()).length;
8.     //使用hash至以及数组长度计算下标，如果table[下标]为空，即没有元素，直接赋值即可
9.     if ((p = tab[return null;]) == null)
10.         tab[i] = newNode(hash, key, value, null);
11.     //否则说明table[下标]有元素
12.     else {
13.         Node<K,V> e; K k;
14.         //头节点不仅hash值相同，key也equals（即头节点就是要找的节点），那么保存这个节点以便后续使用
15.         if (p.hash == hash &&
16.             ((k = p.key) == key || (key != null && key.equals(k))))
17.             e = p;
18.         //头节点不是要找的节点，同时是个TreeNode，那么转调tree的操作
19.         else if (p instanceof TreeNode)
20.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
21.         //头节点不是要找的节点，同时是普通的链表
22.         else {
23.                 //遍历链表找，同时记录遍历了几个元素存到bitCount里。
24.             for (int binCount = 0; ; ++binCount) {
25.                     //到达链表的尾部
26.                 if ((e = p.next) == null) {
27.                     p.next = newNode(hash, key, value, null);
28.                     //判断bitCount是否达到树化的限度，是则树化
29.                     if (binCount >= TREEIFY_THRESHOLD  1) // 1 for 1st
30.                         treeifyBin(tab, hash);
31.                     break;
32.                 }
33.                 //找到了相等的节点
34.                 if (e.hash == hash &&
35.                     ((k = e.key) == key || (key != null && key.equals(k))))
36.                     break;
37.                 p = e;
38.             }
39.         }
40.         //如果有找到相等的节点，那么e保存的就是这个节点的引用，直接替换value即可
41.         if (e != null) { // existing mapping for key
42.             V oldValue = e.value;
43.             if (!onlyIfAbsent || oldValue == null)
44.                 e.value = value;
45.             afterNodeAccess(e);
46.             return oldValue;
47.         }
48.     }
49.     ++modCount;
50.     //加入这个节点后超过了threshold，那么resize
51.     if (++size > threshold)
52.         resize();
53.     afterNodeInsertion(evict);
54.     //hash函数
55. static final int hash(Object key) {
56.     int h;
57.     //hashCode 异或 hashCode 右移16bit
58.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
59. }
60. }

复制代码

3.3.4. 第二次进来如果位置i为空，那么用（key，value）存入该位置

1. //使用hash至以及数组长度计算下标，如果table[下标]为空，即没有元素，直接赋值即可if ((p = tab[final 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.         //table为空或者长度为0
5.     if ((tab = table) == null || (n = tab.length) == 0)
6.             //第一次扩容
7.         n = (tab = resize()).length;
8.     //使用hash至以及数组长度计算下标，如果table[下标]为空，即没有元素，直接赋值即可
9.     if ((p = tab[return null;]) == null)
10.         tab[i] = newNode(hash, key, value, null);
11.     //否则说明table[下标]有元素
12.     else {
13.         Node<K,V> e; K k;
14.         //头节点不仅hash值相同，key也equals（即头节点就是要找的节点），那么保存这个节点以便后续使用
15.         if (p.hash == hash &&
16.             ((k = p.key) == key || (key != null && key.equals(k))))
17.             e = p;
18.         //头节点不是要找的节点，同时是个TreeNode，那么转调tree的操作
19.         else if (p instanceof TreeNode)
20.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
21.         //头节点不是要找的节点，同时是普通的链表
22.         else {
23.                 //遍历链表找，同时记录遍历了几个元素存到bitCount里。
24.             for (int binCount = 0; ; ++binCount) {
25.                     //到达链表的尾部
26.                 if ((e = p.next) == null) {
27.                     p.next = newNode(hash, key, value, null);
28.                     //判断bitCount是否达到树化的限度，是则树化
29.                     if (binCount >= TREEIFY_THRESHOLD  1) // 1 for 1st
30.                         treeifyBin(tab, hash);
31.                     break;
32.                 }
33.                 //找到了相等的节点
34.                 if (e.hash == hash &&
35.                     ((k = e.key) == key || (key != null && key.equals(k))))
36.                     break;
37.                 p = e;
38.             }
39.         }
40.         //如果有找到相等的节点，那么e保存的就是这个节点的引用，直接替换value即可
41.         if (e != null) { // existing mapping for key
42.             V oldValue = e.value;
43.             if (!onlyIfAbsent || oldValue == null)
44.                 e.value = value;
45.             afterNodeAccess(e);
46.             return oldValue;
47.         }
48.     }
49.     ++modCount;
50.     //加入这个节点后超过了threshold，那么resize
51.     if (++size > threshold)
52.         resize();
53.     afterNodeInsertion(evict);
54.     //hash函数
55. static final int hash(Object key) {
56.     int h;
57.     //hashCode 异或 hashCode 右移16bit
58.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
59. }
60. }]) == null)    tab[i] = newNode(hash, key, value, null);

复制代码

3.3.5. 第三次进来如果位置i不为空，那么遍历链表或红黑树找到key相等的节点替换value

1. static class Node<K,V> implements Map.Entry<K,V> {
2.     final int hash;
3.     final K key;
4.     V value;
5.     Node<K,V> next;
7.     Node(int hash, K key, V value, Node<K,V> next) {
8.         this.hash = hash;
9.         this.key = key;
10.         this.value = value;
11.         this.next = next;
12.     }

复制代码

3.3.5.1. 怎么转换成红黑树的

• treeifyBin
  

1. //使用hash至以及数组长度计算下标，如果table[下标]为空，即没有元素，直接赋值即可
2. if ((p = tab[static class Node<K,V> implements Map.Entry<K,V> {
3.     final int hash;
4.     final K key;
5.     V value;
6.     Node<K,V> next;
8.     Node(int hash, K key, V value, Node<K,V> next) {
9.         this.hash = hash;
10.         this.key = key;
11.         this.value = value;
12.         this.next = next;
13.     }]) == null)
14.     tab[i] = newNode(hash, key, value, null);

复制代码

• TreeNode
  

1. //否则说明table[下标]有元素
2. else {
3.     Node<K,V> e; K k;
4.     //头节点不仅hash值相同，key也equals（即头节点就是要找的节点），那么保存这个节点以便后续使用
5.     if (p.hash == hash &&
6.         ((k = p.key) == key || (key != null && key.equals(k))))
7.         e = p;
8.     //头节点不是要找的节点，同时是个TreeNode，那么转调tree的操作
9.     else if (p instanceof TreeNode)
10.         e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
11.     //头节点不是要找的节点，同时是普通的链表
12.     else {
13.             //遍历链表找，同时记录遍历了几个元素存到bitCount里。
14.         for (int binCount = 0; ; ++binCount) {
15.                 //到达链表的尾部
16.             if ((e = p.next) == null) {
17.                 p.next = newNode(hash, key, value, null);
18.                 //判断bitCount是否达到树化的限度，是则树化
19.                 //这里binCount为TREEIFY_THRESHOLD - 1，也就是7的时候
20.                 //也就是这个链表中的节点（不包括头节点）个数为8的时候
21.                 if (binCount >= TREEIFY_THRESHOLD - 1) // 1 for 1st
22.                     treeifyBin(tab, hash);
23.                 break;
24.             }
25.             //找到了相等的节点
26.             if (e.hash == hash &&
27.                 ((k = e.key) == key || (key != null && key.equals(k))))
28.                 break;
29.             p = e;
30.         }
31.     }
32.     //如果有找到相等的节点，那么e保存的就是这个节点的引用，直接替换value即可
33.     if (e != null) { // existing mapping for key
34.         V oldValue = e.value;
35.         if (!onlyIfAbsent || oldValue == null)
36.             e.value = value;
37.         afterNodeAccess(e);
38.         return oldValue;
39.     }
40. }

复制代码

• LinkedHashMap.Entry
  

1. final void treeifyBin(Node<K,V>[] tab, int hash) {
2.     int n, index; Node<K,V> e;
3.     //这里table的长度<64的时候并不进行树化，而是进行扩容
4.     //也就是说链表转换成红黑树的条件是 链表中元素个数为8个 并且 table长度为64
5.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//MIN_TREEIFY_CAPACITY是64
6.         resize();
7.     //下面的操作是把链表中的节点（Node）转换成树中的节点（TreeNode）
8.     else if ((e = tab[index = (n - 1) & hash]) != null) {
9.         TreeNode<K,V> hd = null, tl = null;
10.         //这个循环遍历链表
11.         do {
12.             //传入链表中的当前节点以及下一个节点，转换成TreeNode
13.             TreeNode<K,V> p = replacementTreeNode(e, null);
14.             //tail为空，就是说现在是树中的第一个元素
15.             if (tl == null)
16.                 //那么同时得初始化head为当前节点
17.                 hd = p;
18.             //不是树中的第一个元素，那么插入到树的末尾
19.             else {
20.                 //这里的树节点怎么感觉像是个双向链表？？？
21.                 p.prev = tl;
22.                 tl.next = p;
23.             }
24.             tl = p;
25.         } while ((e = e.next) != null);
26.         if ((tab[index] = hd) != null)
27.             //上面仅是构造了TreeNode为节点的双向链表，这里才是真正的树化操作
28.             hd.treeify(tab);
29.     }
30. }

复制代码

• HashMap.Node
  

1. TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
2.     //就是把当前节点的hash、key、value初始化成TreeNode的hash、key、value
3.     //把下一个节点初始化为TreeNode.next
4.     return new TreeNode<>(p.hash, p.key, p.value, next);
5. }
6.    

复制代码

3.3.5.1.2. 树化

• treeify
  

有点复杂，暂时飘过。。。

1. static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
2.     TreeNode<K,V> parent;  // red-black tree links
3.     TreeNode<K,V> left;
4.     TreeNode<K,V> right;
5.     TreeNode<K,V> prev;    // needed to unlink next upon deletion
6.     boolean red;
7.     //这个构造方法其实就是HashMap的Node的构造方法，没什么特殊的
8.     TreeNode(int hash, K key, V val, Node<K,V> next) {
9.     //LinkedHashMap.Entry
10.         super(hash, key, val, next);
11.     }

复制代码

• getNode方法
  

1. static class Entry<K,V> extends HashMap.Node<K,V> {
2.     Entry<K,V> before, after;
3.     Entry(int hash, K key, V value, Node<K,V> next) {
4.     //HashMap.Node
5.         super(hash, key, value, next);
6.     }
7. }

复制代码

3.4.2. 使用hash值&数组长度-1计算改数据存放的位置i

1. final 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.         //table为空或者长度为0
5.     if ((tab = table) == null || (n = tab.length) == 0)
6.             //第一次扩容
7.         n = (tab = resize()).length;
8.     //使用hash至以及数组长度计算下标，如果table[下标]为空，即没有元素，直接赋值即可
9.     if ((p = tab[return null;]) == null)
10.         tab[i] = newNode(hash, key, value, null);
11.     //否则说明table[下标]有元素
12.     else {
13.         Node<K,V> e; K k;
14.         //头节点不仅hash值相同，key也equals（即头节点就是要找的节点），那么保存这个节点以便后续使用
15.         if (p.hash == hash &&
16.             ((k = p.key) == key || (key != null && key.equals(k))))
17.             e = p;
18.         //头节点不是要找的节点，同时是个TreeNode，那么转调tree的操作
19.         else if (p instanceof TreeNode)
20.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
21.         //头节点不是要找的节点，同时是普通的链表
22.         else {
23.                 //遍历链表找，同时记录遍历了几个元素存到bitCount里。
24.             for (int binCount = 0; ; ++binCount) {
25.                     //到达链表的尾部
26.                 if ((e = p.next) == null) {
27.                     p.next = newNode(hash, key, value, null);
28.                     //判断bitCount是否达到树化的限度，是则树化
29.                     if (binCount >= TREEIFY_THRESHOLD  1) // 1 for 1st
30.                         treeifyBin(tab, hash);
31.                     break;
32.                 }
33.                 //找到了相等的节点
34.                 if (e.hash == hash &&
35.                     ((k = e.key) == key || (key != null && key.equals(k))))
36.                     break;
37.                 p = e;
38.             }
39.         }
40.         //如果有找到相等的节点，那么e保存的就是这个节点的引用，直接替换value即可
41.         if (e != null) { // existing mapping for key
42.             V oldValue = e.value;
43.             if (!onlyIfAbsent || oldValue == null)
44.                 e.value = value;
45.             afterNodeAccess(e);
46.             return oldValue;
47.         }
48.     }
49.     ++modCount;
50.     //加入这个节点后超过了threshold，那么resize
51.     if (++size > threshold)
52.         resize();
53.     afterNodeInsertion(evict);
54.     //hash函数
55. static final int hash(Object key) {
56.     int h;
57.     //hashCode 异或 hashCode 右移16bit
58.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
59. }
60. }

复制代码

3.4.3. 第一个节点就是要找的节点

1. final void treeify(Node<K,V>[] tab) {
2.     TreeNode<K,V> root = null;
3.     for (TreeNode<K,V> x = this, next; x != null; x = next) {
4.         next = (TreeNode<K,V>)x.next;
5.         x.left = x.right = null;
6.         if (root == null) {
7.             x.parent = null;
8.             x.red = false;
9.             root = x;
10.         }
11.         else {
12.             K k = x.key;
13.             int h = x.hash;
14.             Class<?> kc = null;
15.             for (TreeNode<K,V> p = root;;) {
16.                 int dir, ph;
17.                 K pk = p.key;
18.                 if ((ph = p.hash) > h)
19.                     dir = -1;
20.                 else if (ph < h)
21.                     dir = 1;
22.                 else if ((kc == null &&
23.                           (kc = comparableClassFor(k)) == null) ||
24.                          (dir = compareComparables(kc, k, pk)) == 0)
25.                     dir = tieBreakOrder(k, pk);
27.                 TreeNode<K,V> xp = p;
28.                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
29.                     x.parent = xp;
30.                     if (dir <= 0)
31.                         xp.left = x;
32.                     else
33.                         xp.right = x;
34.                     root = balanceInsertion(root, x);
35.                     break;
36.                 }
37.             }
38.         }
39.     }
40.     moveRootToFront(tab, root);
41. }

复制代码

3.4.4. 转调树或红黑树的查找操作找到节点

1. public V get(Object key) {
2.     Node<K,V> e;
3.     //通过key的hash值+key本身寻找node
4.     return (e = getNode(hash(key), key)) == null ? null : e.value;
5. }

复制代码

3.4.5. 没有找到返回null

1. //hash函数
2. static final int hash(Object key) {
3.     int h;
4.     //hashCode 异或 hashCode 右移16bit
5.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
6. }

复制代码

3.5. containsKey方法

1. final Node<K,V> getNode(int hash, Object key) {
2.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
3.     //通过hash&(table长度1)计算下标
4.     if ((tab = table) != null && (n = tab.length) > 0 &&
5.         (first = tab[(n  1) & hash]) != null) {
6.         //找到了：当前节点与table[下标]相等hash相等且key相等
7.         if (first.hash == hash && // always check first node
8.             ((k = first.key) == key || (key != null && key.equals(k))))
9.             return first;
10.         //继续寻找
11.         if ((e = first.next) != null) {
12.                 //TreeNode，转调树
13.             if (first instanceof TreeNode)
14.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
15.             do {
16.                     //遍历链表寻找相等的节点
17.                 if (e.hash == hash &&
18.                     ((k = e.key) == key || (key != null && key.equals(k))))
19.                     return e;
20.             } while ((e = e.next) != null);
21.         }
22.     }
23.     return null;
24. }

复制代码

3.6. remove方法

总体伪算法如下：

• 计算key的hash值
  
• 使用hash值&数组长度1计算改数据存放的位置i
  
• 如果位置i不为空，对比key是否相等，相等则改变头节点指向下一个
  
• 否则
  
  
  
  • 如果是树节点，转调红黑树的删除接口
    
  • 如果是链表节点，遍历链表找到key相等的节点，把前一个节点的next指向该节点的next
    
  
  
• remove
  

1. i = (n - 1) & hash

复制代码

3.6.1. 计算key的hash值

• hash
  

1. if ((tab = table) != null && (n = tab.length) > 0 &&
2.     (first = tab[(n  1) & hash]) != null) {
3.     //找到了：当前节点与table[下标]相等hash相等且key相等
4.     if (first.hash == hash && // always check first node
5.         ((k = first.key) == key || (key != null && key.equals(k))))
6.         return first;

复制代码

• removeNode方法
  

1. final Node removeNode(int hash, Object key, Object value,                           boolean matchValue, boolean movable) {    public boolean containsKey(Object key) {
2.     //也是调用的getNode方法判断是否为空
3.     return getNode(hash(key), key) != null;
4. }        //有找到节点        if (node != null && (!matchValue || (v = node.value) == value ||                             (value != null && value.equals(v)))) {            //转调树            if (node instanceof TreeNode)                ((TreeNode)node).removeTreeNode(this, tab, movable);            //链表的第一个元素            else if (node == p)                tab[index] = node.next;            //链表的非第一个元素            else                p.next = node.next;            ++modCount;            size;            afterNodeRemoval(node);            return node;        }    }    //hash函数
5. static final int hash(Object key) {
6.     int h;
7.     //hashCode 异或 hashCode 右移16bit
8.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
9. }}

复制代码

3.6.2. 使用hash值&数组长度1计算改数据存放的位置i

1. return null;

复制代码

3.6.3. 调用链表或是红黑树的查找操作找到key相等的节点

1. public boolean containsKey(Object key) {
2.     //也是调用的getNode方法判断是否为空
3.     return getNode(hash(key), key) != null;
4. }

复制代码

3.6.4. 调用链表或红黑树的删除操作

1. public V remove(Object key) {
2.     Node<K,V> e;
3.     return (e = removeNode(hash(key), key, null, false, true)) == null ?
4.         null : e.value;
5. }

复制代码

3.7. containsValue

• 效率O（N²）
  

1. //hash函数
2. static final int hash(Object key) {
3.     int h;
4.     //hashCode 异或 hashCode 右移16bit
5.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
6. }

复制代码

4. 问题

4.1. 相对于JDK1.7的区别

• 使用了红黑树
  因此JDK1.8的内部实现是数组+链表+红黑树
  1.8之前是数组+链表实现的。对于一个key，先计算其Hash值再对数组大小取模决定放在那个元素上，再通过连地址法解决冲突
  如果很多key映射到同一个元素上，那么效率退化成O（N），因此1.8在链表超过阈值的时候会转成红黑树，效率为O（logN）
  
• 解决了并发resize时的死循环问题
  保留了顺序，使用的尾插法而不是头插法
  

4.2. 如何解决并发resize时的死循环问题

保留了顺序，把头插法改成了尾插法
4.3. 什么时候扩容

map中Entry的数量 >= threshold的时候，其中threshold =容量*负载因子
4.4. 怎么扩容的

参考

3.3.2. 第一次进来table肯定为空，那么扩容

5. 参考

• HashMap几个***钻的面试题，第六个我就跪了 - 知乎
  
• 3分钟让你明白 HashMap之红黑树树化过程 - 掘金
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

谢谢楼主提供！