精华内容
下载资源
问答
  • 容后传
    千次阅读
    2021-06-30 15:01:06

    问题:ArrayList数组是怎么扩容,扩容的特点,能扩容到多少

    源码分析

    1. ArrayList默认容量为10,没有加载因子,一次最大扩容为16。
    2. 无参数构造方法创建 ArrayList 时,实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为10。DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示的是空的数组对象。
    3. 有参构造:
      第一种:传int参数
      如果这个初始化参数大于0,那么就会设置对象大的数组存储区的容量大小与初始化参数相等。
      如果初始化参数等于0,那就返回EMPTY_ELEMENTDATA的空数组。
      第二种:传Collection
      首先,将Collection转化成数组,赋值给elementData,如果size不为0,那么就判断elementData是不是属于Object数组(这是为了避免出现在集合转数组时可能存在不返回Object数组的情况)。
      如果size为0,那就返回EMPTY_ELEMENTDATA的空数组。

    小结:

    • EMPTY_ELEMENTDATA 表示的是我们在指定size为0的时候的空数组。
    • DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示的一个默认的数组,一个空数组,没有特别指定它的size为0,它处于一个默认的、空的状态。

    扩容机制:

    1. ArrayList扩容发生在add()方法调用的时候, 调用ensureCapacityInternal()来扩容的,通过方法calculateCapacity(elementData, minCapacity)获取需要扩容的长度。
    2. ensureExplicitCapacity方法可以判断是否需要扩容:
      2.1 首先进行判断是否大于默认容量10
      2.2 如果,小于默认容量10,直接在原来基础上+1,元素添加完毕
      2.3 如果,大于默认容量10,则需要进行扩容,扩容核心是 grow()方法
    3. ArrayList扩容的关键方法grow():
      获取到ArrayList中elementData数组的内存空间长度 扩容至原来的1.5倍
      3.1 扩容之前,首先创建一个新的数组,且旧数组被复制到新的数组中,这样就得到了一个全新的副本,我们在操作时就不会影响原来数组了。
      3.2 然后通过位运算符,将新的容量更新为旧容量的1.5倍。
      3.3 如果新的容量-minCapacity<=0,就拿新的容量-最大容量长度如果<=0的,那么最终容量=最大容量长度。
      3.4 如果新的容量-minCapacity>0,那么最终容量=新的容量。
    4. 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间。

    从此方法中我们可以清晰的看出其实ArrayList扩容的本质就是计算出新的扩容数组的size后实例化,并将原有数组内容复制到新数组中去。

    (例如:添加的容量为15,则minCapacity=15,15-16<=0,那么最终容量就是16。)

    (例如:添加的容量为11,则minCapacity=11,15-11>0,那么最终容量就是15。)

    特点:

    • ArrayList有自动扩容机制,它至少会保障这个数组的最小容量和你的数组大小一致,但是ArrayList的扩容机制并不是完全确定的,而且每次添加一个元素会消耗特定不变的缓冲时间。
    更多相关内容
  • HashMap扩容后,元素是如何重新分布的

    千次阅读 多人点赞 2020-09-10 11:39:08
    2、当元素增多导致扩之后,元素是如何重新分布的 同样,为了方便读者复盘,我截取源码是尽量将行号带上。 jdk版本还是1.8 结构图 再重复一遍,HashMap的底层数据结构为数组+链表+红黑树的结构,放一个HashMap的...

    上文回顾

    在上文深入源码分析HashMap到底是怎样将元素put进去的

    我们着重分析了无参构造函数是如何创建map对象和HashMap是如何将第一个元素puttable的。

    此篇重点

    这篇我们将逐行代码分析

    1、有参构造函数是如何创建map对象的
    2、当元素增多导致扩容之后,元素是如何重新分布的

    同样,为了方便读者复盘,我截取源码是尽量将行号带上。

    jdk版本还是1.8

    结构图

    再重复一遍,HashMap的底层数据结构为数组+链表+红黑树的结构,放一个HashMap的结构示意图,有个大致印象。
    在这里插入图片描述

    解剖思路

    创建一个有参构造函数,并往其中添加若干元素,直至触发扩容机制

    为了方便方便计算hash值,key和value都选用比较小的字符串

    关于调试键的使用请参照:IDEA调试键的说明,在此不再赘诉

    调试代码

    public static void main(String[] args) {
    
            System.out.println("★★★★★★解剖开始★★★★★★");
    
            HashMap<String, String> map = new HashMap<>(12);
    
            map.put("1", "1");
            map.put("2", "2");
            map.put("3", "3");
            map.put("4", "4");
    
            // 实验key相同的情况
            map.put("4", "D");
    
            map.put("5", "5");
            map.put("6", "6");
            map.put("7", "7");
            map.put("8", "8");
            map.put("9", "9");
            map.put("10", "10");
            map.put("11", "11");
            map.put("12", "12");
    
            // 第一个扩容点
            map.put("13", "13");
            map.put("14", "14");
            map.put("15", "15");
            map.put("16", "16");
    
            map.put("17", "17");
            map.put("18", "18");
            map.put("19", "19");
            map.put("20", "20");
    
            map.put("21", "21");
            map.put("22", "22");
            map.put("23", "23");
            map.put("24", "24");
    
            //第二个扩容点
            map.put("25", "25");
    
    
        }
    
    

    断点打在第一行
    在这里插入图片描述

    以debug模式启动,开始解剖之旅

    点击Step OverHashMap<String, String> map = new HashMap<>(12);所在行

    点击Force Step Into,会发现先调用的是类加载器
    在这里插入图片描述
    这不是今天的重点,我们直接Step Out,然后再次点击Force Step Into,进入源码
    在这里插入图片描述
    调用的是双参构造函数DEFAULT_LOAD_FACTOR为0.75,initialCapacity为12,继续Force Step Into
    在这里插入图片描述
    上图来到双参构造函数,继续Force Step Into会发现依旧调用了父类的构造函数
    在这里插入图片描述
    掉完父类构造函数,继续双参构造函数,经过参数校验,源码456行之后,loadFactor=0.75,我们重点看看this.threshold = tableSizeFor(initialCapacity)
    在这里插入图片描述
    457Force Step Into,会发现跳转到tableSizeFor(int cap)
    在这里插入图片描述
    关于tableSizeFor(int cap),在以前的文章详细分析过,有兴趣的可以去看看 读HashMap源码之tableSizeFor,这里直接说结论,就是你给一个初始容量值,经过这个方法后,返回一个最接近该值的、且不小于该值本身的2^n的那个值,当然,最大不能超过static final int MAXIMUM_CAPACITY = 1 << 30即2的30次方

    所以这里传入12返回的应该是16,n = 15 ,n+1 = 16
    在这里插入图片描述
    所以看到这应该明白,管你传9 10 11 12 13 14 15 16,经过tableSizeFor后都是返回16,这样就确保了threshold总是2的n次方,后面就会发现,其实这个值不是给扩容阈值的,而是给map的初始容量

    继续Force Step Into回到双参函数,将tableSizeFor的结果赋值给threshold扩容阈值=16
    在这里插入图片描述

    开始 put

    到此初始化map完成,其实到了这一步,table还没建立,继续往下Force Step Into开始put
    在这里插入图片描述
    继续Force Step Into进入map.put("1", "1");,来到源码的put(K key, V value)

    在这里插入图片描述
    源码的put(K key, V value)又是调用的putVal,调用之前会计算一下key的hash值,进去看看
    在这里插入图片描述
    key.hashCode()调用的是StringhashCode
    在这里插入图片描述
    然后返回put方法进入putVal,继续Force Step Into,此时hash值为49
    在这里插入图片描述
    因为在初始化时,并没有看到有初始化table,所以此处的table肯定是null
    在这里插入图片描述
    那顺理成章的就要执行resize()了,继续Force Step Into,进入resize()
    在这里插入图片描述
    这个我们在上文 **深入源码分析HashMap到底是怎样将元素put进去的**已经分析了一次,鉴于比较复杂,就再分析一次,还是一样,代码执行路径用红框标记出来
    在这里插入图片描述
    直接返回newTab
    在这里插入图片描述
    通过对上面源码的走读,发现带参构造函数创建的map,

    初始容量就取决于源码692行的newCap = oldThr;

    oldThr又取决于源码680行的int oldThr = threshold;

    在这里插入图片描述
    还记得threshold怎么来的吗,源码457行的tableSizeFor(int initialCapacity),你说狗不狗,在这等你呢,
    所以tableSizeFor的真实目的是为了确保所有map初始化时容量均为2的n次幂
    在这里插入图片描述
    扯远了,回来,拉回来,继续Force Step Into,刚刚走到table创建完,即首次resize完成
    在这里插入图片描述
    有了数组了,长度也知道了,该考虑元素位置了,上文也详细讲解了,

    决定元素位置的是(n - 1) & hash表达式的结果,自己想动手算的参照上文的方法去算

    这里直接看结果,计算出i=1
    在这里插入图片描述
    因为是刚刚创建的,所以tab[1]自然为null,顺理成章的就执行tab[i] = newNode(hash, key, value, null);,构建一个链表的节点放入1号位
    在这里插入图片描述
    继续调试,执行完放入元素之后modCount自增,size自增,并和扩容阈值(当前是12)比较,1小于12不用扩容,

    执行完毕,关于modCount上文
    在这里插入图片描述

    自己画个示意图,大概就是这样的,只有1号位置有元素,其他的均为null
    在这里插入图片描述
    继续Force Step Into,继续map.put("2", "2");,这次算的hash值为50,但此时table不再为null,直接计算位置,1等于2,且该位置为null,直接构造一个Node放进去
    在这里插入图片描述
    依次类推,我们就不一一看了,直接Step Overmap.put("4", "D");,看看key值相同,value不同时怎么处理
    在这里插入图片描述
    一路Force Step Into,来到putVal,发现hash还是52,定位的i也是4,个位置已经有元素了,所以走了源码634

    仔细研究一下这行代码

    p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
    

    p.hash == hashture(k = p.key) == key也为真so执行e = p;,然后暂时还没有树化,所以源码656行直接将新的value覆盖旧的的value
    在这里插入图片描述
    至此,覆盖问题解决,继续Force Step Into,后面没有值重复的,经过一路Force Step Into
    ,1-9位置示意图如下
    在这里插入图片描述

    一直putputput直到map.put("10", "10");,为什么到了这里停下来看呢,因为此时hash只不同了,位置大概率也会不同,进去看看
    在这里插入图片描述
    果然,此时hash已经变成了1567,比之前的递增大了很多,位置也变成了15,与此类似,11的位置为0
    在这里插入图片描述
    截止到目前已经放了11个元素,位置示意图如下
    前11个元素位置示意图
    理论上,再放一个就触及到了我们的扩容阈值threshold = 16*0.75 = 12,但看一下源码662
    在这里插入图片描述
    其实12的时候还不会,是要大于12才会,那就继续Force Step Into走进map.put("12", "12")
    在这里插入图片描述
    事情开始起变化,这hash值不同,但计算的位置i=1上却已经有了元素
    在这里插入图片描述
    上面红色框就是代码执行路径,源码642表明12节点被放在p节点即1号位置的next,而e在源码641赋值时p.next此时还是null,所以下面的代码路径是正确的
    在这里插入图片描述
    所以此时的key=1就有了next,此时示意图如下:
    在这里插入图片描述

    继续Force Step Into,发现前半段map.put("13", "13");还是和map.put("12", "12");一样在这里插入图片描述
    本来按照剧本,key=13应该被放到2号位置key=2next
    示意图应该如下
    在这里插入图片描述
    但是,万事就怕但是,在这里if (++size > threshold)不满足了
    在这里插入图片描述

    增量扩容

    他要再次执行resize()了进去瞧瞧,先不管元素移动,先看扩容
    在这里插入图片描述
    对比第一次的resize来看
    在这里插入图片描述

    元素迁移

    第二次的容量和阈值都比第一次大了2倍,且oldTab不再为null,需要将oldTab迁移到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)
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            ((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;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.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;
                            }
                        }
                    }
                }
            }
    

    回到正题,继续Force Step Into,看源码707行,for (int j = 0; j < oldCap; ++j)就是要循环整个旧表

    上面的代码分三种情况来读

    1. 一是位置上只有一个Node元素,即nextnull的,类似上面的3-9号位置上都只有一个元素
    2. 第二种一个位置上有多个元素的,类似上面的12号位置,目前都有两个元素
    3. 第三种就是此位置上的元素为TreeNode类型的,目前没有,今天先不考虑

    对于第一种情况,核心操作就是源码712行的newTab[e.hash & (newCap - 1)] = e;

    计算该元素在新表中的位置,e.hash & (newCap - 1)
    在这里插入图片描述
    所以0号元素经过e.hash & (newCap - 1)1568 & 31后,工具计算结果在新表的位置是0
    在这里插入图片描述
    然后第二个元素即1号元素,正好是第二种情况,示意图再看一下
    在这里插入图片描述
    源码709oldTab[1]不为null711e.next也不为null

    e instanceof TreeNode也是false,所以核心流程来到了719行的do……while
    在这里插入图片描述
    do……while这段单独拎出来看,先定义两个链表的头和尾,一个链表用来装与旧表元素位置相同的元素,一个用来装需要重新分配位置的元素

                            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;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.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;
                            }
    

    key=1元素开始执行时,源码721e.hash & oldCap46 & 16 != 0,跳转至源码729
    在这里插入图片描述
    继续循环1号位置,此时e.hash & oldCap1569 & 16结果为0,所以将e赋值给loHead,同时链表尾部loTail也指向e
    在这里插入图片描述
    由于只有两个元素,循环到此结束了

    最后将loHead放在newTab[1]即在新数组中与旧数组位置相同的地方

    hiHead则被放在新的数组newTab[1 + 16]即在旧数组位置基础上再加上旧数组的容量

    以此类推,2号位上的两个元素分别被放置在新表的2号和2+16号位置上

    最后操作下来,位置关系如示意图
    在这里插入图片描述

    总结

    到此目标完成,总结一下要点

    1、HashMap的初始化是在插入第一个元素时调用resize完成的(源码629行)
    2、不指定容量,默认容量为16(源码694
    3、指定容量不一定按照你的值来,会经过tableSizeFor转成不小于输入值的2的n次幂,源码378

    这里有个小问题,tableSizeFor转换成2的n次幂不是直接赋值给capacity,而是先将值暂时保存在threshold,见源码457,然后在put第一个元素resize时,婉转的传递给newCap
    在这里插入图片描述

    4、put元素时,元素的位置取决于数组的长度和key的hash值按位与的结果i = (n - 1) & hash源码630
    4.1 如果这里没有元素,直接放这
    4.2 如果有,判断是不是键冲突(源码634),直接新值覆盖旧值*(源码657
    4.3 如果有且不是键冲突,则将其放在原元素的next位置(源码642
    5、只有当size大于了扩容阈值size > threshold,才会触发扩容,源码662,扩容前,当前元素已经放好了
    6、扩容时,容量和扩容阈值都翻番(源码687),但要小于MAXIMUM_CAPACITY
    7、扩容时,元素在新表中的位置分情况
    7.1 当元素只是孤家寡人即元素的next==null(源码)711时,位置为e.hash & (newCap - 1)(源码712
    7.2 当元素有next节点时,该链表上的元素分两类

    7.21 e.hash & oldCap = 0的,在新表中与旧表中的位置一样(源码738

    7.22 e.hash & oldCap != 0的,位置为旧表位置+旧表容量,源码742

    在这里插入图片描述

    展望:

    调了一天,还只是调了其中的一部分,初始化、初始扩容,和增量扩容,类似树化、拆树还没研究呢

    构造树化的思路,也是从源码上找,主要是以下几行
    在这里插入图片描述



    只要你能让不同的key的hash值相同,并且key不相同,就可以制造出hash冲突,就能将多个元素放在同一个位置上,然后直至触发树化,具体情况我们下回分解。

    展开全文
  • ArrayList的扩机制

    千次阅读 多人点赞 2021-12-23 09:38:57
    所以新容量应该等于15 >> 1 + 15 = 22,由此可得,ArrayList经过第三次扩容后容量为22。 然而在addAll()方法中,扩容机制会有一定的变化,比如: public static void main(String[] args) { List<Integer> list = ...

    在Java中,ArrayList是一个使用非常频繁的集合类型,它的底层是Object数组,所以它拥有数组所拥有的特性,比如支持随机访问,所以查询效率高,但插入数据需要移动元素,所以效率低。

    先来看看若是调用ArrayList的无参构造方法,会发生什么?

    transient Object[] elementData;
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    在构造方法中,它将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData,这个DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的Object数组,而elementData就是ArrayList实际存储数据的容器。

    由此可知,ArrayList在调用无参构造方法时创建的是一个长度为0的空数组,当调用add()方法添加元素时,ArrayList才会触发扩容机制:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    

    add()方法的第一行即是执行扩容流程:

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    

    该方法又会先计算扩容容量:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    

    初始elementData就是一个空数组,条件成立,它会从DEFAULT_CAPACITY和minCapacity中选择一个最大值返回,其中DEFAULT_CAPACITY表示默认的初始容量,它的值为10:

    private static final int DEFAULT_CAPACITY = 10;
    

    而minCapacity是add()方法传递过来的,值为size + 1:

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    

    所以calculateCapacity()方法将返回10,之后调用ensureExplicitCapacity()方法:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    

    首先让modCount++,这是用来记录数组被修改次数的变量,我们先不管它,此时minCapacity的值为10,elementData.length的值为0,条件成立,执行grow()方法:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    

    注意这一行代码:

    int newCapacity = oldCapacity + (oldCapacity >> 1);
    

    先将旧容量右移1位,再加上旧容量就得到了新容量,正数右移1位相当于除以2,在该基础上加旧容量,则等价于新容量 = 旧容量 * 1.5,所以才有ArrayList每次扩容为旧容量的1.5倍的说法,最后调用Arrays.copyOf()方法进行拷贝,并将elementData指向新数组,而旧数组因为没有引用指向它,很快就会被垃圾收集器回收掉。

    当第二次调用add()方法时,程序依然要走到扩容方法:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    

    但此时的elementData已经不是空数组了,所以直接返回当前size + 1,即:2,接着调用:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    

    因为此时minCapacity小于数组长度,所以if判断不会成立,也就不会发生扩容。

    当添加第11个元素时,ArrayList应该会触发第二次扩容,来看源代码:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    

    minCapacity的值为11,紧接着调用它:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    

    此时minCapacity的值大于elementData的长度,条件成立,触发扩容机制:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    

    将原容量10右移一位得到5,再加上原容量10得到15,所以新数组的容量为15,最后对数组进行拷贝扩容就完成了。

    当ArrayList进行第三次扩容后容量会是多少呢?我们知道,新容量一定是旧容量的1.5倍,而15 * 1.5 = 22.5,那么新容量到底是22还是23呢?所以,如果你只知道新容量是旧容量的1.5倍,这个问题你就无法知道。事实上,ArrayList底层是通过移位操作计算得到的新容量。所以新容量应该等于15 >> 1 + 15 = 22,由此可得,ArrayList经过第三次扩容后容量为22。

    然而在addAll()方法中,扩容机制会有一定的变化,比如:

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.addAll(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
    }
    

    执行完addAll()方法后,ArrayList的容量应该是多少呢?是15吗?来看看源代码:

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    

    它将调用ensureCapacityInternal()方法进行扩容,并传入 size + numNew = 11:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    

    因为初始elementData是一个空数组,符合条件,所以它将返回DEFAULT_CAPACITY和minCapacity中较大的那个,结果是minCapacity较大,所以返回11,这就导致addAll()方法执行结果后ArrayList的容量为11。

    addAll()方法总是选择扩容一次后的容量与旧容量加上添加的元素个数的容量中取一个最大值作为新的容量,比如:当前ArrayList中有10个元素,而addAll()方法需要添加6个元素,当ArrayList触发扩容后的新容量应该为15,而旧容量加上需要添加的元素容量为16,从中取一个较大值为16,所以新容量应该为16。

    展开全文
  • 电容式声器的输出阻抗呈性,因电容量小,但低频时容抗会很大。为保证低频的灵敏度,应有一个输入阻抗大于或等于声器输出阻抗的阻抗变换器与其相连,经阻抗变换,再用传输线与放大器相连。这个阻抗变换器一般...
  • HashMap的扩

    千次阅读 2021-09-12 15:18:09
    HashMap初始化 在JDK1.8中,定义了HashMap的初始化过程,我们看看他的源码是...这个threshold的成员变量,就是触发HashMap扩的阈值,当HashMap的数据量达到或超过threshold时,就会扩。 我们再往下看这个tableSi

    HashMap初始化

    在JDK1.8中,定义了HashMap的初始化过程,我们看看他的源码是如果定义这个初始化过程
    在这里插入图片描述
    可以看到,它的构造方法中传入了两个参数,一个是初始化容量,一个是加载因子,默认是0.75f

    HashMap(int initialCapacity, float loadFactor)
    

    但是这个容量最终调用了另一个构造方法
    在这里插入图片描述
    这个threshold的成员变量,就是触发HashMap扩容的阈值,当HashMap的数据量达到或超过threshold时,就会扩容。

    我们再往下看这个tableSizeFor(int cap)的构造方法
    在这里插入图片描述
    在 tableSizeFor(int cap)这个构造方法中,对传入的参数cap进行了多次位运算,这样可以让返回值保持在 2 的 N 次方,在扩容的时候,可以快速计算数据在扩容后的新表中的位置。

    HashMap 的 table 初始化

    从上面的源码大家可以发现一个问题,整个计算阈值的过程中,装载因子loadFactor并没有参与运算

    实际上,在HashMap中,所有的数据都是存储在数组中,这个数组的大小就是阈值与加载因子的乘积

    table.size == threshold * loadFactor
    

    HashMap的动态扩容

    • 在 HashMap 中,动态扩容是 resize() 方法
    • 这个方法了 table 的扩容,它还承担了 table 的初始化。

    我们先看看HashMap中put一个元素的过程,最终调用的是putVal这个方法,我们看看源码

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    

    在resize()中,它调整了扩容阈值threshold,并且完成了对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;
            if (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
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
            	//当我们指定了初始容量,且 table 未被初始化时,oldThr 就不为 0,
            	//将 newCap 赋值为 oldThr,新创建的 table 会是我们构造的 HashMap 时指定的容量值。
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
            	//通过装载因子(loadFactor)调整了新的阈值(newThr)
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            // 使用 loadFactor 调整后的阈值,重新保存到 threshold 中
            threshold = newThr;
            @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            //通过 newCap 创建新的数组,将其指定到 table 上,完成 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)
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            ((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;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.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;
        }
    
    
    • 所有我们传递进来的 initialCapacity 虽然经过 tableSizeFor() 方法调整后,直接赋值给 threshold
    • 但是它实际是 table 的大小,并且最终会通过 loadFactor 重新调整 threshold。

    经典面试题

    计划用HashMap存1k条数据,构造时传1000会触发扩容吗

    • HashMap 初始容量指定为 1000,会被 tableSizeFor() 调整为 1024;
    • 但是它只是表示 table 数组为 1024;
    • 负载因子是0.75,扩容阈值会在 resize() 中调整为 768(1024 * 0.75)
    • 会触发扩容

    如果需要存储1k的数据,应该传入1000 / 0.75(1333)

    • tableSizeFor() 方法调整到 2048,不会触发扩容。

    计划用HashMap存1w条数据,构造时传10000会触发扩容吗

    • 当我们构造HashMap时,参数传入进来 1w
    • 经过 tableSizeFor() 方法处理之后,就会变成 2 的 14 次幂 16384
    • 负载因子是 0.75f,可存储的数据容量是 12288(16384 * 0.75f)
    • 完全够用,不会触发扩容
    展开全文
  •   肯定会触发扩呀,因为 HashMap 中有个负载因子默认为 0.75,就是说存储的数量超过容量的 75% 就会触发扩,put 到 25% 的数据时,肯定就会触发扩。但事实真是这样吗?源码中有我们想知道的一切,真相只有...
  • 褐煤惰质组含量远大于长焰煤,且水分含量也高于者。根据非润湿相的汞侵入毛管获得的孔隙分布和BET模型得出微小孔特征。在此基础上,并对甲烷在不同尺度孔隙中的质方式进行探讨。结果显示:褐煤以中大孔为主,微小孔...
  • 一、HashMap 的初始化 ...回到 HashMap 的构造方法,threshold 为扩的阈值,在构造方法中由 tableSizeFor() 方法调整直接赋值,所以在构造 HashMap 时,如果传递 1000,threshold 调整的值确实是 1024,但
  • 深入理解HashMap的扩机制

    千次阅读 2020-12-21 12:01:47
    Java 7 中Hashmap扩机制一、什么时候扩:网上总结的会有很多,但大多都总结的不够完整或者不够准确。大多数可能值说了满足我下面条件一的情况。扩必须满足两个条件:1、 存放新值的时候当前已有元素的个数必须...
  • ArrayList扩原理

    千次阅读 2021-04-17 22:37:03
    ArrayList扩原理 今天带来的下饭菜是ArrayList的扩源码解读。 相信大家对这盘菜都不陌生,我们经常使用它来定义一个集合,无论日常开发还是自己学习使用的频率是相当的高。 而且大家也都一定知道ArrayList集合是...
  • Redis Cluster 集群扩、数据迁移

    千次阅读 2022-02-28 16:09:30
    1、集群扩 2、添加新节点作为副本 3、删除节点 4、副本迁移 5、redis集群节点版本升级 6、迁移到redis集群 7、手动故障转移 8、集群缩容 官方文档:Redis cluster tutorial – Redis 1、集群扩 ...
  • HashMap扩机制解读

    千次阅读 2021-04-24 18:32:44
    机制 什么时候需要扩: 当hashmap中的元素个数超过数组大小 * loadFactor(负载因子)时,就会进行数组扩,loadFactor的默认值(DEFAULT_LOAD_FACTOR)是0.75这是一个折中的取值,也就是说,默认情况下数组...
  • Redis集群搭建及节点扩实战

    千次阅读 2021-12-19 15:51:36
    #查看集群状态 cluster nodes 流程如下: 我们现在开始执行节点增加,也就是扩操作: ./redis-cli --cluster add-node 192.168.100.130:7007 192.168.100.130:7001 执行,我们可以再去看下集群状态,会发现有所...
  • 浅谈ArrayList扩机制

    千次阅读 2021-01-28 12:07:21
    因此,了解它的扩机制对使用它尤为重要。 首先了解ArrayList的几个成员变量 //默认的初始容量 private static final int DEFAULT_CAPACITY = 10; //定义一个空的数组实例以供其他需要用到空数组
  • 小米AX3600扩刷机,如何恢复分区并刷回官方系统。
  • ArrayList的扩机制是如何实现的?

    千次阅读 2022-07-11 19:36:01
    ArrayList是List接口的实现类,在java.util下,它的底层结构是使用Object类型的数组实现的,特点是:元素有序,可重复。那么ArrayList是如何实现扩呢?
  • ArrayList扩处理

    千次阅读 2018-11-29 21:09:03
    ArrayList是基于动态数组实现的一个数据结构,如果添加元素时,元素个数超过list的容量大小时,会涉及到扩。   ArrayList的扩是如何做的,跟着代码走最容易懂。 /** * 添加元素在list尾部 * * @param e...
  • 2022百度网盘无限扩方法技术分享

    千次阅读 2022-04-01 21:13:38
    现在网上很多网课、电影电视剧资料全部都在网盘共享群里,很多人购买会担心群失效,资料就没了,如果能一次性把资料转存到自己的网盘里,就可以留着以后慢慢看,也可以分享给其他人,基于这种需求,百度网盘扩是...
  • 最近在使用Docker容器的过程中,往往会上许多文件,下载镜像等操作会导致虚拟机的磁盘空间被大量的占用。通过在虚拟机中按顺序执行许多的指令,实现扩
  • ArrayList 是 List 接口底下的实现类 , 底层是数组, 可自动扩 , 满足数组的所有特性 先来看它的构造方法 ArrayList() : 构造一个初始容量为10的空列表 ArrayList(collection<? exteds E> c) 构造一个包含...
  • ArrayList扩问题

    万次阅读 2018-12-14 15:19:30
    然后还要再进行一步判断,即判断当前新容量是否超过最大的容量 if (newCapacity - MAX_ARRAY_SIZE > 0),如果超过,则调用hugeCapacity方法,进去的是minCapacity,即新增元素需要的最小容量。获取newCapacity...
  • ArrayList 到底是如何进行扩

    千次阅读 2020-12-08 10:01:08
    } 2,看一下,如果构造ArrayList 对象的时候,如果在构造函数里面什么也不,其会进行什么操作。可以看到,其进行的操作是,初始化了一个空的数组。 public ArrayList() { this.elementData = DEFAULTCAPACITY_...
  • 学习笔记:java数组的扩方法

    千次阅读 2021-12-15 14:50:52
    1.新旧替换,使用一个新的容量更大的数组来接收旧的数组中的数据 1.1 遍历数组进行值的... //将旧数组的值遍历给新数组 for(int i=0;i<a.length;i++) { b[i]=a[i]; } a = b; 1.2 使用System.a...
  • StringBuilder继承了父类AbstractStringBuilder,里面调用的大部分方法都是父类的方法 在StringBuilder的构造函数中定义了初始容量值16,如果传递的是int类型则给指定...当调用append()方法调用时(以下都是字符串的情
  • java 集合Vector 的扩机制

    千次阅读 2022-01-31 02:10:03
    Vector底层是如何实现扩的?
  • c++中,动态数组的动态扩

    千次阅读 2020-05-17 11:06:27
    本文通过以下两个例子来阐述c++动态数组的动态扩机制:** 1. 从给定范围内(start,end)找寻素数并储存在一个一维数组中——函数GetPrimerNumber(); 2. 读取文本,将所有的单词储存到一个二维数组中——函数...
  • 以方便在扩容的时候,快速计算数据在扩容后的新表中的位置。 那么当我们从外部传递进来 1w 时,实际上经过 tableSizeFor() 方法处理之后,就会变成 2 的 14 次幂 16384,再算上负载因子 0.75f,实际在不触发扩容的...
  • 上文讲解过自动迁移槽实现集群扩(传送门) 1.准备新节点 安装redis,参考传送门 节点配置,参考传送门 2.将节点加入集群 redis-cli --cluster add-node {new host}:{new port} {exist host}:{exist port} 加入...
  • jdk1.8 HashMap工作原理和扩机制(源码解析)

    万次阅读 多人点赞 2018-05-29 20:37:14
    容后得到了一个table的节点(Node)数组,接着根据传入的hash值去获得一个对应节点p并去判断是否为空,是的话就存入一个新的节点(Node)。反之如果当前存放的位置已经有值了就会进入到else中去。接着根据前面得到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,250
精华内容 18,100
关键字:

容后传