源码分析之Map（三）HashMap

　　HashMap基于哈希表的Map接口实现，是以key-value存储形式存在（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同)。HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

数据结构

　　在 JDK1.8 中，HashMap 是由数组+链表+红黑树构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。数组保存着每个链表的表头结点；查找时，先通过hash函数计算key的hash值，再根据key的hash值计算数组索引（取余法），然后根据索引找到链表表头结点，然后遍历查找该链表；

HashMap源码解析

  1 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
  2 
  3     private static final long serialVersionUID = 362498820763181265L;
  4 
  5     /**
  6      * The default initial capacity. MUST be a power of two.初始化大小16
  7      */
  8     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  9 
 10     /**
 11      * The maximum capacity. MUST be a power of two <= 1<<30.最大值，小于Integer最大值
 12      */
 13     static final int MAXIMUM_CAPACITY = 1 << 30;
 14 
 15     /**
 16      * The load factor used when none specified in constructor.默认负载因子
 17      */
 18     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 19 
 20     /**
 21      * The bin count threshold for using a tree rather than list for a bin. 链表长度到8，转为红黑树
 22      */
 23     static final int TREEIFY_THRESHOLD = 8;
 24 
 25     /**
 26      * The bin count threshold for untreeifying a (split) bin during a
 27      * resize operation.  树大小为6，转为链表
 28      */
 29     static final int UNTREEIFY_THRESHOLD = 6;
 30 
 31     /**
 32      * The smallest table capacity for which bins may be treeified.
 33      * Should be at least 4 * TREEIFY_THRESHOLD  Map里面的数量至少到 64，表中的桶才能转为树。（当哈希冲突超过8，但是元素数量小于64时，会优先扩容而不是树化）
 34      */
 35     static final int MIN_TREEIFY_CAPACITY = 64;
 36 
 37     /**
 38      * Basic hash bin node, used for most entries.  (See below for TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 39      */
 40     static class Node<K,V> implements Map.Entry<K,V> {
 41         final int hash;
 42         final K key;
 43         V value;
 44         Node<K,V> next;
 45 
 46         Node(int hash, K key, V value, Node<K,V> next) {
 47             this.hash = hash;
 48             this.key = key;
 49             this.value = value;
 50             this.next = next;
 51         }
 52 
 53         public final K getKey()        { return key; }
 54         public final V getValue()      { return value; }
 55         public final String toString() { return key + "=" + value; }
 56 
 57         public final int hashCode() { //节点的hashcode由key的hashcode与value的hashcode异或(按位相同为0，不相同为1)得到
 58             return Objects.hashCode(key) ^ Objects.hashCode(value);
 59         }
 60 
 61         public final V setValue(V newValue) {
 62             V oldValue = value;
 63             value = newValue;
 64             return oldValue;
 65         }
 66 
 67         public final boolean equals(Object o) {
 68             if (o == this)
 69                 return true;
 70             if (o instanceof Map.Entry) {
 71                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 72                 if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
 73                     return true;
 74             }
 75             return false;
 76         }
 77     }
 78 
 79     /* ---------------- Static utilities -------------- */
 80 
 81     /**
 82      * 获取hash值方法，右移16位 异或，减少hash冲突 
 83      */
 84     static final int hash(Object key) {
 85         int h;
 86         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 87     }
 88 
 89     /**
 90      * Returns x's Class if it is of the form "class C implements
 91      * Comparable<C>", else null. 如果key实现了Comparable就返回具体类型，否则返回null
 92      */
 93     static Class<?> comparableClassFor(Object x) {
 94         if (x instanceof Comparable) {
 95             Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
 96             if ((c = x.getClass()) == String.class) // bypass checks
 97                 return c;
 98             if ((ts = c.getGenericInterfaces()) != null) {
 99                 for (int i = 0; i < ts.length; ++i) {
100                     if (((t = ts[i]) instanceof ParameterizedType) &&
101                         ((p = (ParameterizedType)t).getRawType() ==
102                          Comparable.class) &&
103                         (as = p.getActualTypeArguments()) != null &&
104                         as.length == 1 && as[0] == c) // type arg is c
105                         return c;
106                 }
107             }
108         }
109         return null;
110     }
111 
112     /**
113      * Returns k.compareTo(x) if x matches kc (k's screened comparable
114      * class), else 0. 比较传入的key和当前遍历元素的key
115      */
116     @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
117     static int compareComparables(Class<?> kc, Object k, Object x) {
118         return (x == null || x.getClass() != kc ? 0 :
119                 ((Comparable)k).compareTo(x));
120     }
121 
122     /**
123      * Returns a power of two size for the given target capacity. 找到大于或等于cap的最小2的幂
124      */
125     static final int tableSizeFor(int cap) {
126         int n = cap - 1;
127         n |= n >>> 1;
128         n |= n >>> 2;
129         n |= n >>> 4;
130         n |= n >>> 8;
131         n |= n >>> 16;
132         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
133     }
134 
135     /* ---------------- Fields -------------- */
136 
137     /**
138      * The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two.     * 存放元素的地方，连续的内存空间，由数组来实现，但存放的元素并不要求紧凑存储。hash索引映射到数组中即为数组索引
139      */
140     transient Node<K,V>[] table;
141 
142     /**
143      * Holds cached entrySet(). Note that AbstractMap fields are used for keySet() and values().
144      */
145     transient Set<Map.Entry<K,V>> entrySet;
146 
147     /**
148      * The number of key-value mappings contained in this map. map中k-v的实时数量
149      */
150     transient int size;
151 
152     /**
153      * The number of times this HashMap has been structurally modified
154      */
155     transient int modCount;
156 
157     /**
158      * The next size value at which to resize (capacity * load factor).
159      * 下一次扩容的预判值。map中元素数量超过这个值就扩容，扩容后HashMap容量是之前的两倍
160      */
161     int threshold;
162 
163     /**
164      * The load factor for the hash table. 加载因子，用来衡量hashMap满的程度。
165      * @serial
166      */
167     final float loadFactor;
168 
169     /* ---------------- Public operations -------------- */
170 
171     /**
172      * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and load factor.
173      *
174      * @param  initialCapacity the initial capacity
175      * @param  loadFactor      the load factor
176      * @throws IllegalArgumentException if the initial capacity is negative or the load factor is nonpositive
177      */
178     public HashMap(int initialCapacity, float loadFactor) {
179         if (initialCapacity < 0)
180             throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
181         if (initialCapacity > MAXIMUM_CAPACITY)
182             initialCapacity = MAXIMUM_CAPACITY;
183         if (loadFactor <= 0 || Float.isNaN(loadFactor))
184             throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
185         this.loadFactor = loadFactor;
186         this.threshold = tableSizeFor(initialCapacity);
187     }
188 
189     /**
190      * Constructs an empty <tt>HashMap</tt> with the specified initial capacity and the default load factor (0.75).*/
191     public HashMap(int initialCapacity) {
192         this(initialCapacity, DEFAULT_LOAD_FACTOR);
193     }
194 
195     /**
196      * Constructs an empty <tt>HashMap</tt> with the default initial capacity (16) and the default load factor (0.75).
197      */
198     public HashMap() {
199         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
200     }
201 
202     /**
203      * Constructs a new <tt>HashMap</tt> with the same mappings as the specified <tt>Map</tt>. 
204      * @param   m the map whose mappings are to be placed in this map
205      * @throws  NullPointerException if the specified map is null
206      */
207     public HashMap(Map<? extends K, ? extends V> m) {
208         this.loadFactor = DEFAULT_LOAD_FACTOR;
209         putMapEntries(m, false);
210     }
211 
212     /**
213      * Implements Map.putAll and Map constructor
214      * @param m the map
215      * @param evict false when initially constructing this map, else true (relayed to method afterNodeInsertion).
216      */
217     final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
218         int s = m.size();
219         if (s > 0) {
220             if (table == null) { // pre-size
221                 float ft = ((float)s / loadFactor) + 1.0F;
222                 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
223                 if (t > threshold)
224                     threshold = tableSizeFor(t);
225             }
226             else if (s > threshold)
227                 resize();
228             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
229                 K key = e.getKey();
230                 V value = e.getValue();
231                 putVal(hash(key), key, value, false, evict);
232             }
233         }
234     }
235 
236     /**
237      * Returns the number of key-value mappings in this map.*/
238     public int size() {
239         return size;
240     }
241 
242     /**
243      * Returns <tt>true</tt> if this map contains no key-value mappings.
244      */
245     public boolean isEmpty() {
246         return size == 0;
247     }
248 
249     /**
250      * Returns the value to which the specified key is mapped,or {@code null} if this map contains no mapping for the key.*/
251     public V get(Object key) {
252         Node<K,V> e;
253         return (e = getNode(hash(key), key)) == null ? null : e.value;
254     }
255 
256     /**
257      * Implements Map.get and related methods
258      * @param hash hash for key
259      * @param key the key
260      * @return the node, or null if none
261      */
262     final Node<K,V> getNode(int hash, Object key) {
263         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
264         if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // (n-1)&hash  根据hash和map大小确定下标位置
265         if (first.hash == hash && // always check first node
266                 ((k = first.key) == key || (key != null && key.equals(k))))
267                 return first;
268             if ((e = first.next) != null) {
269                 if (first instanceof TreeNode)  //如果first是TreeNode类型，调用红黑树方法查询
270                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
271                 do { //对链表进行查找
272                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
273                       return e;
274                 } while ((e = e.next) != null);
275             }
276         }
277         return null;
278     }
279 
280     /**
281      * Returns <tt>true</tt> if this map contains a mapping for the specified key.*/
282     public boolean containsKey(Object key) {
283         return getNode(hash(key), key) != null;
284     }
285 
286     /**
287      * Associates the specified value with the specified key in this map.
288      * If the map previously contained a mapping for the key, the old value is replaced.*/
289     public V put(K key, V value) {
290         return putVal(hash(key), key, value, false, true);
291     }
292 
293     /**
294      * Implements Map.put and related methods
295      *
296      * @param hash hash for key
297      * @param key the key
298      * @param value the value to put
299      * @param onlyIfAbsent if true, don't change existing value
300      * @param evict if false, the table is in creation mode.
301      * @return previous value, or null if none
302      */
303     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
304         Node<K,V>[] tab; Node<K,V> p; int n, i;
305         if ((tab = table) == null || (n = tab.length) == 0) //空表，需要初始化
306             n = (tab = resize()).length;
307         if ((p = tab[i = (n - 1) & hash]) == null) //根据hash确定节点所在桶的位置，并且判断桶中该位置没有元素
308             tab[i] = newNode(hash, key, value, null);
309         else {
310             Node<K,V> e; K k;
311             if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //当前位置就是元素p，说明目的是修改值
312                 e = p;
313             else if (p instanceof TreeNode) //红黑树处理方法
314                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
315             else {
316                 for (int binCount = 0; ; ++binCount) {  //链表结构
317                     if ((e = p.next) == null) { //如果当前节点是尾节点
318                         p.next = newNode(hash, key, value, null);
319                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
320                             treeifyBin(tab, hash);   //链表较长，树化
321                         break;
322                     }
323                     if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //如果元素不匹配
324                         break;
325                     p = e;
326                 }
327             }
328             if (e != null) { // existing mapping for key  找到匹配元素
329                 V oldValue = e.value;
330                 if (!onlyIfAbsent || oldValue == null)
331                     e.value = value;
332                 afterNodeAccess(e);
333                 return oldValue;
334             }
335         }
336         ++modCount; 
337         if (++size > threshold)  //没有找到匹配元素，判断增加元素后是否要扩容
338             resize();
339         afterNodeInsertion(evict);
340         return null;
341     }
342 
343     /**
344      * Initializes or doubles table size. 
345      * @return the table
346      */
347     final Node<K,V>[] resize() {
348         Node<K,V>[] oldTab = table;
349         int oldCap = (oldTab == null) ? 0 : oldTab.length;
350         int oldThr = threshold;
351         int newCap, newThr = 0;
352         if (oldCap > 0) {
353             if (oldCap >= MAXIMUM_CAPACITY) {
354                 threshold = Integer.MAX_VALUE;
355                 return oldTab;
356             }
357             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //扩容，扩充为原来的两倍
358                 newThr = oldThr << 1; // double threshold
359         }
360         else if (oldThr > 0) // initial capacity was placed in threshold
361             newCap = oldThr;
362         else {               // zero initial threshold signifies using defaults
363             newCap = DEFAULT_INITIAL_CAPACITY;
364             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
365         }
366         if (newThr == 0) {
367             float ft = (float)newCap * loadFactor;
368             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
369         }
370         threshold = newThr;
371         @SuppressWarnings({"rawtypes","unchecked"})
372             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
373         table = newTab; 
374         if (oldTab != null) { //扩容完成，进行数据拷贝
375              for (int j = 0; j < oldCap; ++j) {
376                 Node<K,V> e;
377                 if ((e = oldTab[j]) != null) {
378                     oldTab[j] = null;
379                     if (e.next == null)
380                         newTab[e.hash & (newCap - 1)] = e;
381                     else if (e instanceof TreeNode)
382                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
383                     else { // preserve order
384                         Node<K,V> loHead = null, loTail = null;
385                         Node<K,V> hiHead = null, hiTail = null;
386                         Node<K,V> next;
387                         do {
388                             next = e.next;
389                             if ((e.hash & oldCap) == 0) {//oldCap是2的次幂，最高位为1，其他位为0.按位与结果为0，说明hash比它小，原表有这个位置
390                                 if (loTail == null)
391                                     loHead = e;
392                                 else
393                                     loTail.next = e;
394                                 loTail = e;
395                             }
396                             else {
397                                 if (hiTail == null)
398                                     hiHead = e;
399                                 else
400                                     hiTail.next = e;
401                                 hiTail = e;
402                             }
403                         } while ((e = next) != null);
404                         if (loTail != null) {
405                             loTail.next = null;
406                             newTab[j] = loHead;
407                         }
408                         if (hiTail != null) {
409                             hiTail.next = null;
410                             newTab[j + oldCap] = hiHead;
411                         }
412                     }
413                 }
414             }
415         }
416         return newTab;
417     }
418 
419     /**
420      * Replaces all linked nodes in bin at index for given hash unless table is too small, in which case resizes instead.
421      */
422     final void treeifyBin(Node<K,V>[] tab, int hash) {
423         int n, index; Node<K,V> e;
424         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //map大小小于64时，只扩容不树化
425             resize();
426         else if ((e = tab[index = (n - 1) & hash]) != null) {
427             TreeNode<K,V> hd = null, tl = null;
428             do {
429                 TreeNode<K,V> p = replacementTreeNode(e, null);
430                 if (tl == null)
431                     hd = p;
432                 else {
433                     p.prev = tl;
434                     tl.next = p;
435                 }
436                 tl = p;
437             } while ((e = e.next) != null);
438             if ((tab[index] = hd) != null)
439                 hd.treeify(tab);
440         }
441     }
442 
443     /**
444      * Copies all of the mappings from the specified map to this map.*/
445     public void putAll(Map<? extends K, ? extends V> m) {
446         putMapEntries(m, true);
447     }
448 
449     /**
450      * Removes the mapping for the specified key from this map if present.*/
451     public V remove(Object key) {
452         Node<K,V> e;
453         return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
454     }
455 
456     /**
457      * Implements Map.remove and related methods
458      *
459      * @param hash hash for key
460      * @param key the key
461      * @param value the value to match if matchValue, else ignored
462      * @param matchValue if true only remove if value is equal
463      * @param movable if false do not move other nodes while removing
464      * @return the node, or null if none
465      */
466     final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
467         Node<K,V>[] tab; Node<K,V> p; int n, index;
468         if ((tab = table) != null && (n = tab.length) > 0 &&
469             (p = tab[index = (n - 1) & hash]) != null) {
470             Node<K,V> node = null, e; K k; V v;
471             if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
472                 node = p;
473             else if ((e = p.next) != null) {
474                 if (p instanceof TreeNode)
475                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
476                 else {
477                     do {
478                         if (e.hash == hash &&
479                             ((k = e.key) == key ||
480                              (key != null && key.equals(k)))) {
481                             node = e;
482                             break;
483                         }
484                         p = e;
485                     } while ((e = e.next) != null);
486                 }
487             }
488             if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {
489                 if (node instanceof TreeNode)
490                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
491                 else if (node == p)
492                     tab[index] = node.next;
493                 else
494                     p.next = node.next;
495                 ++modCount;
496                 --size;
497                 afterNodeRemoval(node);
498                 return node;
499             }
500         }
501         return null;
502     }
503 
504     /**
505      * Removes all of the mappings from this map.The map will be empty after this call returns.
506      */
507     public void clear() {
508         Node<K,V>[] tab;
509         modCount++;
510         if ((tab = table) != null && size > 0) {
511             size = 0;
512             for (int i = 0; i < tab.length; ++i)
513                 tab[i] = null;
514         }
515     }
516 
517     /**
518      * Returns <tt>true</tt> if this map maps one or more keys to the specified value.
519      * @param value value whose presence in this map is to be tested
520      * @return <tt>true</tt> if this map maps one or more keys to the specified value
521      */
522     public boolean containsValue(Object value) {
523         Node<K,V>[] tab; V v;
524         if ((tab = table) != null && size > 0) {
525             for (int i = 0; i < tab.length; ++i) {
526                 for (Node<K,V> e = tab[i]; e != null; e = e.next) {
527                     if ((v = e.value) == value ||
528                         (value != null && value.equals(v)))
529                         return true;
530                 }
531             }
532         }
533         return false;
534     }
535 
536     // Overrides of JDK8 Map extension methods
537 
538     @Override
539     public V getOrDefault(Object key, V defaultValue) {
540         Node<K,V> e;
541         return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
542     }
543 
544     @Override
545     public V putIfAbsent(K key, V value) {
546         return putVal(hash(key), key, value, true, true);
547     }
548 
549     @Override
550     public boolean remove(Object key, Object value) {
551         return removeNode(hash(key), key, value, true, true) != null;
552     }
553 
554     @Override
555     public boolean replace(K key, V oldValue, V newValue) {
556         Node<K,V> e; V v;
557         if ((e = getNode(hash(key), key)) != null &&
558             ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
559             e.value = newValue;
560             afterNodeAccess(e);
561             return true;
562         }
563         return false;
564     }
565 
566     @Override
567     public V replace(K key, V value) {
568         Node<K,V> e;
569         if ((e = getNode(hash(key), key)) != null) {
570             V oldValue = e.value;
571             e.value = value;
572             afterNodeAccess(e);
573             return oldValue;
574         }
575         return null;
576     }
577 
578     @Override
579     public void forEach(BiConsumer<? super K, ? super V> action) {
580         Node<K,V>[] tab;
581         if (action == null)
582             throw new NullPointerException();
583         if (size > 0 && (tab = table) != null) {
584             int mc = modCount;
585             for (int i = 0; i < tab.length; ++i) {
586                 for (Node<K,V> e = tab[i]; e != null; e = e.next)
587                     action.accept(e.key, e.value);
588             }
589             if (modCount != mc)
590                 throw new ConcurrentModificationException();
591         }
592     }
593 
594     @Override
595     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
596         Node<K,V>[] tab;
597         if (function == null)
598             throw new NullPointerException();
599         if (size > 0 && (tab = table) != null) {
600             int mc = modCount;
601             for (int i = 0; i < tab.length; ++i) {
602                 for (Node<K,V> e = tab[i]; e != null; e = e.next) {
603                     e.value = function.apply(e.key, e.value);
604                 }
605             }
606             if (modCount != mc)
607                 throw new ConcurrentModificationException();
608         }
609     }
610 
611     /* ------------------------------------------------------------ */
612     // Cloning and serialization
613 
614     /**
615      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and values themselves are not cloned.
616      *
617      * @return a shallow copy of this map
618      */
619     @SuppressWarnings("unchecked")
620     @Override
621     public Object clone() {
622         HashMap<K,V> result;
623         try {
624             result = (HashMap<K,V>)super.clone();
625         } catch (CloneNotSupportedException e) {
626             // this shouldn't happen, since we are Cloneable
627             throw new InternalError(e);
628         }
629         result.reinitialize();
630         result.putMapEntries(this, false);
631         return result;
632     }
633 
634     // These methods are also used when serializing HashSets
635     final float loadFactor() { return loadFactor; }
636     final int capacity() {
637         return (table != null) ? table.length : (threshold > 0) ? threshold : DEFAULT_INITIAL_CAPACITY;
638     }/* ------------------------------------------------------------ */
639     // LinkedHashMap support
640 
641 
642     /*
643      * The following package-protected methods are designed to be
644      * overridden by LinkedHashMap, but not by any other subclass.
645      * Nearly all other internal methods are also package-protected
646      * but are declared final, so can be used by LinkedHashMap, view
647      * classes, and HashSet.
648      */
649 
650     // Create a regular (non-tree) node
651     Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
652         return new Node<>(hash, key, value, next);
653     }
654 
655     // For conversion from TreeNodes to plain nodes
656     Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
657         return new Node<>(p.hash, p.key, p.value, next);
658     }
659 
660     // Create a tree bin node
661     TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
662         return new TreeNode<>(hash, key, value, next);
663     }
664 
665     // For treeifyBin
666     TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
667         return new TreeNode<>(p.hash, p.key, p.value, next);
668     }
669 
670     /**
671      * Reset to initial default state.  Called by clone and readObject.
672      */
673     void reinitialize() {
674         table = null;
675         entrySet = null;
676         keySet = null;
677         values = null;
678         modCount = 0;
679         threshold = 0;
680         size = 0;
681     }
682 
683     // Callbacks to allow LinkedHashMap post-actions
684     void afterNodeAccess(Node<K,V> p) { }
685     void afterNodeInsertion(boolean evict) { }
686     void afterNodeRemoval(Node<K,V> p) { }
687 
688     // Called only from writeObject, to ensure compatible ordering.
689     void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
690         Node<K,V>[] tab;
691         if (size > 0 && (tab = table) != null) {
692             for (int i = 0; i < tab.length; ++i) {
693                 for (Node<K,V> e = tab[i]; e != null; e = e.next) {
694                     s.writeObject(e.key);
695                     s.writeObject(e.value);
696                 }
697             }
698         }
699     }
700 
701 }

HashMap View Code

总结：

　　1.MAXIMUM_CAPACITY 是数组最大的长度2的30次方，原因是2的31次方就超过Integer.MAX_VALUE(2147483647)了（也就是2^31-1）

　　2.HashMap有两个参数影响其性能：初始容量和加载因子。默认初始容量是16，加载因子是0.75。容量是哈希表中桶(Entry数组)的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。

　　3.transient是Java语言的关键字，用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候，transient型变量的值不包括在串行化的表示中，也就是说没法持久化。

　　4.在扩容过程中，树化要满足两个条件：链表长度大于等于 TREEIFY_THRESHOLD、桶数组容量大于等于 MIN_TREEIFY_CAPACITY

　　其他hashcode相关内容见源码分析之Map（二）HashCode详解

HashMap.TreeNode源码解析

　　TreeNode不仅是红黑树，还是链表。继承了LinkedHashMap.Entry，而Entry继承了 HashMap.Node

  1 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
  2 
  3      
  4   static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  5         TreeNode<K,V> parent;  // red-black tree links
  6         TreeNode<K,V> left;
  7         TreeNode<K,V> right;
  8         TreeNode<K,V> prev;    // needed to unlink next upon deletion  前一个录入节点，删除后需要取消链接
  9         boolean red;
 10         TreeNode(int hash, K key, V val, Node<K,V> next) {
 11             super(hash, key, val, next);
 12         }
 13 
 14         /**
 15          * Returns root of tree containing this node. 获取root节点
 16          */
 17         final TreeNode<K,V> root() {
 18             for (TreeNode<K,V> r = this, p;;) {
 19                 if ((p = r.parent) == null)
 20                     return r;
 21                 r = p;
 22             }
 23         }
 24 
 25         /**
 26          * Ensures that the given root is the first node of its bin.          * 移动root节点到前面，然后确认是否符合红黑树性质
 27          */
 28         static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
 29             int n;
 30             if (root != null && tab != null && (n = tab.length) > 0) {
 31                 int index = (n - 1) & root.hash; //树在数组中的下标
 32                 TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
 33                 if (root != first) {
 34                     Node<K,V> rn;
 35                     tab[index] = root; //将传入的root放在此位置
 36                     TreeNode<K,V> rp = root.prev;
 37                     if ((rn = root.next) != null) //root的后一个节点不为null
 38                         ((TreeNode<K,V>)rn).prev = rp; //root的前节点指向root的后节点的前节点，相当于移除root
 39                     if (rp != null)
 40                         rp.next = rn;
 41                     if (first != null)
 42                         first.prev = root; //原首节点的前一个指向root
 43                     root.next = first; //root的下一个节点指向原首节点
 44                     root.prev = null;
 45                 }
 46                 assert checkInvariants(root);
 47             }
 48         }
 49 
 50         /**
 51          * Finds the node starting at root p with the given hash and key.
 52          * The kc argument caches comparableClassFor(key) upon first use
 53          * comparing keys. 以该节点作为根节点，查找对象k  h是k的hash值　　　　  */
 54         final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
 55             TreeNode<K,V> p = this;
 56             do {
 57                 int ph, dir; K pk;
 58                 TreeNode<K,V> pl = p.left, pr = p.right, q;
 59                 if ((ph = p.hash) > h) //如果当前节点的hash值大于k的hash值，那么后续应该让k和左孩子节点进行下一轮比较
 60                     p = pl;
 61                 else if (ph < h)
 62                     p = pr;
 63                 else if ((pk = p.key) == k || (k != null && k.equals(pk))) //地址相同或equals相同
 64                     return p; //返回当前节点
 65                 else if (pl == null)
 66                     p = pr;
 67                 else if (pr == null)
 68                     p = pl;
 69                 else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)
 70                     p = (dir < 0) ? pl : pr;
 71                 else if ((q = pr.find(h, k, kc)) != null) //从右孩子节点递归循环查找，如果匹配则返回
 72                     return q;
 73                 else
 74                     p = pl;
 75             } while (p != null);
 76             return null;
 77         }
 78 
 79         /**
 80          * Calls find for root node.
 81          */
 82         final TreeNode<K,V> getTreeNode(int h, Object k) {
 83             return ((parent != null) ? root() : this).find(h, k, null);
 84         }
 85 
 86         /**
 87          * Tie-breaking utility for ordering insertions when equal  hashCodes and non-comparable. We don't require a total
 88          * order, just a consistent insertion rule to maintain equivalence across rebalancings. Tie-breaking further than
 89          * necessary simplifies testing a bit.
 90          */
 91         static int tieBreakOrder(Object a, Object b) {
 92             int d;
 93             if (a == null || b == null ||
 94                 (d = a.getClass().getName().
 95                  compareTo(b.getClass().getName())) == 0)
 96                 d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
 97                      -1 : 1);
 98             return d;
 99         }
100 
101         /**
102          * Forms tree of the nodes linked from this node. 从当前节点开始，遍历列表，往红黑树里插入。插入后平衡处理
103          * @return root of tree
104          */
105         final void treeify(Node<K,V>[] tab) {
106             TreeNode<K,V> root = null;
107             for (TreeNode<K,V> x = this, next; x != null; x = next) {
108                 next = (TreeNode<K,V>)x.next;
109                 x.left = x.right = null;
110                 if (root == null) { //设置第一个节点为根节点，颜色为黑色
111                     x.parent = null;
112                     x.red = false;
113                     root = x;
114                 }
115                 else {
116                     K k = x.key;
117                     int h = x.hash;
118                     Class<?> kc = null;
119                     for (TreeNode<K,V> p = root;;) {
120                         int dir, ph;
121                         K pk = p.key;
122                         if ((ph = p.hash) > h)
123                             dir = -1;
124                         else if (ph < h)
125                             dir = 1;
126                         else if ((kc == null &&
127                                   (kc = comparableClassFor(k)) == null) ||
128                                  (dir = compareComparables(kc, k, pk)) == 0)
129                             dir = tieBreakOrder(k, pk);
130 
131                         TreeNode<K,V> xp = p;
132                         if ((p = (dir <= 0) ? p.left : p.right) == null) {//dir小于等于0，指向左子树，反之右子树，如果为null直接插入，不为null则继续遍历
133                             x.parent = xp;
134                             if (dir <= 0)
135                                 xp.left = x;
136                             else
137                                 xp.right = x;
138                             root = balanceInsertion(root, x); //红黑树平衡
139                             break;
140                         }
141                     }
142                 }
143             }
144             moveRootToFront(tab, root);//把根节点指向桶节点
145         }
146 
147         /**
148          * Returns a list of non-TreeNodes replacing those linked from
149          * this node. 红黑树转链表
150          */
151         final Node<K,V> untreeify(HashMap<K,V> map) {
152             Node<K,V> hd = null, tl = null;
153             for (Node<K,V> q = this; q != null; q = q.next) {
154                 Node<K,V> p = map.replacementNode(q, null);
155                 if (tl == null)
156                     hd = p;
157                 else
158                     tl.next = p;
159                 tl = p;
160             }
161             return hd;
162         }
163 
164         /**
165          * Tree version of putVal.
166          */
167         final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
168             Class<?> kc = null;
169             boolean searched = false;
170             TreeNode<K,V> root = (parent != null) ? root() : this;
171             for (TreeNode<K,V> p = root;;) {
172                 int dir, ph; K pk;
173                 if ((ph = p.hash) > h)
174                     dir = -1;
175                 else if (ph < h)
176                     dir = 1;
177                 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
178                     return p;
179                 else if ((kc == null &&
180                           (kc = comparableClassFor(k)) == null) ||
181                          (dir = compareComparables(kc, k, pk)) == 0) {
182                     if (!searched) {
183                         TreeNode<K,V> q, ch;
184                         searched = true;
185                         if (((ch = p.left) != null &&
186                              (q = ch.find(h, k, kc)) != null) ||
187                             ((ch = p.right) != null &&
188                              (q = ch.find(h, k, kc)) != null))
189                             return q;
190                     }
191                     dir = tieBreakOrder(k, pk);
192                 }
193 
194                 TreeNode<K,V> xp = p;
195                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
196                     Node<K,V> xpn = xp.next;
197                     TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
198                     if (dir <= 0)
199                         xp.left = x;
200                     else
201                         xp.right = x;
202                     xp.next = x;
203                     x.parent = x.prev = xp;
204                     if (xpn != null)
205                         ((TreeNode<K,V>)xpn).prev = x;
206                     moveRootToFront(tab, balanceInsertion(root, x));
207                     return null;
208                 }
209             }
210         }
211 
212         /**
213          * Removes the given node, that must be present before this call.
214          */
215         final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
216                                   boolean movable) {
217             int n;
218             if (tab == null || (n = tab.length) == 0)
219                 return;
220             int index = (n - 1) & hash;
221             TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
222             TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
223             if (pred == null)
224                 tab[index] = first = succ;
225             else
226                 pred.next = succ;
227             if (succ != null)
228                 succ.prev = pred;
229             if (first == null)
230                 return;
231             if (root.parent != null)
232                 root = root.root();
233             if (root == null || root.right == null ||
234                 (rl = root.left) == null || rl.left == null) {
235                 tab[index] = first.untreeify(map);  // too small
236                 return;
237             }
238             TreeNode<K,V> p = this, pl = left, pr = right, replacement;
239             if (pl != null && pr != null) {
240                 TreeNode<K,V> s = pr, sl;
241                 while ((sl = s.left) != null) // find successor
242                     s = sl;
243                 boolean c = s.red; s.red = p.red; p.red = c; // swap colors
244                 TreeNode<K,V> sr = s.right;
245                 TreeNode<K,V> pp = p.parent;
246                 if (s == pr) { // p was s's direct parent
247                     p.parent = s;
248                     s.right = p;
249                 }
250                 else {
251                     TreeNode<K,V> sp = s.parent;
252                     if ((p.parent = sp) != null) {
253                         if (s == sp.left)
254                             sp.left = p;
255                         else
256                             sp.right = p;
257                     }
258                     if ((s.right = pr) != null)
259                         pr.parent = s;
260                 }
261                 p.left = null;
262                 if ((p.right = sr) != null)
263                     sr.parent = p;
264                 if ((s.left = pl) != null)
265                     pl.parent = s;
266                 if ((s.parent = pp) == null)
267                     root = s;
268                 else if (p == pp.left)
269                     pp.left = s;
270                 else
271                     pp.right = s;
272                 if (sr != null)
273                     replacement = sr;
274                 else
275                     replacement = p;
276             }
277             else if (pl != null)
278                 replacement = pl;
279             else if (pr != null)
280                 replacement = pr;
281             else
282                 replacement = p;
283             if (replacement != p) {
284                 TreeNode<K,V> pp = replacement.parent = p.parent;
285                 if (pp == null)
286                     root = replacement;
287                 else if (p == pp.left)
288                     pp.left = replacement;
289                 else
290                     pp.right = replacement;
291                 p.left = p.right = p.parent = null;
292             }
293 
294             TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
295 
296             if (replacement == p) {  // detach
297                 TreeNode<K,V> pp = p.parent;
298                 p.parent = null;
299                 if (pp != null) {
300                     if (p == pp.left)
301                         pp.left = null;
302                     else if (p == pp.right)
303                         pp.right = null;
304                 }
305             }
306             if (movable)
307                 moveRootToFront(tab, r);
308         }
309 
310         /**
311          * Splits nodes in a tree bin into lower and upper tree bins,
312          * or untreeifies if now too small. Called only from resize;
313          * see above discussion about split bits and indices.
314          *
315          * @param map the map
316          * @param tab the table for recording bin heads
317          * @param index the index of the table being split
318          * @param bit the bit of hash to split on
319          */
320         final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
321             TreeNode<K,V> b = this;
322             // Relink into lo and hi lists, preserving order
323             TreeNode<K,V> loHead = null, loTail = null;
324             TreeNode<K,V> hiHead = null, hiTail = null;
325             int lc = 0, hc = 0;
326             for (TreeNode<K,V> e = b, next; e != null; e = next) {
327                 next = (TreeNode<K,V>)e.next;
328                 e.next = null;
329                 if ((e.hash & bit) == 0) {
330                     if ((e.prev = loTail) == null)
331                         loHead = e;
332                     else
333                         loTail.next = e;
334                     loTail = e;
335                     ++lc;
336                 }
337                 else {
338                     if ((e.prev = hiTail) == null)
339                         hiHead = e;
340                     else
341                         hiTail.next = e;
342                     hiTail = e;
343                     ++hc;
344                 }
345             }
346 
347             if (loHead != null) {
348                 if (lc <= UNTREEIFY_THRESHOLD)
349                     tab[index] = loHead.untreeify(map);
350                 else {
351                     tab[index] = loHead;
352                     if (hiHead != null) // (else is already treeified)
353                         loHead.treeify(tab);
354                 }
355             }
356             if (hiHead != null) {
357                 if (hc <= UNTREEIFY_THRESHOLD)
358                     tab[index + bit] = hiHead.untreeify(map);
359                 else {
360                     tab[index + bit] = hiHead;
361                     if (loHead != null)
362                         hiHead.treeify(tab);
363                 }
364             }
365         }
366 
367         /* ------------------------------------------------------------ */
368         // Red-black tree methods, all adapted from CLR        // 进行左旋的是当前节点⑤和它的右节点12。12取代⑤的位置；⑤变成12的左节点；⑦点变成⑤的右节点
369 
370         static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,TreeNode<K,V> p) {
371             TreeNode<K,V> r, pp, rl;
372             if (p != null && (r = p.right) != null) {
373                 if ((rl = p.right = r.left) != null)
374                     rl.parent = p;
375                 if ((pp = r.parent = p.parent) == null)
376                     (root = r).red = false;
377                 else if (pp.left == p)
378                     pp.left = r;
379                 else
380                     pp.right = r;
381                 r.left = p;
382                 p.parent = r;
383             }
384             return root;
385         }
386 　　　　 //进行右旋的是当前节点19和它的左节点12。12取代19的位置；19变成12的右节点;13变成19的左节点
387         static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
388             TreeNode<K,V> l, pp, lr;
389             if (p != null && (l = p.left) != null) {
390                 if ((lr = p.left = l.right) != null)
391                     lr.parent = p;
392                 if ((pp = l.parent = p.parent) == null)
393                     (root = l).red = false;
394                 else if (pp.right == p)
395                     pp.right = l;
396                 else
397                     pp.left = l;
398                 l.right = p;
399                 p.parent = l;
400             }
401             return root;
402         }
403 
404         static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,TreeNode<K,V> x) {
405             x.red = true;
406             for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
407                 if ((xp = x.parent) == null) {
408                     x.red = false;
409                     return x;
410                 }
411                 else if (!xp.red || (xpp = xp.parent) == null)
412                     return root;
413                 if (xp == (xppl = xpp.left)) {
414                     if ((xppr = xpp.right) != null && xppr.red) {
415                         xppr.red = false;
416                         xp.red = false;
417                         xpp.red = true;
418                         x = xpp;
419                     }
420                     else {
421                         if (x == xp.right) {
422                             root = rotateLeft(root, x = xp);
423                             xpp = (xp = x.parent) == null ? null : xp.parent;
424                         }
425                         if (xp != null) {
426                             xp.red = false;
427                             if (xpp != null) {
428                                 xpp.red = true;
429                                 root = rotateRight(root, xpp);
430                             }
431                         }
432                     }
433                 }
434                 else {
435                     if (xppl != null && xppl.red) {
436                         xppl.red = false;
437                         xp.red = false;
438                         xpp.red = true;
439                         x = xpp;
440                     }
441                     else {
442                         if (x == xp.left) {
443                             root = rotateRight(root, x = xp);
444                             xpp = (xp = x.parent) == null ? null : xp.parent;
445                         }
446                         if (xp != null) {
447                             xp.red = false;
448                             if (xpp != null) {
449                                 xpp.red = true;
450                                 root = rotateLeft(root, xpp);
451                             }
452                         }
453                     }
454                 }
455             }
456         }
457 
458         static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) {
459             for (TreeNode<K,V> xp, xpl, xpr;;)  {
460                 if (x == null || x == root)
461                     return root;
462                 else if ((xp = x.parent) == null) {
463                     x.red = false;
464                     return x;
465                 }
466                 else if (x.red) {
467                     x.red = false;
468                     return root;
469                 }
470                 else if ((xpl = xp.left) == x) {
471                     if ((xpr = xp.right) != null && xpr.red) {
472                         xpr.red = false;
473                         xp.red = true;
474                         root = rotateLeft(root, xp);
475                         xpr = (xp = x.parent) == null ? null : xp.right;
476                     }
477                     if (xpr == null)
478                         x = xp;
479                     else {
480                         TreeNode<K,V> sl = xpr.left, sr = xpr.right;
481                         if ((sr == null || !sr.red) &&
482                             (sl == null || !sl.red)) {
483                             xpr.red = true;
484                             x = xp;
485                         }
486                         else {
487                             if (sr == null || !sr.red) {
488                                 if (sl != null)
489                                     sl.red = false;
490                                 xpr.red = true;
491                                 root = rotateRight(root, xpr);
492                                 xpr = (xp = x.parent) == null ?
493                                     null : xp.right;
494                             }
495                             if (xpr != null) {
496                                 xpr.red = (xp == null) ? false : xp.red;
497                                 if ((sr = xpr.right) != null)
498                                     sr.red = false;
499                             }
500                             if (xp != null) {
501                                 xp.red = false;
502                                 root = rotateLeft(root, xp);
503                             }
504                             x = root;
505                         }
506                     }
507                 }
508                 else { // symmetric
509                     if (xpl != null && xpl.red) {
510                         xpl.red = false;
511                         xp.red = true;
512                         root = rotateRight(root, xp);
513                         xpl = (xp = x.parent) == null ? null : xp.left;
514                     }
515                     if (xpl == null)
516                         x = xp;
517                     else {
518                         TreeNode<K,V> sl = xpl.left, sr = xpl.right;
519                         if ((sl == null || !sl.red) &&
520                             (sr == null || !sr.red)) {
521                             xpl.red = true;
522                             x = xp;
523                         }
524                         else {
525                             if (sl == null || !sl.red) {
526                                 if (sr != null)
527                                     sr.red = false;
528                                 xpl.red = true;
529                                 root = rotateLeft(root, xpl);
530                                 xpl = (xp = x.parent) == null ?
531                                     null : xp.left;
532                             }
533                             if (xpl != null) {
534                                 xpl.red = (xp == null) ? false : xp.red;
535                                 if ((sl = xpl.left) != null)
536                                     sl.red = false;
537                             }
538                             if (xp != null) {
539                                 xp.red = false;
540                                 root = rotateRight(root, xp);
541                             }
542                             x = root;
543                         }
544                     }
545                 }
546             }
547         }
548 
549         /**
550          * Recursive invariant check
551          */
552         static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
553             TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
554                 tb = t.prev, tn = (TreeNode<K,V>)t.next;
555             if (tb != null && tb.next != t)
556                 return false;
557             if (tn != null && tn.prev != t)
558                 return false;
559             if (tp != null && t != tp.left && t != tp.right)
560                 return false;
561             if (tl != null && (tl.parent != t || tl.hash > t.hash))
562                 return false;
563             if (tr != null && (tr.parent != t || tr.hash < t.hash))
564                 return false;
565             if (t.red && tl != null && tl.red && tr != null && tr.red)
566                 return false;
567             if (tl != null && !checkInvariants(tl))
568                 return false;
569             if (tr != null && !checkInvariants(tr))
570                 return false;
571             return true;
572         }
573     }}

TreeNode View Code

　　红黑树的特性见数据结构之树（三）

　　参照：https://blog.csdn.net/sun112233445/article/details/103350026