HashMap 源码分析 —— 一篇文章搞定 HashMap 面试
//如果链表中没有最新插入的节点，将新放入的数据放到链表的末尾 p.next = newNode(hash, key, value, null);
//如果链表过长，达到树化阈值，将链表转化成红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果链表中有新插入的节点位置数据不为空，则此时 e 赋值为节点的值，跳出循环 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}
//经过上面的循环后，如果 e 不为空，则说明上面插入的值已经存在于当前的 hashMap 中，那么更新指定位置的键值对 if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//如果此时 hashMap size 大于阈值，则进行扩容 if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
从代码看，put 方法分为三种情况：
table 尚未初始化，对数据进行初始化
table 已经初始化，且通过 hash 算法找到下标所在的位置数据为空,直接将数据存放到指定位置
table 已经初始化，且通过 hash 算法找到下标所在的位置数据不为空，发生 hash 冲突（碰撞），发生碰撞后，会执行以下操作：
判断插入的 key 如果等于当前位置的 key 的话，将 e 指向该键值对
如果此时桶中数据类型为 treeNode，使用红黑树进行插入
如果是链表，则进行循环判断， 如果链表中包含该节点，跳出循环，如果链表中不包含该节点，则把该节点插入到链表末尾，同时，如果链表长度超过树化阈值（TREEIFY_THRESHOLD）且 table 容量超过最小树化容量（MIN_TREEIFY_CAPACITY），则进行链表转红黑树（由于 table 容量越小，越容易发生 hash 冲突，因此在 table 容量<MIN_TREEIFY_CAPACITY 的时候，如果链表长度>TREEIFY_THRESHOLD,会优先选择扩容，否则会进行链表转红黑树操作）
首先分析 table 尚未初始化的情况：
1.2.1 table 尚未初始化
n = (tab = resize()).length;
从代码可以看出，table 尚未初始化的时候，会调用 resize()方法：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;
//1、table 已经初始化，且容量 > 0if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {/
/如果旧的容量已近达到最大值，则不再扩容，阈值直接设置为最大值 threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)//如果旧的容量不小于默认的初始容量，则进行扩容，容量扩张为原来的二倍 newThr = oldThr << 1; // double threshold}//2、阈值大于 0 threshold 使用 threshold 变量暂时保存 initialCapacity 参数的值 else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//3 threshold 和 table 皆未初始化情况，此处即为首次进行初始化//也就在此处解释了构造方法中没有对 threshold 和 初始容量进行赋值的问题 else { // zero initial threshold signifies using defaults//如果阈值为零，表示使用默认的初始化值//这种情况在调用无参构造的时候会出现，此时使用默认的容量和阈值 newCap = DEFAULT_INITIAL_CAPACITY;//此处阈值即为 threshold=initialCapacityloadFactornewThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// newThr 为 0 时，按阈值计算公式进行计算，容量负载因子 if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}
//更新阈值 threshold = newThr;
//更新数组桶 @SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;
//如果之前的数组桶里面已经存在数据，由于 table 容量发生变化，hash 值也会发生变化，需要重新计算下标 if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//如果指定下标下有数据 if ((e = oldTab[j]) != null) {//1、将指定下标数据置空 oldTab[j] = null;//2、指定下标只有一个数据 if (e.next == null)//直接将数据存放到新计算的 hash 值下标下 newTab[e.hash & (newCap - 1)] = e;//3、如果是 TreeNode 数据结构 else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//4、对于链表，数据结构 else { // preserve order//如果是链表，重新计算 hash 值，根据新的下标重新分组 Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}
resize 方法逻辑比较复杂，需要静下心来一步步的分析，但是总的下来，分为以下几步：
首先先判断当前 table 是否进行过初始化，如果没有进行过初始化，此处就解决了调用无参构造方法时候，threshold 和 initialCapacity 未初始化的问题，如果已经初始化过了，则进行扩容，容量为原来的二倍
扩容后创建新的 table，并对所有的数据进行遍历
如果新计算的位置数据为空，则直接插入
如果新计算的位置为链表，则通过 hash 算法重新计算下标，对链表进行分组
如果是红黑树，则需要进行拆分操作
1.3 get 方法，查找
put 方法分析完成之后，剩下的就很简单了，先看一下源码：
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
//1、根据 hash 算法找到对应位置的第一个数据，如果是指定的 key，则直接返回 if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;
if ((e = first.next) != null) {//如果该节点为红黑树，则通过树进行查找 if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//如果该节点是链表，则遍历查找到数据 do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}
get 方法相对于 put 来说，逻辑实在是简单太多了
根据 hash 值查找到指定位置的数据
校验指定位置第一个节点的数据是 key 是否为传入的 key，如果是直接返回第一个节点，否则继续查找第二个节点
如果数据是 TreeNode（红黑树结构），直接通过红黑树查找节点数据并返回
如果是链表结构，循环查找所有节点，返回数据
如果没有找到符合要求的节点，返回 null
在这个方法里面，需要注意的有两个地方：hash（key）和 hash 的取模运算 (n - 1) & hash
1.3.1 hash（key）的源码
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
这段代码叫做扰动函数，也是 hashMap 中的 hash 运算，主要分为下面几步：
key.hashCode()，获取 key 的 hashCode 值，如果不进行重写的话返回的是根据内存地址得到的一个 int 值
key.hashCode() 获取到的 hashcode 无符号右移 16 位并和元 hashCode 进行^ ，这样做的目的是为了让高位与低进行混合，让两者都参与运算，以便让 hash 值分布更加均匀
1.3.2 取模运算 (n - 1) & hash
在 hashMap 的代码中，在很多地方都会看到类似的代码：
first = tab[(n - 1) & hash])
hash 算法中，为了使元素分布的更加均匀，很多都会使用取模运算，在 hashMap 中并没有使用 hash%n 这样进行取模运算，而是使用(n - 1) & hash 进行代替，原因是在计算机中，&的效率要远高于 %；需要注意的是，只有容量为 2 的 n 次幂的时候，(n - 1) & hash 才能等效 hash%n，这也是 hashMap 初始化初始容量时，无论传入任何值，都会通过 tableSizeFor(int cap) 方法转化成 2 的 n 次幂的原因，这种巧妙的设计真的很令人惊叹； 至于为什么只有 2 的 n 次幂才能这样进行取模运算，这里就不再详细叙述了，有兴趣的可以看一下一位大佬写的文章：由HashMap哈希算法引出的求余%和与运算&转换问题
1.4 remove 方法，删除
了解完 get 方法之后，我们再最后了解一下 remove 方法：
public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;
//根据 key 和 key 的 hash 值，查找到对应的元素 if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}
//如果查找的了元素 node，移除即可 if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {//如果是 TreeNode，通过树进行移除 if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//如果是第一个节点，移除第一个节点，将 index 下标的位置指向第二个节点 else if (node == p)tab[index] = node.next;else//如果不是链表的第一个节点，则移除该节点 p.next = node.next;
评论