循序渐进分析源码之 HashMap put 方法的示例分析
循序渐进分析源码之 HashMap put 方法的执行流程(jdk 1.8 )的示例分析,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
预备知识
注意:这里不会讲红黑树是什么,以及如何具体实现。我们只需知道它长什么样子并了解它的好处即可。
为什么 在jdk1.8 中采用数组+链表/红黑树的数据结构存储数据?
当 Hash 冲突严重时,在数组上的链表会越来越长,此时就会会降低查询时的效率;时间复杂度为 O(N)。 引入红黑树之后查询效率直接提高到了 O(logn)。
引入红黑树后,HashMap 内部数据结构长什么样子?
什么时候会采用链表,什么时候用红黑树?
当链表的大小大于预设的阈值(8)时就要转换为红黑树
put 方法源码(带注释)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; // 局部变量,指向容器 Node<K,V> p; // 局部变量 int n, i; // 1. 如果 HashMap 没有初始化,需要进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2. 根据计算出的元素所在数组中的位置,并判断目标位置是否为空 // 2.1 如果为空. new 一个新的 Node 放置在目标位置 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 2.2 如果不为空, 再分情况讨论 else { Node<K,V> e; K k; // 2.2.1 如果目标位置有值(有可能是红黑树的根节点,也有可能是链表的表头),就比较key 是否相同(相当于提前判断吧) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 2.2.2 如果目标位置放的是一个红黑树,就按照红黑树的方式,写入数据 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 2.2.3 如果目标位置放置的是一个链表,就遍历整个链表。 else { for (int binCount = 0; ; ++binCount) { // 如果当前节点的下一个节点为空,就 new 一个新的节点,然后当前节点指向这个新节点 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 对这个增加了一个节点的链表进行长度判断,如果长度大于阀值,就将链表转成红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果当前节点的下一个节点不为空,就要判断 key 是否相同,如果相同,就跳出循环。 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 对 2.2.1 和 2.2.2 和 2.2.3 进行判断。判断成立表示要覆盖原有位置的元素。 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // 下面是扩容代码,暂时忽略 ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
put 方法的流程图
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注行业资讯频道,感谢您对亿速云的支持。