HashMap源码分析

主要过一遍HashMap中的常量、构造方法、put方法
当我们调用put时，实际上就是调用putVal

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

复制代码

putVal

1. /**
2. * @param  onlyIfAbsent        若为true，插入重复key的值时，不改变已存在的value
3. * @param  evict 若为false，则表为创建模式（在HashMap中因该没啥用，LinkedhashMap需要注意）
4. */
5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
6.     Node<K,V>[] tab;
7.     Node<K,V> p; // p在后边用来暂存冲突位置上的元素
8.     int n, i;        // n为table.length
9.     // 1. 新创建的HashMap先初始化
10.     if ((tab = table) == null || (n = tab.length) == 0)
11.         n = (tab = resize()).length;
12.     // 2. 若指定位置不存在元素(没有hash冲突)
13.     if ((p = tab[i = (n - 1) & hash]) == null) // n为hashMap的长度，即2的幂次，故：(n-1)&hash = hash%n
14.         tab[i] = newNode(hash, key, value, null);
15.     else {
16.        // 3. 发生冲突时处理逻辑
17.         Node<K,V> e;
18.         K k; // 冲突位置上的key
19.         // 3.1 key相同则覆盖旧值
20.         if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
21.             e = p;
22.         // 3.2 已有很多冲突值(已经转为树了)，则put进该冲突树
23.         else if (p instanceof TreeNode)
24.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
25.         // 3.3 拉链法存放
26.         else {
27.             // 3.3.1 循环冲突链表，将新来的冲突的元素尾插到链表中
28.             for (int binCount = 0; ; ++binCount) {
29.                 if ((e = p.next) == null) {
30.                     p.next = newNode(hash, key, value, null);
31.                     
32.                     if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8
33.                             // 链表转红黑树       
34.                         treeifyBin(tab, hash);
35.                     break;
36.                 }
37.                 // 如果新插入的元素是与冲突链表上的key相同的，那么就要覆盖这个key对应的value
38.                 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
39.                     // beark后走【a】处的逻辑
40.                     break;
41.                 p = e;
42.             }
43.         }
44.         // 循环结束后，经历尾插后的e为空
45.         
46.         if (e != null) { // 【a】existing mapping for key
47.             V oldValue = e.value;
48.             if (!onlyIfAbsent || oldValue == null)
49.                 e.value = value;
50.             afterNodeAccess(e);// 这方法空的，没啥用，在LinkedHashMap中被重写
51.             return oldValue;
52.         }
53.     }
54.    
55.     ++modCount;                // 记录被结构修改的次数
56.     // 如果当前保存的k-v数量(不包含冲突的)大于阈值 则扩容
57.     if (++size > threshold)
58.         resize();
59.     afterNodeInsertion(evict);// 这方法空的，没啥用，在LinkedHashMap中被重写
60.     return null;
61. }

复制代码

resize

初始化或加倍表的大小。
如果为空，则按照字段阈值中持有的初始容量目标分配。
否则，因为我们使用的是2的幂展开，所以每个bin中的元素要么必须保持相同的索引，要么在新表中以2的幂偏移量移动。

1. final Node<K,V>[] resize() {
2.     Node<K,V>[] oldTab = table;
3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
4.     int oldThr = threshold; // 类成员变量threshold，int类型默认值为0
5.     int newCap, newThr = 0;
6.     // 1.确定新阈值和新容量
7.     // 1.1 元素不为空
8.     if (oldCap > 0) {
9.         if (oldCap >= MAXIMUM_CAPACITY) { //  MAXIMUM_CAPACITY = 1 << 30 = 1073741824
10.             threshold = Integer.MAX_VALUE;//  MAX_VALUE = 2147483647
11.             return oldTab;
12.         }
13.         // newCap扩为原来的2倍 ，若其在[16,1073741824)范围内threshold也翻倍
14.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
15.             newThr = oldThr << 1;   
16.     }
17.     // 1.2 元素为空，且阈值有效（可能是调用HashMap(int initialCapacity,float loadFactor)初始化或被清空元素的hashmap）
18.     else if (oldThr > 0)
19.         newCap = oldThr;
20.     // 1.3 新创建的HashMap 容量默认为16，阈值默认为(负载因子*容量)0.75*16=12
21.     else {              
22.         newCap = DEFAULT_INITIAL_CAPACITY;
23.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
24.     }
25.     if (newThr == 0) {
26.         float ft = (float)newCap * loadFactor;
27.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
28.                   (int)ft : Integer.MAX_VALUE);
29.     }
30.     threshold = newThr;
31.     @SuppressWarnings({"rawtypes","unchecked"})
32.     // 2.扩容
33.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
34.     table = newTab;
35.     if (oldTab != null) {
36.         // 循环老的元素
37.         for (int j = 0; j < oldCap; ++j) {
38.             Node<K,V> e;
39.             if ((e = oldTab[j]) != null) {
40.                 oldTab[j] = null;
41.                 // 2.1 该元素链表中没有存储冲突值，重新计算该元素存储位置，并赋值
42.                 if (e.next == null)
43.                     newTab[e.hash & (newCap - 1)] = e;
44.                
45.                 // 2.2 如果该元素保存到冲突值很多 以至于链表已经转成红了
46.                 else if (e instanceof TreeNode)
47.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
48.                
49.                 // 2.3 有产生冲突的值，但还没有转成树
50.                 else { // preserve order
51.                     Node<K,V> loHead = null, loTail = null;
52.                     Node<K,V> hiHead = null, hiTail = null;
53.                     Node<K,V> next;
54.                     do {
55.                         next = e.next;
56.                         // 空键的hash为零，或出现1001 & 0110这种情况
57.                         if ((e.hash & oldCap) == 0) {
58.                             if (loTail == null)
59.                                 loHead = e;
60.                             else
61.                                 loTail.next = e;
62.                             loTail = e;
63.                         }
64.                         else {
65.                             if (hiTail == null)
66.                                 hiHead = e;
67.                             else
68.                                 hiTail.next = e;
69.                             hiTail = e;
70.                         }
71.                     } while ((e = next) != null);
72.                     // 将冲突的链表拎出来，放到数组中
73.                     if (loTail != null) {
74.                         loTail.next = null;
75.                         newTab[j] = loHead;
76.                     }
77.                     if (hiTail != null) {
78.                         hiTail.next = null;
79.                         newTab[j + oldCap] = hiHead;
80.                     }
81.                 }
82.             }
83.         }
84.     }
85.     return newTab;
86. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

继续阅读请点击广告