ArrayList的底层数据结构

谁借莪１个温暖的怀抱￠ 2022-05-04 11:56 233阅读 0赞

转自：[https://www.cnblogs.com/dassmeta/p/5334960.html][https_www.cnblogs.com_dassmeta_p_5334960.html]

ublic class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        private static final long serialVersionUID = 8683452581122892189L;
    
        /**
         * Default initial capacity.
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * 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 == EMPTY_ELEMENTDATA will be expanded to
         * DEFAULT_CAPACITY when the first element is added.
         */
        private transient Object[] elementData;
    
        /**
         * The size of the ArrayList (the number of elements it contains).
         *
         * @serial
         */
        private int size;
    }

ArrayList 的底层最重要的两个属性：Object 数组和 size 属性。

Add方法

public boolean add(E e) {
    		//先判断长度用不用扩容,要扩容的话就马上进行扩容
    		ensureCapacityInternal(size + 1);
    		//将元素放进数组里
    		elementData[size++] = e;
    		return true;
    	}

//minCapacity是所需的最小容量
     public void ensureCapacity(int minCapacity) {
    
            int minExpand = (elementData != EMPTY_ELEMENTDATA)  ? 0 : DEFAULT_CAPACITY;
            //如果已经大于初始容量就扩容
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            //大于数组的长度扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        private void grow(int minCapacity) {
    
            int oldCapacity = elementData.length;
            //旧容量＋旧容量/2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //新容量还是没大于所需的最小容量
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
    
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
    
            //minCapacity通常接近大小，所以这是一个胜利
            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;
    
        }

2点结论：

a. ArrayList 是通过将底层 Object 数组复制的方式（System.arraycopy方法）来处理数组的增长；

b. 当ArrayList 的容量不足时，其扩充容量的方式：先将容量扩充至当前容量的1.5倍，若还不够，则将容量扩充至当前需要的数量（grow方法）。

**ArrayList****与Vector****的区别**

1） vector 是线程同步的，所以它也是线程安全的，而arraylist 是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用 arraylist效率比较高。

2）如果集合中的元素的数目大于目前集合数组的长度时，vector 增长率为目前数组长度的100%, 而arraylist 增长率为目前数组长度的50% .如果在集合中使用数据量比较大的数据，用vector有一定的优势。

3）如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，都是O(1) ,这个时候使用vector和arraylist都可以。

而如果移动一个指定位置的数据花费的时间为O(n-i)n为总长度，这个时候就应该考虑到使用linklist ,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。

[https_www.cnblogs.com_dassmeta_p_5334960.html]: https://www.cnblogs.com/dassmeta/p/5334960.html