写点什么

HashMap 源码分析 —— 一篇文章搞定 HashMap 面试

发布于: 2021 年 11 月 07 日

//如果链表中没有最新插入的节点,将新放入的数据放到链表的末尾 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) {/


《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开:qq.cn.hn/FTe 免费领取
复制代码


/如果旧的容量已近达到最大值,则不再扩容,阈值直接设置为最大值 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 来说,逻辑实在是简单太多了


  1. 根据 hash 值查找到指定位置的数据

  2. 校验指定位置第一个节点的数据是 key 是否为传入的 key,如果是直接返回第一个节点,否则继续查找第二个节点

  3. 如果数据是 TreeNode(红黑树结构),直接通过红黑树查找节点数据并返回

  4. 如果是链表结构,循环查找所有节点,返回数据

  5. 如果没有找到符合要求的节点,返回 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;

评论

发布
暂无评论
HashMap源码分析 —— 一篇文章搞定HashMap面试