展开

关键词

HashMap扩容机制

HashMap扩容机制 上一期已经讲到了添加元素的put方法了,现在回顾一下put方法,主要讲解扩容方法: ? 调用的是putVal方法: ? final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // oldTable 为null的话说明这个HashMap 0 : oldTab.length; // 用来判断是否扩容的阀值,如果没被初始化过的HashMap这个oldCap是为0的 int oldThr = threshold; int newCap , newThr = 0; // oldCap > 0说明是已经使用过的HashMap现在添加元素导致产生扩容 if (oldCap > 0) { // 旧容量如果大于 MAXIMUM_CAPACITY 的扩容机制啦,感谢您宝贵的时间!

76110

HashMap扩容机制解析

HashMap初始化和第一次put()元素后,来研究一下探讨它的扩容机制。 通过查看Java JDK1.8putVal()源码可看到,有两种情况可能会触发扩容扩容时机 第一种情况:当HashMap第一次调用put方法时。 第二种情况:当存储在HashMap中元素的实际长度大于扩容临界值时。 什么是存储在HashMap中元素的实际长度? HashMap扩容临界值是通过变量threshold表示,它是通过当前底层数组长度*加载因子得到的。加载因子在上一篇中已经介绍过了,这里就不多说了。 扩容逻辑 如下进入resize()方法。 HashMap第一次扩容。 至此HashMap扩容机制解析完毕,有兴趣的各位可以使用下面代码打断点进行debug查看扩容流程。

8510
  • 广告
    关闭

    【玩转 Cloud Studio】有奖调研征文,千元豪礼等你拿!

    想听听你玩转的独门秘籍,更有机械键盘、鹅厂公仔、CODING 定制公仔等你来拿!

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    Java之HashMap扩容

    扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素,方法是使用一个新的数组代替已有的容量小的数组 核心代码如下 void resize(int newCapacity) { //传入新的容量 Entry[] oldTable = table; //引用扩容前的Entry 当前hashmap数据如下,我们加载因子我们设为1,那么hashmap容量已经达到阈值了,再添加数据则需要扩容。 image.png 扩容如下。 image.png 那我们就开始重新安置原本hashmap里面数据的位置吧。 image.png 扩容基本完成。

    16520

    HashMap扩容拾遗

    JDK8中HashMap扩容涉及到的加载因子和链表转红黑树的知识点经常被作为面试问答题,本篇将对这两个知识点进行小结。 默认加载因子为什么选择0.75 HashMap有两个参数影响其性能:初始容量和加载因子。容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。 加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。 当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行扩容、rehash操作(即重建内部数据结构),扩容后的哈希表将具有两倍的原容量。 在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少rehash操作次数,所以,一般在使用HashMap时建议根据预估值设置初始容量,减少扩容操作。

    25920

    HashMap hash碰撞 扩容 全解

    image.png 我们插入的元素为第13个元素,触发resize()重新分配元素 image.png 我们的旧值为: oldCap = 16 //最大容量 oldthr = 12 //触发扩容阈值 通过上述方法扩容之后: newCap = 32 newThr = 24 image.png 此时重新分配数组上面的链表节点元素 ,把旧节点数组的不为空的头节点全部置空, 当其没有next节点时,为其在

    20610

    6.HashMap扩容 resize() 原理

    6.HashMap扩容 resize() 原理 我们先来上一段测试代码,直观感受一下 HashMap 的真实的扩容过程: package i import java.util.* /** * @author: Jack * 2020-03-21 21:55 */ fun main(args: Array<String>) { val map = HashMap<String

    53730

    HashMap扩容机制—resize()「建议收藏」

    HashMap扩容机制—resize() 什么时候扩容:当向容器添加元素的时候,会判断当前容器的元素个数,如果大于等于阈值(知道这个阈字怎么念吗? 扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。 扩容时,遍历hashmap每个bucket里的链表,每个链表可能会被拆分成两个链表,不需要移动的元素置入loHead为首的链表,需要移动的元素置入hiHead为首的链表,然后分别分配给老的buket和新的 补充一下jdk 1.8中,HashMap扩容时红黑树的表现 扩容时,如果节点是红黑树节点,就会调用TreeNode的split方法对当前节点作为跟节点的红黑树进行修剪 ... else if (e instanceof 小结 (1) 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容

    7920

    Hashmap实现原理及扩容机制详解

    目录 HashMap基础 HashMap实现原理 Node和Node链 拉链法 关于Node数组 table 散列算法 HashMap和红黑树 关于TreeNode 红黑树基础 HashMap扩容机制 JDK1.7下的扩容机制 JDK1.8下的扩容机制 ---- HashMap基础 HashMap继承了AbstractMap类,实现了Map,Cloneable,Serializable接口 HashMap 中元素数超过容量*加载因子时,HashMap会进行扩容。 (JDK1.8) 5,如果添加元素之后,HashMap总节点数超过了阈值,则HashMap会进行扩容HashMap扩容机制 当HashMap决定扩容时,会调用HashMap类中的resize(int newCapacity)方法,参数是新的table长度。

    16720

    HashMap 如何解决冲突?扩容机制?

    正文 我们来看看HashMap的put数据的时候,是怎么处理的: /** * Implements Map.put and related methods * 的扩容 说道HashMap扩容,我们先来看看HashMap的resize()方法。 = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } 以上是针对链表结构的一个扩容。 loHead这部分表示的是在扩容之后,在table中的位置没有变动的数据,然后将他们拼装到链表中,然后在后面拼接到newTab[j]中。 hiHead这部分表示的是在扩容之后,位置有发生变动,然后将他们拼装的链表拼接到newTab[j + oldCap]中。 注意: 在我们这个Jdk1.8中,不会发生扩容的死循环.

    43220

    超硬核HashMap底层构成以及扩容原理

    (链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树.为啥这样可以解决冲突呢?因为数组扩容涉及到重新hash的问题.) Hashmap扩容因子选择的是0.75为啥呢? 主要是出于时间和空间上的考虑 如果我们选择扩容因子是1,那么每次使用完全部空间再扩容势必造成时间上的等待问题 如果我们选择扩容因子是0.5,那么每次使用一半就扩容,造成了每次都有一半的空间是浪费的. 多线程操作导致死循环问题 在多线程下,进行 put 操作会导致 HashMap 死循环,原因在于 HashMap扩容 resize()方法。 由于扩容是新建一个数组,复制原数据到数组。由于数组下标挂有链表,所以需要复制链表,但是多线程操作有可能导致环形链表。复制链表过程如下: 以下模拟2个线程同时扩容

    8620

    那么HashMap什么时候进行扩容呢?

    那么HashMap什么时候进行扩容呢? 当HashMap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。 也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为 2*16=32,即扩大一倍 ,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。 HashMap扩容的代码如下所示: //HashMap数组扩容 void resize(int newCapacity) { Entry

    20530

    八、JDK1.8中HashMap扩容机制

    七、JDK1.7中HashMap扩容机制 中介绍了JDK1.7中HashMap扩容机制及扩容过程中可能出现的死锁及数据丢失问题。 本篇文章我们将要介绍JDK1.8中HashMap扩容机制,并通过一个实例来展示链表的哈希扩容HashMap扩容机制-为什么负载因子默认为0.75f? 负载因子0.75 如果容量大大0.75则扩容为原来的两倍。 扩容因此 0.75 空间利用率和时间效率在0.75的时候达到了平衡。 首先总结一下JDK1.8的HashMap都在什么时候触发resize()方法,根据阅读源码总结了三个时机触发扩容,这里只做介绍,后面根据源码详细分析 HashMap是由数组+链表+红黑树构成的,数组就称之为桶了 ③当new完HashMap之后,第一次往HashMap进行put操作的时候,首先会进行扩容

    7020

    Java - HashMap扩容为什么选用2倍

    做除余的时候2的倍数可以直接使用&进行快速计算 例如: 19%16可以写成19&(16-1),位运算更高效 扩容的时候只移动大约一半的数据,并且不会造成扩容之后碰撞更加严重的情况 例如: hash 值为4和8的值存放在size为4的数组中,则两个元素都存放在0下标的数据中,当以2倍扩容时,size变为8,8依然存放在0下标位置上,而4移动到下标为4的位置上,这样不仅达到了扩容的效果,还减少了hash

    65840

    HashMap的put kv,是如何扩容的?

    刘志航 1、描述下HashMap put(k,v)的流程? 2、它的扩容流程是怎么样的? 1 HashMap put(k,v)流程 ? 相等则需要操作的就是该node 判断当前节点是否为TreeNode,对TreeNode进行操作,并返回结果e 如果是链表则遍历链表,key存在则返回节点e,不存在则赋值 判断节点e有没有被赋值,覆盖旧值 hashMap // 声明Node数组tab, Node节点 Node<K,V>[] tab; Node<K,V> p; int n, i; // 对tab数组赋值为当前HashMap 的table, 并判断是否为空, 或者长度为0 // 为0则进行resize()数组, 并对 n赋值为当前tab的长度 // resize() 对HashMap的table else { // zero initial threshold signifies using defaults // 旧数组不存在, new HashMap

    19240

    HashMap - 为什么数组扩容是二倍

    增加运算效率 扩容时使用位运算<<,计算除余时使用(n-1)&hash,这些位运算都可以增加效率 2. 减少扩容后数据移动造成的hash冲突增多,并且数据迁移减少一半,同时方便操作 改变数据长度之后,原来存储的数据需要重新计算数组下标,找到新的存储位置,如果数组长度设置不当,则容易出现扩容之后,反而造成 hash冲突变多,这样扩容就没有意义了。 当使用2的倍数进行扩容时,hash冲突只会减少,最坏的情况也就是hash冲突不变。 并且这种操作还可以对链表进行优化操作,通过计算新 下标>老数组长度 判断数据需不需要移动,这样整体只迁移一半的数据就完成了扩容。 ?

    44110

    jdk1.8 HashMap扩容机制变化「建议收藏」

    概述 JDK1.8中的HashMap较于前代有了较大的变更,主要变化在于扩容机制的改变。 在JDK1.7及之前HashMap扩容进行数组拷贝的时候采用的是头插法,因此会造成并发情景下形成环状链表造成死循环的问题。JDK1.8中改用了尾插法进行数组拷贝,修复了这个问题。 其次,JDK1.8开始HashMap改用数组+链表/红黑树组合的数据结构来提高查询效率,降低哈希冲突产生的链表过长导致的查询效率减缓现象。 本文的主要内容是对JDK1.8中的扩容机制与前代进行比较。 如下图所示: JDK1.8中的扩容 JDK1.8中将transfer()方法的操作也放入了resize()方法中,而由于JDK1.8引入了红黑树的结构,扩容的操作看起来也更加复杂。 具体推演过程见 (2条消息) HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导_Dylanu的博客-CSDN博客_e.hash https://blog.csdn.net

    7610

    【优雅的避坑】避免HashMap扩容的正确姿势

    :17 通过运行结果发现: 设置了初始容量的hashMap,其初始容量并不是我指定的1000000,而是1048576(2^20) hashMap的容量并不是固定不变的,当达到扩容条件时会进行扩容,从 )时,hashMap依然会扩容1次 为什么会酱紫呢? 带着上面的三个发现,来看一下HashMap扩容机制。 HashMap扩容机制 先看一下HashMap的几个成员变量: ? 同样能使HashMap不用扩容! 小结 设置了初始容量的hashMap,其真实初始容量并不一定是指定的数值,而是HashMap内部计算过的 hashMap的容量并不是固定不变的,当达到扩容条件时会进行扩容,从 16 扩容到 32、64、

    36610

    深入理解 HashMap扩容机制:resize 过程详解

    首先是put()方法 public V put(K key, V value) {     //判断当前Hashmap(底层是Entry数组)是否存值(是否为空数组)     if (table == threshold);//如果为空,则初始化     }          //判断key是否为空     if (key == null)       return putForNullKey(value);//hashmap ;     //判断是否有超出扩容的最大值,如果达到最大值则不进行扩容操作     if (oldCapacity == MAXIMUM_CAPACITY) {       threshold = Integer.MAX_VALUE     // transfer()方法把原数组中的值放到新数组中     transfer(newTable, initHashSeedAsNeeded(newCapacity));     //设置hashmap 扩容后为新的数组引用     table = newTable;     //设置hashmap扩容新的阈值     threshold = (int)Math.min(newCapacity * loadFactor

    74340

    JDK1.8HashMap源码学习-put操作以及扩容(二)

    “本文将主要介绍HashMap的put操作以及相应的扩容。” 相关阅读: JDK1.8HashMap源码学习-数据结构 JDK1.8HashMap源码学习-初始化 JDK1.8HashMap源码学习-put操作以及扩容(一) 01 — 红黑树化 当我们继续向编号 ,通过数组扩容为原先的两倍达到减少桶中节点数的目的。 03 — 树的裁剪 我们看下针对根节点是红黑树是如何进行扩容裁剪的。 最后说一个面试的知识点,我们都知道HashMap是非线程安全,那什么情况下是非线程安全的呢?一个是在初始化双put一个是在扩容的时候。 记得关注哦,关注木左不迷路,木左带你上高速!

    16350

    JDK1.8HashMap源码学习-put操作以及扩容(一)

    “本文将主要介绍HashMap的put操作以及相应的扩容。” 前文链接地址: JDK1.8HashMap源码学习-数据结构 JDK1.8HashMap源码学习-初始化 我们先看下HashMap的hash方法。在之后的源码阅读中会经常看到。 在退出循环后,如果是已存在的key,根据条件判断是否覆盖原值,HashMap是覆盖原值并返回旧值。最后完成的是统一操作,数组变更次数加1和容量值加1以及判断是否扩容。 如果没有则直接进行原数组长度左移1位,即扩容为原先的两倍,接着做了判断,如果新数组的长度小于数组长度最大值且旧数组长度大于等于默认值16,则阀值也直接左移一位,扩容为原先的两倍。 这也是为什么扩容的时候直接扩容为2倍。非常容易操作,而节点也可以均匀的分布在各个桶中。 此时我们的数据结构下图 ? 就这样一直向编号6的桶中增加值,直到数组长度达到64。

    21230

    相关产品

    • 服务注册中心

      服务注册中心

      服务注册中心(service registry center,src)支持多种主流注册中心组件托管(consul、eureka、zookeeper),为您提供服务及服务实例可视化管理、数据管理等能力,

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券