精华内容
下载资源
问答
  • 2022-04-14 19:01:18

    一、先从 ArrayList 的构造函数说起

    ArrayList有三种方式来初始化,构造方法源码如下

       /**
         * 默认初始容量大小
         */
        private static final int DEFAULT_CAPACITY = 10;
        
    
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        /**
         *默认构造函数,使用初始容量10构造一个空列表(无参数构造)
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        
        /**
         * 带初始容量参数的构造函数。(用户自己指定容量)
         */
        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {//初始容量大于0
                //创建initialCapacity大小的数组
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {//初始容量等于0
                //创建空数组
                this.elementData = EMPTY_ELEMENTDATA;
            } else {//初始容量小于0,抛出异常
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    
    
       /**
        *构造包含指定collection元素的列表,这些元素利用该集合的迭代器按顺序返回
        *如果指定的集合为null,throws NullPointerException。 
        */
         public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }
    

    细心的同学一定会发现 :以无参数构造方法创建 ArrayList 时,实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为10。 下面在我们分析 ArrayList 扩容时会降到这一点内容!

    二、一步一步分析 ArrayList 扩容机制

    这里以无参构造函数创建的 ArrayList 为例分析

    1. 先来看add方法

        /**
         * 将指定的元素追加到此列表的末尾。 
         */
        public boolean add(E e) {
       //添加元素之前,先调用ensureCapacityInternal方法
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //这里看到ArrayList添加元素的实质就相当于为数组赋值
            elementData[size++] = e;
            return true;
        }
    

    2. 再来看看ensureCapacityInternal()方法

    可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)

       //得到最小扩容量
        private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                  // 获取默认的容量和传入参数的较大值
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    

    当 要 add 进第1个元素时,minCapacity为1,在Math.max()方法比较后,minCapacity 为10

    3. ensureExplicitCapacity()方法

    如果调用ensureCapacityInternal()方法就一定会进过(执行)这个方法,下面我们来研究一下这个方法的源码!

      //判断是否需要扩容
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                //调用grow方法进行扩容,调用此方法代表已经开始扩容了
                grow(minCapacity);
        }
    

    我们来仔细分析一下:

    • 当我们要 add 进第1个元素到 ArrayList 时,elementData.length 为0 (因为还是一个空的 list),因为执行了ensureCapacityInternal()方法 ,所以 minCapacity 此时为10。此时,minCapacity - elementData.length > 0 成立,所以会进入grow(minCapacity)方法。
    • 当add第2个元素时,minCapacity 为2,此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时,minCapacity - elementData.length > 0不成立,所以不会进入 (执行)grow(minCapacity)方法。
    • 添加第3、4···到第10个元素时,依然不会执行grow方法,数组容量都为10。

    直到添加第11个元素,minCapacity(为11)比elementData.length(为10)要大。进入grow方法进行扩容。

    4. grow() 方法

        /**
         * 要分配的最大数组大小
         */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        /**
         * ArrayList扩容的核心方法。
         */
        private void grow(int minCapacity) {
            // oldCapacity为旧容量,newCapacity为新容量
            int oldCapacity = elementData.length;
            //将oldCapacity 右移一位,其效果相当于oldCapacity /2,
            //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
           // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,
           //如果minCapacity大于最大容量,则新容量则为`Integer.MAX_VALUE`,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
            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),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍! 记清楚了!不是网上很多人说的 1.5 倍+1!

    ">>"(移位运算符):>>1 右移一位相当于除2,右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源

    我们再来通过例子探究一下grow() 方法

    • 当add第1个元素时,oldCapacity 为0,经比较后第一个if判断成立,newCapacity = minCapacity(为10)。但是第二个if判断不会成立,即newCapacity 不比 MAX_ARRAY_SIZE大,则不会进入hugeCapacity方法。数组容量为10,add方法中 return true,size增为1。
    • 当add第11个元素进入grow方法时,newCapacity为15,比minCapacity(为11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中return true,size增为11。
    • 以此类推······

    这里补充一点比较重要,但是容易被忽视掉的知识点

    • java 中的length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
    • java 中的length()方法是针对字符串说的,如果想看这个字符串的长度则用到length()这个方法.
    • java 中的size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

    5. hugeCapacity() 方法。

    从上面grow()方法源码我们知道: 如果新容量大于 MAX_ARRAY_SIZE,进入(执行)hugeCapacity()方法来比较 minCapacity 和 MAX_ARRAY_SIZE,如果minCapacity大于最大容量,则新容量则为Integer.MAX_VALUE,否则,新容量大小则为 MAX_ARRAY_SIZE 即为Integer.MAX_VALUE - 8

        private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            //对minCapacity和MAX_ARRAY_SIZE进行比较
            //若minCapacity大,将Integer.MAX_VALUE作为新数组的大小
            //若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小
            //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
    

    三、System.arraycopy()Arrays.copyOf()方法

    阅读源码的话,我们就会发现 ArrayList 中大量调用了这两个方法。比如:我们上面讲的扩容操作以及add(int index, E element)toArray()等方法中都用到了该方法!

    3.1 System.arraycopy() 方法

        /**
         * 在此列表中的指定位置插入指定的元素。 
         *先调用 rangeCheckForAdd 对index进行界限检查;然后调用 ensureCapacityInternal 方法保证capacity足够大;
         *再将从index开始之后的所有成员后移一个位置;将element插入index位置;最后size加1。
         */
        public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //arraycopy()方法实现数组自己复制自己
            //elementData:源数组;index:源数组中的起始位置;elementData:目标数组;index + 1:目标数组中的起始位置; size - index:要复制的数组元素的数量;
            System.arraycopy(elementData, index, elementData, index + 1, size - index);
            elementData[index] = element;
            size++;
        }
    

    我们写一个简单的方法测试以下:

    public class ArraycopyTest {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            int[] a = new int[10];
            a[0] = 0;
            a[1] = 1;
            a[2] = 2;
            a[3] = 3;
            System.arraycopy(a, 2, a, 3, 3);
            a[2]=99;
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
        }
    
    }
    

    结果:

    0 1 99 2 3 0 0 0 0 0
    

    3.2Arrays.copyOf()方法

       /**
         以正确的顺序返回一个包含此列表中所有元素的数组(从第一个到最后一个元素); 返回的数组的运行时类型是指定数组的运行时类型。 
         */
        public Object[] toArray() {
        //elementData:要复制的数组;size:要复制的长度
            return Arrays.copyOf(elementData, size);
        }
    

    个人觉得使用 Arrays.copyOf()方法主要是为了给原有数组扩容,测试代码如下:

    public class ArrayscopyOfTest {
    
        public static void main(String[] args) {
            int[] a = new int[3];
            a[0] = 0;
            a[1] = 1;
            a[2] = 2;
            int[] b = Arrays.copyOf(a, 10);
            System.out.println("b.length"+b.length);
        }
    }
    

    结果:

    10
    

    3.3 两者联系和区别

    联系

    看两者源代码可以发现 copyOf() 内部实际调用了System.arraycopy()方法

    区别

    arraycopy()需要目标数组,将原数组拷贝到你自己定义的数组里或者原数组,而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf()是系统自动在内部新建一个数组,并返回该数组。

    四、ensureCapacity方法

    ArrayList 源码中有一个ensureCapacity方法不知道大家注意到没有,这个方法 ArrayList 内部没有被调用过,所以很显然是提供给用户调用的,那么这个方法有什么作用呢?

        /**
        如有必要,增加此 ArrayList 实例的容量,以确保它至少可以容纳由minimum capacity参数指定的元素数。
         *
         * @param   minCapacity   所需的最小容量
         */
        public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }
    

    最好在 add 大量元素之前用 ensureCapacity 方法,以减少增量从新分配的次数

    我们通过下面的代码实际测试以下这个方法的效果:

    public class EnsureCapacityTest {
        public static void main(String[] args) {
            ArrayList<Object> list = new ArrayList<Object>();
            final int N = 10000000;
            long startTime = System.currentTimeMillis();
            for (int i = 0; i < N; i++) {
                list.add(i);
            }
            long endTime = System.currentTimeMillis();
            System.out.println("使用ensureCapacity方法前:"+(endTime - startTime));
    
            list = new ArrayList<Object>();
            long startTime1 = System.currentTimeMillis();
            list.ensureCapacity(N);
            for (int i = 0; i < N; i++) {
                list.add(i);
            }
            long endTime1 = System.currentTimeMillis();
            System.out.println("使用ensureCapacity方法后:"+(endTime1 - startTime1));
        }
    }
    

    运行结果:

    使用ensureCapacity方法前:4637
    使用ensureCapacity方法前:241
    

    通过运行结果,我们可以很明显的看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法,以减少增量从新分配的次数

    更多相关内容
  • ArrayList扩容机制

    2022-04-27 16:22:33
    ArrayList扩容机制 在ArrayList中,声明了三个常量 private static final int DEFAULT_CAPACITY = 10;//默认容量大小为10 private static final Object[] EMPTY_ELEMENTDATA = {};//一个空数组 private static final...

    ArrayList扩容机制

    在ArrayList中,声明了三个常量

    private static final int DEFAULT_CAPACITY = 10;//默认容量大小为10
    private static final Object[] EMPTY_ELEMENTDATA = {};//一个空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//一个默认容量的空数组
    

    还声明了一个数组

    transient Object[] elementData; // non-private to simplify nested class access
    

    然后再看一下ArrayList的构造方法

    这是无参构造

    public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    

    这是有参构造

    public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    

    通常创建ArrayList时都是调用的无参构造,调用无参构造时,会将数组赋为默认长度的空数组,之后通过调取add方法添加元素时会进行扩容

    add方法有三个,看一下常用add方法的源码

    public boolean add(E e) {
            modCount++;
            add(e, elementData, size);
            return true;
        }
    
    private void add(E e, Object[] elementData, int s) {
            if (s == elementData.length)
                elementData = grow();
            elementData[s] = e;
            size = s + 1;
        }
    

    调用boolean add(E e),首先让modCount++,这是用来记录数组被修改次数的变量,我们先不管它,此时size值为0,再调取void add(E e, Object[] elementData, int s)这个方法,将初始化的elementData,e, 还有size传过去,在这个add方法中先判断数组长度是否与size相等,如果相等,则调用grow()方法进行扩容,扩容后再将e插入到elementData最后,size+1。

    看一下grow方法的源码

    private Object[] grow() {
            return grow(size + 1);
        }
    
    private Object[] grow(int minCapacity) {
            return elementData = Arrays.copyOf(elementData,
                                               newCapacity(minCapacity));
        }
    

    add方法调用grow的无参方法,无参grow方法又调用带参grow方法,并传入size+1。

    在grow方法中,返回一个elementData,elementData等于Arrays.coptOf(element, newCapacity(minCapacity)),这个Arrays.copyOf是一个数组复制方法,将elementData数组赋给newCapacity(minCapacity)返回的新数组中。接着就是重点了,看newCapacity(minCapacity)方法的源码

    private int newCapacity(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity <= 0) {
                if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                    return Math.max(DEFAULT_CAPACITY, minCapacity);
                if (minCapacity < 0) // overflow
                    throw new OutOfMemoryError();
                return minCapacity;
            }
            return (newCapacity - MAX_ARRAY_SIZE <= 0)
                ? newCapacity
                : hugeCapacity(minCapacity);
        }
    

    在这个方法中有一个oldCapacity,表示旧的数组容量,还有一个newCapacity表示扩容后的数组容量,这个容量为oldCapacity+(oldCapacity >> 1),这里有一个位运算,表示将oldCapacity右移一位,在二进制中,右移一位相当于除以二,下面举例说明:

    十进制2用二进制表示为10,右移一位后变为1,也就是十进制的1
    十进制6用二进制表示为110,右移一位后变为11, 也就是十进制的3
    

    所以扩容后的容量相当于oldCapacity * (Capacity / 2),也就有了ArrayList每次扩容都是原来1.5倍的说法。

    扩容后判断是否小于minCapacity(注:minCapacity的值为grow传入的size+1),若小于,判断elementData是否为默认大小的空数组,若是,则返回minCapaacity与默认大小比较后的最大值。

    若不是,再判断minCapacity是否小于0,若小于0,则抛出异常。最后再返回minCapacity。

    oldCapacity由于扩容后没有引用,很快就会被垃圾回收器回收掉,再调用add方法时,还会再走一遍扩容流程,由于此时数组已经经过了一次扩容,他的size与elementData.length不同,直接插入即可,当到达上限后在进行下此次扩容。

    我们可以写一段代码来查看ArrayList的容量

    获取ArrayList当前容量

    import java.lang.reflect.Field;
    import java.util.ArrayList;
    
    public class Test{
        public static void main(String args[]) {
            ArrayList<Integer> arrayList = new ArrayList<>();
    
            System.out.println(getArrayListCapacity(arrayList));
    
            //增加元素,使其扩容
            arrayList.add(0);
            System.out.println(getArrayListCapacity(arrayList));
    
            for(int i = 0; i < 10; ++i)
                arrayList.add(0);
            System.out.println(getArrayListCapacity(arrayList));
    
            for(int i = 0; i < 5; ++i)
                arrayList.add(0);
            System.out.println(getArrayListCapacity(arrayList));
        }
    
        public static int getArrayListCapacity(ArrayList<?> arrayList) {
            Class<ArrayList> arrayListClass = ArrayList.class;
            try {
                Field field = arrayListClass.getDeclaredField("elementData");
                field.setAccessible(true);
                Object[] objects = (Object[])field.get(arrayList);
                return objects.length;
            } catch (NoSuchFieldException e) {
                e.printStackTrace();
                return -1;
            } catch (IllegalAccessException e) {
                e.printStackTrace();
                return -1;
            }
        }
    }
    
    

    输出结果

    0
    10
    15
    22
    

    以上均为个人理解,如有错误,欢迎指正,不胜感激。

    展开全文
  • 本资源根据个人学习和总结,主要介绍Java中ArrayList扩容机制源码的解析,主要包含文字和代码等内容,以源码的形式进行分析,详细介绍了ArrayList扩容机制的整个流程,特此将该资源分享
  • 分析ArrayList扩容机制

    2021-02-15 17:16:58
    一、先从 ArrayList 的构造函数说起 ArrayList有三种方式来初始化,这里讲最常用的无参数方法: /** * 默认初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; private static final Object[]...

    转载自:白春雨(https://www.cnblogs.com/baichunyu/p/12965241.html)

    一、先从 ArrayList 的构造函数说起

    ArrayList有三种方式来初始化,这里讲最常用的无参数方法:

    	/**
         * 默认初始容量大小
         */
        private static final int DEFAULT_CAPACITY = 10;
    
    
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    	
    	transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         *默认构造函数,使用初始容量10构造一个空列表(无参数构造)
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
    

    构造方法将elementData指向内部空的数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA,当真正对数组进行添加元素操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为10。

    二、一步一步分析 ArrayList 扩容机制

    这里以无参构造函数创建的 ArrayList 为例分析:

    1、先来看 add 方法

    	/**
         * 将指定的元素追加到此列表的末尾。
         */
        public boolean add(E e) {
       //添加元素之前,先调用ensureCapacityInternal方法
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //这里看到ArrayList添加元素的实质就相当于为数组赋值
            elementData[size++] = e;
            return true;
        }
    

    2、再来看看 ensureCapacityInternal() 方法

    可以看到 add 方法 首先调用了ensureCapacityInternal(size + 1)

    	//得到最小扩容量
        private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                  // 获取默认的容量和传入参数的较大值
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    

    3、ensureExplicitCapacity() 方法

    如果调用 ensureCapacityInternal() 方法就一定会进过(执行)这个方法,下面我们来研究一下这个方法的源码!

     	protected transient int modCount = 0;
    	//判断是否需要扩容
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                //调用grow方法进行扩容,调用此方法代表已经开始扩容了
                grow(minCapacity);
        }
    

    我们来仔细分析一下:

    • 当我们要 add 进第1个元素到 ArrayList 时,elementData.length 为0 (因为还是一个空的 list),因为执行了 ensureCapacityInternal() 方法 ,所以 minCapacity 此时为10。此时,minCapacity - elementData.length > 0 成立,所以会进入 grow(minCapacity) 方法。
    • 当add第2个元素时,minCapacity 为2,此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时,minCapacity - elementData.length > 0 不成立,所以不会进入 (执行)grow(minCapacity) 方法。
    • 添加第3、4···到第10个元素时,依然不会执行grow方法,数组容量都为10。

    直到添加第11个元素,minCapacity(为11)比elementData.length(为10)要大。进入grow方法进行扩容。

    4、grow() 方法

    /**
         * 要分配的最大数组大小
         */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        /**
         * ArrayList扩容的核心方法。
         */
        private void grow(int minCapacity) {
            // oldCapacity为旧容量,newCapacity为新容量
            int oldCapacity = elementData.length;
            //将oldCapacity 右移一位,其效果相当于oldCapacity /2,
            //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
           // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,
           //如果minCapacity大于最大容量,则新容量则为`Integer.MAX_VALUE`,否则,新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
            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),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右(oldCapacity为偶数就是1.5倍,否则是1.5倍左右)! 奇偶不同,比如 :10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

    我们再来通过例子探究一下grow() 方法 :

    • 当add第1个元素时,oldCapacity 为0,经比较后第一个if判断成立,newCapacity = minCapacity(为10)。但是第二个if判断不会成立,即newCapacity 不比 MAX_ARRAY_SIZE大,则不会进入 hugeCapacity 方法。数组容量为10,add方法中 return true,size增为1。
    • 当add第11个元素进入grow方法时,newCapacity为15,比minCapacity(为11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中return true,size增为11。
      以此类推······

    这里补充一点比较重要,但是容易被忽视掉的知识点:

    1.java 中的 length 属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
    2.java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.
    3.java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!
    

    5、hugeCapacity() 方法

    最后讲一下当扩容后数组大小大于MAX_ARRAY_SIZE时候执行的hugeCapacity()方法。

    private static int hugeCapacity(int minCapacity) {
    	if (minCapacity < 0) // overflow
    	    throw new OutOfMemoryError();
    	//对minCapacity和MAX_ARRAY_SIZE进行比较
    	//若minCapacity大,将Integer.MAX_VALUE作为新数组的大小
    	//若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小
    	//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    	return (minCapacity > MAX_ARRAY_SIZE) ?
    	    Integer.MAX_VALUE :
    	    MAX_ARRAY_SIZE;
    }
    

    这个方法是指当扩容后的size大于规定的MAX_ARRAY_SIZE那么这个时候有两种可能

    1. 当前ArrayList存入的size小于MAX_ARRAY_SIZE即调用add插入后数组容量不大于MAX_ARRAY_SIZE,即minCapacity小于等于MAX_ARRAY_SIZE那么这个时候,进入hugeCapacity方法最后返回的是MAX_ARRAY_SIZE;
    2. 上面的容量已经扩容到最大了,那么这个时候如果在插入会发生什么?这个时候minCapacity等于MAX_ARRAY_SIZE+1,最后返回的是Integer.MAX_VALUE;

    所以最大是只能到Integer.MAX_VALUE;

    另:ensureCapacity方法

    ArrayList 源码中有一个 ensureCapacity 方法不知道大家注意到没有,这个方法 ArrayList 内部没有被调用过,所以很显然是提供给用户调用的,那么这个方法有什么作用呢?

    	/**
    	    如有必要,增加此 ArrayList 实例的容量,以确保它至少可以容纳由minimum capacity参数指定的元素数。
         *
         * @param   minCapacity   所需的最小容量
         */
        public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }
    

    目的就是减少扩容次数,当我们知道具体的容量大小的时候,直接使用有参构造方法,而不是使用默认的构造方法,默认的10容量会使得程序频繁扩容,极大拉低程序效率,同理Hashmap在知道具体容量的时候也应该避免。

    展开全文
  • Java ArrayList扩容机制

    千次阅读 2022-04-04 19:38:12
    ArrayList的容量为Capacity,如果你ArrayList array=new ArrayList(initial_capacity),那么ArrayList的初始...Capacity,那ArrayList就发生扩容,容量Capacity变为1.5Capacity(其实是Capacity=Capacity+Capacity&g
  • 细品ArrayList扩容机制

    千次阅读 2022-04-10 21:20:23
    ArrayList扩容现象演示 首先通过简单的测试代码看看初始化及扩容现象,测试代码如下: @Test public void test3() { List<Integer> list = new ArrayList<>(); list.add(0); System.out.println("***...
  • ArrayList扩容机制JDK1.8

    多人点赞 热门讨论 2021-12-10 19:32:50
    这道题考察了ArrayList的构造器和对扩容机制的了解,本篇博客基于此出发讲解ArrayList扩容机制 想要做出这道题必须了解ArrayList的构造函数,ArrayList的构造函数总共有三个: ArrayList()构造一个空的数组。JDK7...
  • 首先分析ArrayList的变量,最主要的是以下五个。 private static final int DEFAULT_CAPACITY = 10;//默认容量 private static final Object[] EMPTY_ELEMENTDATA = {};//空数组 private static final ...
  • ArrayList扩容机制分析

    2022-03-29 11:21:57
    ArrayList是有三种初始化的方法,其中一种以无参构造方法来创建ArrayList:实际上初始化赋值的是一个空数组,当真正对数组进行添加元素操作时,才会分配容量,即向数组添加第一个元素时,数组容量扩容为10,我们以这...
  • ArrayList继承自AbstractList,实现List接口,是一个可变长的列表。...今天看了下ArrayList的源码,记录一下它的扩容机制。 首先,需要了解类内的这6个属性: /** * 列表默认的初始化容量,10 */
  • 1. ArrayList() 会使用长度为零的数组 ...4.add(Object o)首次扩容为10,再次扩容为上次容量的1.5倍 5.addAll(Collection c) 没有元素时,扩容为Math,max(10,实际元素个数),有元素时为Math.ma(原容量的1.5倍,实际
  • 文章目录ArrayList主要方法和扩容机制(源码解析)一、ArrayList基本概述二、ArrayList扩容机制 一、ArrayList基本概述   ArrayList是实现了List接口的基于动态数组的数据结构,可以用来存放各种类型的数据,...
  • 常见面试题02-ArrayList扩容机制详解

    千次阅读 2020-11-20 12:52:54
    默认长度是什么,说一下它的扩容机制 进入ArrayList类源码进行分析 分析思路: 1.查看arraylist类的介绍 2.理解arraylist类的属性含义 3.理解arraylist的构造方法 4..理解arraylist中比较重要的方法机制(如add、...
  • 首先简单的总结一下ArrayList扩容机制: 使用无参构造器,初始容量为0,第一次添加扩容为10,再次扩容为1.5倍(向下取整) 使用指定大小的构造器,初始容量为指定大小,再次扩容为1.5倍(向下取整) 为什么初始...
  • 首先看看 ArrayList 构造器和几个属性: //默认初始容量大小 private static final int DEFAULT_CAPACITY = 10; //空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; //用于默认大小空实例的共享...
  • ArrayList 扩容机制 全局变量 // 如果使用无参构造器,初始化后第一次add时的默认数组长度 private static final int DEFAULT_CAPACITY = 10; // 定义一个空数组以供使用 private static final Object[] EMPTY...
  • 一 先从 ArrayList 的构造函数说起 ArrayList有三种方式来初始化,构造方法源码如下: /** * 默认初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; private static final Object[] ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,328
精华内容 11,331
关键字:

arraylist的扩容机制