精华内容
下载资源
问答
  • HashMap扩容机制

    2021-01-18 20:05:14
    HashMap扩容机制 hashMap的扩容机制主要是在resize方法中进行实现,我们来看源码并进行解析: final Node<K,V>[] resize() { //把扩容前的具体值table用临时变量oldTab 进行存储 Node<K,V>[] oldTab =...

    HashMap扩容机制

    hashMap的扩容机制主要是在resize方法中进行实现,我们来看源码并进行解析:

    final Node<K,V>[] resize() {
            //把扩容前的具体值table用临时变量oldTab 进行存储
            Node<K,V>[] oldTab = table; 
            //获取扩容前的容量
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            //threshold为触发扩容的值:HashMap的size大于threshold时会执行resize操作
            //阈值又等于容量乘以加载因子
            //threshold=capacity*loadFactor
            //用临时变量存放原始阈值
            int oldThr = threshold;
            //新的容量值,新的扩容阀界值
            int newCap, newThr = 0;
            //如果扩容前容量大于0
            if (oldCap > 0) {
                 //如果扩容前容量大于等于1073741824这个值,则最大容量就是原始容量,
                 //设置阈值为1073741824
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //如果原始容量的2倍小于最大限制容量且原始容量大于16
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //新容量就是原始容量的2倍
                    newThr = oldThr << 1; // double threshold 
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
              //进入此if,说明map当前容量为0,正在进行有参构造初始化
              //public HashMap(int initialCapacity)或 
              //public HashMap(int initialCapacity, float loadFactor)进行初始,
              //计算this.threshold = tableSizeFor(initialCapacity);
                newCap = oldThr;
            else {    // zero initial threshold signifies using defaults
                 //进入此if,说明map当前容量为0,正在进行无参构造初始化
                 //设置容量为DEFAULT_INITIAL_CAPACITY=16
                newCap = DEFAULT_INITIAL_CAPACITY;
                 //设置阈值为12=0.75*16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
               //进入此判断1.oldCap > 0满足  后面两个if都不满足
               //         2 oldThr > 0,这两种情况都会使newThr =0;
               //计算出新容量对应的阈值
                float ft = (float)newCap * loadFactor;
               //如果新容量小于最大容量且计算的阈值也小于最大容量,阈值就为计算出的值,
               //否则为最大容量
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            //修改当前对象的阈值为新容量的阈值
            threshold = newThr;
            //实例化一个新的容量的table(Node数组)
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            //把原始table赋值为新容量
            table = newTab;
            //如果原始对象不为空,就需要重新进行元素的定位,说明是正在扩容
            if (oldTab != null) {
                //遍历元素数据,获取每一个下标数据
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    //判断下标值是否为空
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        //如果下标值没有子节点
                        if (e.next == null)
                            //下标值得hash值与数组长度-1取模,减一是因为下标从0开始
                            //e.hash & (newCap - 1)得到新的下标位置
                            //然后就把当前值放到新容量的下标中
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                             //如果下标值是TreeNode子类,说明是树结构,然后把树节点进     行hash计算取模得到新的下标值
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            //这里就是对链表结构的子节点进行重新分配位置
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            //用了循环获取子节点,对每一个节点进行hash取模得到新的位置
                            do {
                                //临时变量存放子节点,每个子节点都会用到此变量
                                next = e.next;
                                //确定下标是用(e.hash & oldCap-1),而这里是对没有减一  
                                //结果只有两种,一种为0,一种为oldCap,这里也是1.8修改的精髓之处 
                                //如oldCap=8,hash是3,11,19,27时,(e.hash & oldCap)
                                //的结果是0,8,0,8,这样3,19组成新的链表,index为3;
                                //而11,27组成新的链表,新分配的index为3+8
                                //因此1.7中经过resize后数据的顺序变成了倒序,而1.8没有改变顺序,原因就是因为这里-1
                                if ((e.hash & oldCap) == 0) { 
                                    //3,19进这
                                    //这里就是判断尾节点是不是空,因为第一个节点来,
                                    //值赋值给头结点,也同时赋值给尾节点,第一个值即头即尾
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                 //11,27进这,与上面同理
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            //然后就把当前节点中拆分为的两个链表分配在新的hashMap中
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }
    
    展开全文
  • Hashmap扩容机制

    2019-09-18 13:55:29
    HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中...

    当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置。
     

    转载于:https://my.oschina.net/u/4085644/blog/3020448

    展开全文
  • HashMap 扩容机制

    2020-09-07 12:59:34
    HashMap在1.7 和1.8 做了比较大的改变 1.7之前使用的就是数组 + 链表,它数据节点是一个Entry 节点,它的一个内部类;1.7之前它的数据插入过程是使用了头插入,头插入法虽然效率比较高,但在resize拓过程时,反复...

    HashMap在1.7 和1.8 做了比较大的改变

    1.7之前使用的就是数组 + 链表,它数据节点是一个Entry 节点,它的一个内部类;1.7之前它的数据插入过程是使用了头插入,头插入法虽然效率比较高,但在resize拓容过程时,反复调用一个transfer的方法,把里面的一些Entry进行一个rehash,可能会造成链表的循环,就可能在下一次Get的时候出现一个死循环的情况;1.7没有加锁,也可能在多线程并发的情况下,数据不能保证它是一个安全的,就是我push的进去的值,取出来还是我push进去的一个值

    jdk1.8 升级为,数组 + 链表/ 红黑树,把原来一个Entry节点也变成了一个Node节点。它的整个put的过程也做了优化,1.8是尾插入;

    HashMap中的链表什么时候转化为红黑树?

    1.链表长度大于8,官方源码如下:

    2.当满足条件1以后调用treeifyBin方法转化红黑树。该方法中,数组如果长度小于MIN_TREEIFY_CAPACITY(64)就选择扩容,而不是转化为红黑树 


    TreeNodes(红黑树)占用空间是普通Nodes(链表)的两倍,为了时间和空间的权衡。

    节点的分布频率会遵循泊松分布,链表长度达到8个元素的概率为0.00000006,几乎是不可能事件.

    为什么转化为红黑树的阈值8和转化为链表的阈值6不一样,是为了避免频繁来回转化

     

    文章最后,给大家推荐一些受欢迎的技术博客链接

    1. JAVA相关的深度技术博客链接
    2. Flink 相关技术博客链接
    3. Spark 核心技术链接
    4. 设计模式 —— 深度技术博客链接
    5. 机器学习 —— 深度技术博客链接
    6. Hadoop相关技术博客链接
    7. 超全干货--Flink思维导图,花了3周左右编写、校对
    8. 深入JAVA 的JVM核心原理解决线上各种故障【附案例】
    9. 请谈谈你对volatile的理解?--最近小李子与面试官的一场“硬核较量”
    10. 聊聊RPC通信,经常被问到的一道面试题。源码+笔记,包懂
    11. 深入聊聊Java 垃圾回收机制【附原理图及调优方法】

    欢迎扫描下方的二维码或 搜索 公众号“大数据高级架构师”,我们会有更多、且及时的资料推送给您,欢迎多多交流!

                                               

           

    展开全文
  • hashMap扩容机制

    千次阅读 2017-08-23 15:46:40
    扩容时空间大小变化:  HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数,具体证明可以...

    扩容时空间大小变化:

             HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),这是一种非常规的设计,常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数,具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159,       Hashtable初始化桶大小为11,就是桶大小设计为素数的应用(Hashtable扩容后不能保证还是素数)。

             HashMap采用这种非常规设计,主要是为了在取模和扩容时做优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,也加入了高位参与运算的过程。

     

     

     

    初始容量(默认)

    最大容量

    扩容时倍数

    加载因子

    hashtable

    11

     

    newCapacity=

       (oldCapacity *2) + 1;

    0.75

    hashmap

    2^4

    2^30

    *2

    0.75

    hashMap用户自定义长度时,底层会设置长度为大于等于用户提供数的2 的倍数;

     

     

    扩容时数据的重新分布:


    jdk1.8

             当table需要扩容时,扩容后的table大小变为原来的两倍,接下来就是进行扩容后table的调整:

             假设扩容前的table大小为2的N次方,有put方法解析可知,元素的table索引为其hash值的后N位确定

             那么扩容后的table大小即为2的N+1次方,则其中元素的table索引为其hash值的后N+1位确定,比原来多了一位

             因此,table中的元素只有两种情况:

                       元素hash值第N+1位为0:不需要进行位置调整

                       元素hash值第N+1位为1:调整至原索引+N;

             在resize方法中,第45行的判断即用于确定元素hashi值第N+1位是否为0:

             若为0,则使用loHead与loTail,将元素移至新table的原索引处

             若不为0,则使用hiHead与hiHead,将元素移至新table的两倍索引处

    扩容或初始化完成后,resize方法返回新的table

     

    展开全文
  • 集合类:HashMap扩容机制集合类:HashMap扩容机制 集合类:HashMap扩容机制 扩容:hashMap的初始容量是16,默认扩容因子0.75.扩容因子可在new的时候通过构造方法设置。hashmap每次扩容大小为原大小的2倍。当hashmap...
  • HashMap扩容机制(1.7/1.8)

    2021-03-18 16:47:26
    HashMap扩容机制(1.7/1.8) 当HashMap决定扩容时,会调用HashMap类中的resize(int newCapacity)方法,参数是新的table长度。在JDK1.7和JDK1.8的扩容机制有很大不同。 JDK1.7下的扩容机制 JDK1.7下的resize()方法是...
  • java8中HashMap扩容机制-结点的挂载java8扩容机制三级目录 java8扩容机制 三级目录
  • 待修改。。 一、扩容机制 HashMap是没有进行初始化容量,也就是现在是一个空的HashMap(容量为0),这是因为HashMap使用的懒加载机制。 HashMap就使用默认的初始化容量,也就是16...测试HashMap扩容机制:loadFacto...
  • -转化临界值三、HashMap扩容机制1.构造方法2.容量3.扩容总结 HashMap HashMap是一个用来存储键值对(key-value)的集合,键值都可使用null,并且键不能重复,每一个键值对都是一个Entry。 一、哈希表 1.简介 散...
  • HashMap扩容机制 将(k1,v1)直接放入Node类型的数组中,这个数组初始化容量是16,默认的加载因子是0.75,也就是当元素加到12的时候,底层会进行扩容,扩容为原来的2倍。 可能引发的问题: HashMap实际使用过程中会...
  • 必知必会--HashMap扩容机制

    千次阅读 2019-09-10 14:47:59
    这是因为多次put操作会引发HashMap扩容机制HashMap扩容机制采用头插法的方式移动元素,这样会造成链表闭环,形成死循环。JDK1.8中HashMap使用高低位来平移元素,这样保证效率的同时避免了多线程情...
  • java7和java8 hashmap扩容机制及区别

    千次阅读 2020-06-23 17:50:52
    (一) Java 7 中Hashmap扩容机制 一、什么时候扩容: 网上总结的会有很多,但大多都总结的不够完整或者不够准确。大多数可能值说了满足我下面条件一的情况。 扩容必须满足两个条件: 1、 存放新值的时候当前已...
  • HashMap扩容机制解读

    2021-04-24 18:32:44
    扩容机制 什么时候需要扩容: 当hashmap中的元素个数超过数组大小 * loadFactor(负载因子)时,就会进行数组扩容,loadFactor的默认值(DEFAULT_LOAD_FACTOR)是0.75这是一个折中的取值,也就是说,默认情况下数组...
  • 面试题:HashMap扩容机制

    千次阅读 2021-01-19 13:47:00
    扩容机制 1.什么时候才需要扩容 在首次调用put方法的时候,初始化数组table 当HashMap中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时,就会进行数组扩容,loadFactor的默认值(DEFAULT_LOAD_FACTOR)...
  • 前几天写了一篇,ArrayList扩容源码分析。好像源码也没有我们想象的那么可怕?(当然了,只是简单的分析,后面等我知识充足了,将进一步的分析) 今天本来想打游戏的,但是网速太差了,真是的是让人火爆。努力写代码...
  • java HashMap扩容机制

    2020-05-09 14:24:10
    jdk7源码: //1、判断当前个数是否大于等于阈值 //2、当前存放是否发生哈希碰撞 //如果上面两个条件否发生,那么就...Hashmap扩容需要满足两个条件:当前数据存储的数量(即size())大小必须大于等于阈值;当前加...
  • 扩容机制 新增方法(put) 总结 hashMap是基于Hash表的Map实现,存储的方式未key:value类型的键值对,同时允许key、value为null,如果出现像如同的key或者value十,新值将会覆盖之前的值。 使用 //初始化...
  • HashMap扩容机制以及尾插法

    千次阅读 2020-02-22 19:47:51
    HashMap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,...
  • 随笔--hashmap扩容机制

    2020-06-27 11:31:19
    今天看到了一个问题,关于hashmap扩容机制 网上有人说,hashmap数组扩容必须是原来数组长度两倍,这个没有问题,但是长度是两倍的原因是什么呢?有大佬说是因为再给要添加的节点计算其在数组中具体的下标位置时,...
  • JAVA中HashMap扩容机制

    2018-11-24 16:05:07
    第一部分: HashMap&lt;String, String&gt; hmap=new HashMap&lt;&gt;(); HashSet&lt;String&gt; hset=new HashSet&lt;&gt;(); Hashtable&...1. HashMap扩容   HashM...
  • JDK1.8 HashMap 扩容机制

    千次阅读 2019-10-04 19:04:36
    当然实际数组初始长度最小为 16, 不存在从 8 到 16 的扩容,只是为了好画图。 假设元素的 hash(key) = key Node 节点中存储的 hash 其实就是 key 的 hash 值 亦即:(key == null) ? 0 : (h = key.hashCode()) ...
  • 扩容算法:<<1,即*2 HashMap是先插入还是先扩容HashMap初始化后首次插入数据时,先扩容再插入数据,之后每当插入的数据个数达到阈值时就会发生扩容,此时是先插入数据再扩容
  • HashMap 扩容机制默认初始化指定初始化扩容触发条件重新散列 默认初始化 当HashMap 未初始化容量时,第一次put()添加元素,table数组未null,触发扩容机制,resize()会初始化table数组,默认值为16,阈值threshold为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,159
精华内容 12,463
关键字:

hashmap扩容机制