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

    2021-04-27 18:14:06
    ArrayList的扩容机制 1、源码分析 /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ...

    ArrayList的扩容机制

    1、源码分析

        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData; // non-private to simplify nested class access
    

    ArrayList的底层为Object[] 数组。

        /**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;
    

    ArrayList的默认容量为10

        /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    

    ArrayList的无参构造函数,DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10,也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10

        /**
         * Constructs an empty list with the specified initial capacity.
         *
         * @param  initialCapacity  the initial capacity of the list
         * @throws IllegalArgumentException if the specified initial capacity
         *         is negative
         */
        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对象时自己指定集合的大小)

    如果传入的参数大于0,创建initialCapacity大小的数组,如果传入的参数等于0,创建空数组,其他情况,抛出异常。

    2、扩容机制

        /**
         * Increases the capacity of this <tt>ArrayList</tt> instance, if
         * necessary, to ensure that it can hold at least the number of elements
         * specified by the minimum capacity argument.
         *
         * @param   minCapacity   the desired minimum capacity
         */
        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);
            }
        }
    

    minCapacity参数指的是所需的最小容量,minExpand指的是已有最大容量,先判断elementData是否为空,如果为空,则minExpand为10,如果不为空,minExpand为0,如果最小容量大于已有的最大容量,则通过ensureExplicitCapacity()方法判断是否需要扩容。

        private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    

    获取“默认的容量”和“传入参数”两者之间的最大值

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

    判断是否需要扩容。

        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);
        }
    

    oldCapacity为旧容量,newCapacity为新容量,通过位运算将新容量更新为旧容量的1.5倍,然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当做数组的新容量,再检查新容量是否超出了ArrayList所定义的最大容量,若超出了,则比较minCapacity和MAX_ARRY_SIZE,如果minCapacity大于Max_ARRAY_SIZE,则新容量为Interger.MAX_VALUE,否则,新容量大小为MAX_ARRAY_SIZE。

    展开全文
  • ArrayList 的扩容机制

    2021-03-04 16:14:50
    当然了,这个存储是不可能无限的,ArrayList的扩容长度受限于vms即虚拟机的最大数组限制,MAX_ARRAY_SIZE 那么ArrayList是如何实现动态扩容的呢 ArrayList内部是使用Object[] 数组进行存储内容的 一开始...

    ArrayList 是基于数组Array的

     

    Array 需要人为定长,一旦在内存空间内根据长度开辟,则不可改变

     

    而ArrayList 就是为了能够趋近于无限的存储内容,而设计的。当然了,这个存储是不可能无限的,ArrayList的扩容长度受限于vms即虚拟机的最大数组限制,MAX_ARRAY_SIZE

     

    那么ArrayList是如何实现动态扩容的呢

     

    ArrayList内部是使用Object[] 数组进行存储内容的 

     

    一开始设定了一个默认长度,

    private static final int DEFAULT_CAPACITY = 10; 

     

    题外话,像这种被static final 标记的常量,一般是存储在JVM 方法区内的常量池内

     

    在ArrayList 实例化的时候,可以设置默认长度给Object[] 对象,若没设置,会直接给它一个定义好的{} 对象

     

    扩容这步骤其实是在add操作内发生的

     

    测试案例:

     

    ArrayList<String> test = new ArrayList<>();
    
    for(int i = 1; i<11; i++){
    
        test.add(String.valueOf(i));
    
    }

     

    在add的时候,它会自主去检查当前容器是否足够存储接下来的值

     

    minCapacity - elementData.length > 0 

    加了1后的容量是否大于elementData[]数组初始化的长度,如果大于,则进行grow(扩容)

     

    扩容

    private void grow(int minCapacity) {
    
        // overflow-conscious code
    
        int oldCapacity = elementData.length;
    
        //原先存储的值的大小的一半  例如 原先存 10 右移 1 位后 变成5
    
        //原先空间的长度 + 长度的一半  为扩容值
    
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    
        //如果新计算的扩容值比先设置的最小扩容值还小的话,以Capacity大小扩容
    
        if (newCapacity - minCapacity < 0)
    
            newCapacity = minCapacity;
    
        //MAX_ARRAY_SIZE  有些虚拟机会对数组最大容量进行限制,所以 扩容大小上下限需要进行判断
    
        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);
    
    }
    private static int hugeCapacity(int minCapacity) {
    
        if (minCapacity < 0) // overflow
    
            throw new OutOfMemoryError();
    
        return (minCapacity > MAX_ARRAY_SIZE) ?
    
            Integer.MAX_VALUE :
    
            MAX_ARRAY_SIZE;
    
    }

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,141
精华内容 456
关键字:

arraylist的扩容机制