【Java】HashMap源码分析——常用方法详解
上一篇介绍了HashMap的基本概念，这一篇着重介绍HasHMap中的一些常用方法：
put()
get()
**resize()**
首先介绍resize()这个方法，在我看来这是HashMap中一个非常重要的方法，是用来调整HashMap中table的容量的，在很多操作中多需要重新计算容量。
源码如下：
1 final Node<K,V>[] resize() { 2 Node<K,V>[] oldTab = table; 3 int oldCap = (oldTab == null) ? 0 : oldTab.length; 4 int oldThr = threshold; 5 int newCap, newThr = 0; 6 if (oldCap > 0) { 7 if (oldCap >= MAXIMUM_CAPACITY) { 8 threshold = Integer.MAX_VALUE; 9 return oldTab; 10 } 11 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 12 oldCap >= DEFAULT_INITIAL_CAPACITY) 13 newThr = oldThr << 1; // double threshold 14 } 15 else if (oldThr > 0) // initial capacity was placed in threshold 16 newCap = oldThr; 17 else { // zero initial threshold signifies using defaults 18 newCap = DEFAULT_INITIAL_CAPACITY; 19 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 20 } 21 if (newThr == 0) { 22 float ft = (float)newCap * loadFactor; 23 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 24 (int)ft : Integer.MAX_VALUE); 25 } 26 threshold = newThr; 27 @SuppressWarnings({"rawtypes","unchecked"}) 28 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 29 table = newTab; 30 if (oldTab != null) { 31 for (int j = 0; j < oldCap; ++j) { 32 Node<K,V> e; 33 if ((e = oldTab[j]) != null) { 34 oldTab[j] = null; 35 if (e.next == null) 36 newTab[e.hash & (newCap - 1)] = e; 37 else if (e instanceof TreeNode) 38 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 39 else { // preserve order 40 Node<K,V> loHead = null, loTail = null; 41 Node<K,V> hiHead = null, hiTail = null; 42 Node<K,V> next; 43 do { 44 next = e.next; 45 if ((e.hash & oldCap) == 0) { 46 if (loTail == null) 47 loHead = e; 48 else 49 loTail.next = e; 50 loTail = e; 51 } 52 else { 53 if (hiTail == null) 54 hiHead = e; 55 else 56 hiTail.next = e; 57 hiTail = e; 58 } 59 } while ((e = next) != null); 60 if (loTail != null) { 61 loTail.next = null; 62 newTab[j] = loHead; 63 } 64 if (hiTail != null) { 65 hiTail.next = null; 66 newTab[j + oldCap] = hiHead; 67 } 68 } 69 } 70 } 71 } 72 return newTab; 73 }
可以看到这段代码非常庞大，其内容可以分为两大部分：
第一部分计算并生成新的哈希表（空表）：
1 // 记录原表 2 Node<K,V>[] oldTab = table; 3 // 得到原来哈希表的总长度，及原来总容量 4 int oldCap = (oldTab == null) ? 0 : oldTab.length; 5 // 得到原来最佳容量 6 int oldThr = threshold; 7 // 存放新的总容量、新最佳容量的变量 8 int newCap, newThr = 0; 9 if (oldCap > 0) { 10 // 原来总容量达到或超过HashMap的最大容量，则最佳容量设置为int类型的最大值 11 // 且原来容量不变，直接返回，不做后需调整 12 if (oldCap >= MAXIMUM_CAPACITY) { 13 threshold = Integer.MAX_VALUE; 14 return oldTab; 15 } 16 // 让新的总容量等于原来容量的二倍 17 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 18 oldCap >= DEFAULT_INITIAL_CAPACITY) 19 // 新的最佳容量也变为原来的二倍 20 newThr = oldThr << 1; 21 } 22 // 原来总容量为0，将新的总容量设置为最佳容量，构造方法出入参数是一个派生的Map的时候，就会使用派生的Map计算出新的最佳容量 23 else if (oldThr > 0) 24 newCap = oldThr; 25 else { 26 // 原来总容量和原来最佳容量都没有定义 27 // 新的总容量设为默认值16 28 // 新的最佳容量=默认负载因子×默认容量=0.75×16=12 29 newCap = DEFAULT_INITIAL_CAPACITY; 30 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 31 } 32 // 判断上述操作后新的最佳容量是否计算，若没有，就利用负载因子和新的总容量计算 33 if (newThr == 0) { 34 float ft = (float)newCap * loadFactor; 35 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 36 (int)ft : Integer.MAX_VALUE); 37 } 38 // 更新当前的最佳容量 39 threshold = newThr; 40 @SuppressWarnings({"rawtypes","unchecked"}) 41 // 生成新的哈希表，即一维数组 42 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 43 // 更新哈希表 44 table = newTab;
可以看出上述操作仅仅是生成了一张大小合适的哈希表，但表还是空的，后面的操作就是把以前的表中的元素重新排列，移动到当前表中合适的位置！
第二部分将原表元素移动到新表合适的位置：
1 // 先判断原表是或否为空 2 if (oldTab != null) { 3 // 遍历原表（一维数组）中的所有元素， 4 for (int j = 0; j < oldCap; ++j) { 5 // 记录原来一维数组中下标为j的元素 6 Node<K,V> e; 7 // 只对有效元素进行操作 8 if ((e = oldTab[j]) != null) { 9 //将原表中的元素置空 10 oldTab[j] = null; 11 if (e.next == null) 12 // 当前元素没有后继，那么直接把它放在新表中合适位置 13 // 其中e.hash & (newCap - 1)在我上一篇博客有介绍 14 // 就是以该节点的hash值和新表总容量取余，将余数作为下标 15 newTab[e.hash & (newCap - 1)] = e; 16 else if (e instanceof TreeNode) 17 // 当前元素有后继，且后继是红黑树 18 // 进行有关红黑树的相应操作 19 // 这里不详细介绍红黑树的操作 20 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 21 else { 22 // 这里就进行有关链表的移动 23 // 这两组结点变量，分别代表两条不同链表的头和尾 24 // 低位的头和尾 25 Node<K,V> loHead = null, loTail = null; 26 // 高位的头和尾 27 Node<K,V> hiHead = null, hiTail = null; 28 // 下一节点 29 Node<K,V> next; 30 do { 31 // 让next等于当前结点的后继结点 32 next = e.next; 33 // 这个位运算实际上判断的是该节点在新表中的位置是否发生改变 34 // 成立则说明没有改变，还是原来表中下标为j的位置 35 if ((e.hash & oldCap) == 0) { 36 // 若是首结点，则让低位的头等于当前结点 37 if (loTail == null) 38 loHead = e; 39 else 40 // 若不是首结点，则让低位的尾等于当前结点 41 loTail.next = e; 42 // 让低位的尾移动到当前 43 loTail = e; 44 } 45 // 这里就说明其在新表中的位置发生了改变，则要将其放入另一条链表 46 else { 47 // 若是首结点，则让高位的头等于当前结点 48 if (hiTail == null) 49 hiHead = e; 50 else 51 // 若不是首结点，则让高位的尾等于当前结点 52 hiTail.next = e; 53 // 让高位的尾移动到当前 54 hiTail = e; 55 } 56 } while ((e = next) != null); 57 // 原来位置的这条链表还存在 58 if (loTail != null) { 59 // 置空低位的尾的next 60 loTail.next = null; 61 // 将该链表的头结点放入新表下标为j的位置，即原表中的原位置 62 newTab[j] = loHead; 63 } 64 // 新位置上的链表存在 65 if (hiTail != null) { 66 // 置空高位的尾的next 67 hiTail.next = null; 68 // 将该链表的头结点放入新表中下标为j+原表长度的位置 69 newTab[j + oldCap] = hiHead; 70 } 71 } 72 } 73 } 74 } 75 return newTab;
链表的移动如图：
可以看出，这个方法可以使得单个结点重新散列，链表可以拆分成两条，红黑树重新移动，这样使得新的哈希表分布比以前均匀！
下面来分析put方法：
源码如下：
1 public V put(K key, V value) { 2 return putVal(hash(key), key, value, false, true); 3 }
这里我们可以知道其调用了内部的一个putVal方法：
首先第一个参数是通过内部的hash方法（在前一篇博客有介绍过）计算出键对象的hash（int类型）值，再把key和value对象传过去，置于后面两个参数先不着急
先来看下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 * // 看以看出，put方法传入的onlyIfAbsent是false，那么就会改变原来已存在的值 8 * @param onlyIfAbsent if true, don't change existing value 9 * // 这个参数先不考虑，往后慢慢分析 10 * @param evict if false, the table is in creation mode. 11 * @return previous value, or null if none 12 */ 13 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
该方法内容：
1 // 用于保存原表 2 Node<K,V>[] tab; 3 // 保存下标为hash的结点 4 Node<K,V> p; 5 // n用来记录表长 6 int n, i; 7 // 先检查原表是否存在，或者是空表 8 if ((tab = table) == null || (n = tab.length) == 0) 9 // 如果为空就生成一张大小为16的新表 10 n = (tab = resize()).length; 11 if ((p = tab[i = (n - 1) & hash]) == null) 12 // 如果以该方法形参hash对表长取余，令其作为下标的表中的元素为空，那么就产生一个新结点放在这个位置 13 tab[i] = newNode(hash, key, value, null); 14 else { 15 // 如果该结点不空，那么就会出现两种情况：链表和红黑树 16 Node<K,V> e; K k; 17 if (p.hash == hash && 18 ((k = p.key) == key || (key != null && key.equals(k)))) 19 // 如果当前结点的hash并且key值（指针值和内容值）相等，由于onlyIfAbsent是false，那么就会改变这个结点的V值，先用e将其保存起来 20 e = p; 21 else if (p instanceof TreeNode) 22 // 如果当前结点是一棵红黑树，那么就进行红黑树的平衡，这里不讨论红黑树的问题 23 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 24 else { 25 // 这里就对链表进行操作 26 // 从头开始遍历这条链表 27 for (int binCount = 0; ; ++binCount) { 28 if ((e = p.next) == null) { 29 // 如果该节点的next为空 30 // 就需要新增一个结点追加其后 31 p.next = newNode(hash, key, value, null); 32 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 33 // 这里进行红黑树阈值的判断，由于TREEIFY_THRESHOLD默认值是8，binCount是从0开始，那么当链表长度大于等于8的时候，就将该链表转换成红黑树，并且结束循环 34 treeifyBin(tab, hash); 35 break; 36 } 37 // 这里和之前的判断是一样的 38 if (e.hash == hash && 39 ((k = e.key) == key || (key != null && key.equals(k)))) 40 break; 41 // 让p = p->next 42 p = e; 43 } 44 } 45 // 若e非空，则就是说明原表中存在hash值相等，且key的值或内容相同的结点 46 if (e != null) { 47 // 将原来的V值保存 48 V oldValue = e.value; 49 // 判断是否是需要进行覆盖原来V值的操作 50 if (!onlyIfAbsent || oldValue == null) 51 // 覆盖原来的V值 52 e.value = value; 53 // 这个方法是一个空的方法，预留的一个操作，不用去管它 54 afterNodeAccess(e); 55 // 由于在这里面的操作只是替换了原来的V值，并没有改变原来表的大小，直接返回oldValue 56 return oldValue; 57 } 58 } 59 // 操作数自增 60 ++modCount; 61 // 实际大小自增 62 // 若其大于最佳容量进行扩容的操作，使其分布均匀 63 if (++size > threshold) 64 resize(); 65 // 这也是一个空的方法，预留操作 66 afterNodeInsertion(evict); 67 // 并没有替换原来的V值，返回null 68 return null;
下来是get方法，逻辑相对简单不难分析：
1 public V get(Object key) { 2 Node<K,V> e; 3 return (e = getNode(hash(key), key)) == null ? null : e.value; 4 }
同样也是通过hash方法计算出key对象的hash值，调用内部的getNode方法：
1 final Node<K,V> getNode(int hash, Object key) { 2 // 记录表对象 3 Node<K,V>[] tab; 4 // 记录第一个结点和当前节点 5 Node<K,V> first, e; 6 // 记录表长 7 int n; 8 // 记录K值 9 K k; 10 // 表非空或者长度大于0才对其操作 11 // 并且key的hash值对表长取余为下标，其所对应的哈希表中的结点存在 12 if ((tab = table) != null && (n = tab.length) > 0 && 13 (first = tab[(n - 1) & hash]) != null) { 14 // 当前结点满足情况，直接返回给该节点 15 if (first.hash == hash && 16 ((k = first.key) == key || (key != null && key.equals(k)))) 17 return first; 18 // 后面就分为两种情况：在红黑树或者链表中查找 19 if ((e = first.next) != null) { 20 // 当前结点是红黑树，进行红黑树的查找 21 if (first instanceof TreeNode) 22 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 23 // 进行链表的遍历 24 do { 25 if (e.hash == hash && 26 ((k = e.key) == key || (key != null && key.equals(k)))) 27 return e; 28 } while ((e = e.next) != null); 29 } 30 } 31 return null; 32 }
若有不足还请指出！
我在CSDN也放了一篇【Java】HashMap源码分析——常用方法详解
版权声明：本文为a526583280原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。