说明:本文中所谈论的HashMap基于JDK 1.8版本源码进行分析和说明。
HashMap的put方法算是HashMap中比较核心的功能了,复杂程度高但是算法巧妙,同时在上一版本的基础之上优化了存储结构,从链表逐步进化成了红黑树,以满足存取性能上的需要。本文逐行分析了put方法的执行流程,重点放在了对整个流程的把握,对于红黑树的执行逻辑只是点到为止,其实HashMap中还有很多细节算法值得分析和学习,本文没有涉及,算是抛砖引玉吧,后面抽空把其他的地方分析一番。
源码阅读与分析
1、HashMap的put方法,翻看源码:
1 /** 2 * Associates the specified value with the specified key in this map. 3 * If the map previously contained a mapping for the key, the old 4 * value is replaced. 5 * 6 * @param key key with which the specified value is to be associated 7 * @param value value to be associated with the specified key 8 * @return the previous value associated with <tt>key</tt>, or 9 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 10 * (A <tt>null</tt> return can also indicate that the map 11 * previously associated <tt>null</tt> with <tt>key</tt>.) 12 */ 13 public V put(K key, V value) { 14 return putVal(hash(key), key, value, false, true); 15 }
2、紧接着调用内部方法putVal:
1 /** 2 * Implements Map.put and related methods 3 * 4 * @param hash hash for key 5 * @param key the key 6 * @param value the value to put 7 * @param onlyIfAbsent if true, don't change existing value 8 * @param evict if false, the table is in creation mode. 9 * @return previous value, or null if none 10 */ 11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 12 boolean evict) { 13 Node<K,V>[] tab; Node<K,V> p; int n, i; 14 if ((tab = table) == null || (n = tab.length) == 0) 15 n = (tab = resize()).length; 16 if ((p = tab[i = (n - 1) & hash]) == null) 17 tab[i] = newNode(hash, key, value, null); 18 else { 19 Node<K,V> e; K k; 20 if (p.hash == hash && 21 ((k = p.key) == key || (key != null && key.equals(k)))) 22 e = p; 23 else if (p instanceof TreeNode) 24 e = ((TreeNode<K,V>)p).putTreeva l(this, tab, hash, key, value); 25 else { 26 for (int binCount = 0; ; ++binCount) { 27 if ((e = p.next) == null) { 28 p.next = newNode(hash, key, value, null); 29 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 30 treeifyBin(tab, hash); 31 break; 32 } 33 if (e.hash == hash && 34 ((k = e.key) == key || (key != null && key.equals(k)))) 35 break; 36 p = e; 37 } 38 } 39 if (e != null) { // existing mapping for key 40 V oldValue = e.value; 41 if (!onlyIfAbsent || oldValue == null) 42 e.value = value; 43 afterNodeAccess(e); 44 return oldValue; 45 } 46 } 47 ++modCount; 48 if (++size > threshold) 49 resize(); 50 afterNodeInsertion(evict); 51 return null; 52 }
拆解源码进行解析
1、put方法的注释
我们先把源码中的注释大致翻译一遍:
1 Associates the specified value with the specified key in this map. 2 If the map previously contained a mapping for the key, the old 3 value is replaced. 4 @param key key with which the specified value is to be associated 5 @param value value to be associated with the specified key 6 @return the previous value associated with <tt>key</tt>, or 7 <tt>null</tt> if there was no mapping for <tt>key</tt>. 8 (A <tt>null</tt> return can also indicate that the map 9 previously associated <tt>null</tt> with <tt>key</tt>.)
大意为:将指定的值与此映射中的指定键相关联,如果Map中已经包含了该键的映射,那么旧的映射值将会被替代,也就是说在put时,如果map中已经包含有key所关联的键值对,那么后续put进来的键值对,将会以相同key为准替换掉原来的那一对键值对。
返回的值则将是之前在map中实际与key相关联的Value值(也就是旧的值),如果key没有实际映射