HashMap源码分析

创建一个最简单的HashMap并打上断点。

先看看构造方法另外两个构造方法只是可以自己设置初始容器大小和loadfactor 感兴趣的可以自己看一看

1     /**
2      * Constructs an empty {@code HashMap} with the default initial capacity
3      * (16) and the default load factor (0.75).
4        DEFAULT_LOAD_FACTOR默认为0.75f   初始容量默认为16
5      */
6     public HashMap() {
7         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
8     }

View Code

接下来进入put方法 put方法核心是putVal

 1 public V put(K key, V value) {
 2         return putVal(hash(key), key, value, false, true);
 3 }
 4 
 5 //hash方法为计算哈希值  暂时跳过
 6 //接下来是putVal方法
 7 //olnyIfAbsent为false  则改变现有值
 8 //evict为true 则不为确定的模式
 9 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
10                    boolean evict) {
11         //创建一个Node数组   P节点  
12         Node<K,V>[] tab; Node<K,V> p; int n, i;
13         //一开始为空  resize()方法重新分配内存
14         if ((tab = table) == null || (n = tab.length) == 0)
15             n = (tab = resize()).length;
16         // (n-1)&hash为计算数组中的位置  如果未空直接创建一个新的节点
17         if ((p = tab[i = (n - 1) & hash]) == null)
18             tab[i] = newNode(hash, key, value, null);
19         //不为空则存在冲突  往该位置的链表或者红黑树添加
20          else {
21             Node<K,V> e; K k;
22             //如果当前值的哈希与要加入的哈希相等 并且key也相等  则直接覆盖
23             if (p.hash == hash &&
24                 ((k = p.key) == key || (key != null && key.equals(k))))
25                 e = p;
26             //否则判断是否是红黑树  是的话 往红黑树添加
27             else if (p instanceof TreeNode)
28                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
29             //此时不是红黑树 则是链表往链表尾部添加  同时判断是否大于阈值8 大于则转换 
30             //成红黑树 即调用treeifyBin  
31             //如果没到队尾就发现有哈希值相同 则跳出循环 直接覆盖
32             else {
33                 for (int binCount = 0; ; ++binCount) {
34                     if ((e = p.next) == null) {
35                         p.next = newNode(hash, key, value, null);
36                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
37                             treeifyBin(tab, hash);
38                         break;
39                     }
40                     if (e.hash == hash &&
41                         ((k = e.key) == key || (key != null && key.equals(k))))
42                         break;
43                     p = e;
44                 }
45             }
46             if (e != null) { // existing mapping for key
47                 V oldValue = e.value;
48                 if (!onlyIfAbsent || oldValue == null)
49                     e.value = value;
50                 afterNodeAccess(e);
51                 return oldValue;
52             }
53         }
54         ++modCount;
55         //当数量大于thredshold则扩容
56         if (++size > threshold)
57             resize();
58         afterNodeInsertion(evict);
59         return null;
60     }

putVal方法还算容易理解就是往一个数组加元素如果冲突后该节点为链表就往链表添加如果为红黑树则往红黑树添加哈希相同且key相同则进行替换

接下来看一下putVal中的 resize()方法

 1 /**
 2      * Initializes or doubles table size.  If null, allocates in
 3      * accord with initial capacity target held in field threshold.
 4      * Otherwise, because we are using power-of-two expansion, the
 5      * elements from each bin must either stay at same index, or move
 6      * with a power of two offset in the new table.
 7      *
 8      * @return the table
 9      */
10     final Node<K,V>[] resize() {
11         Node<K,V>[] oldTab = table;
12         //一开始默认为空
13         int oldCap = (oldTab == null) ? 0 : oldTab.length;
14         int oldThr = threshold;
15         int newCap, newThr = 0;
16         //大于0则已经初始化
17         if (oldCap > 0) {
18             //当前已经达到最大 无需扩充 则threshold为最大  直接返回
19             if (oldCap >= MAXIMUM_CAPACITY) {
20                 threshold = Integer.MAX_VALUE;
21                 return oldTab;
22             }
23             //容量和阈值都翻倍
24             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
25                      oldCap >= DEFAULT_INITIAL_CAPACITY)
26                 newThr = oldThr << 1; // double threshold
27         }
28         // 初始容量已存在threshold中
29         else if (oldThr > 0) // initial capacity was placed in threshold
30             newCap = oldThr;
31         //默认构造函数  oldThr为空  则进行初始化  newCap为16   newThr为12
32         else {               // zero initial threshold signifies using defaults
33             newCap = DEFAULT_INITIAL_CAPACITY;
34             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
35         }
36         //计算阈值
37         if (newThr == 0) {
38             float ft = (float)newCap * loadFactor;
39             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
40                       (int)ft : Integer.MAX_VALUE);
41         }
42         //threshold在这里进行赋值
43         threshold = newThr;
44         @SuppressWarnings({"rawtypes","unchecked"})
45         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
46         table = newTab;
47         //之前已经初始化  现在开始扩容
48         if (oldTab != null) {
49             //复制元素，重新进行hash
50             for (int j = 0; j < oldCap; ++j) {
51                 Node<K,V> e;
52                 if ((e = oldTab[j]) != null) {
53                     oldTab[j] = null;
54                     if (e.next == null)
55                         newTab[e.hash & (newCap - 1)] = e;
56                     else if (e instanceof TreeNode)
57                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
58                     else { // preserve order
59                         Node<K,V> loHead = null, loTail = null;
60                         Node<K,V> hiHead = null, hiTail = null;
61                         Node<K,V> next;
62                         do {
63                             next = e.next;
64                             if ((e.hash & oldCap) == 0) {
65                                 if (loTail == null)
66                                     loHead = e;
67                                 else
68                                     loTail.next = e;
69                                 loTail = e;
70                             }
71                             else {
72                                 if (hiTail == null)
73                                     hiHead = e;
74                                 else
75                                     hiTail.next = e;
76                                 hiTail = e;
77                             }
78                         } while ((e = next) != null);
79                         if (loTail != null) {
80                             loTail.next = null;
81                             newTab[j] = loHead;
82                         }
83                         if (hiTail != null) {
84                             hiTail.next = null;
85                             newTab[j + oldCap] = hiHead;
86                         }
87                     }
88                 }
89             }
90         }
91         return newTab;
92     }

由此可见，扩容较为复杂扩容机制为原来的两倍同时会遍历每个元素重新hash找位置比较耗时，应尽量避免。

get方法较为简单，就不分析了大致就是hash 然后找数组上是否存在存在则判断是否有红黑树链表等等

小总结：数组大小n总是2的整数次幂，因此计算下标时直接( hash & n-1)，这样的好处就是可以直接取代取模运算，提高计算速度。分配内存初始化通过resize()方法，主要时初始化的时候和put方法超过阈值的时候扩容，因此最好是在构造函数就进行初始化。哈希冲突时转为链表存储，如果链表的长度大于8则转化为红黑树。