ArrayList源码分析（jdk1.8）

雨点打透心脏的1/2处 2024-04-18 20:13 85阅读 0赞

聊一聊ArrayList的特点吧~（以下都是基于jdk1.8）

ArrayList的继承树如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]

（1）底层使用动态数组Object\[\] elementData 来保存所有元素

（2）线程不安全。可通过如下方式使用线程安全的操作：

List list = Collections.synchronizedList(new ArrayList(...));

（3）默认初始容量是10

（4）可通过构造函数指定初始容量（实际分配容量）

（5）允许null值。

（6）具有fail-fast机制。

（7）如果要向集合中添加大量元素，可以使用ensureCapacity（int minCapacity)，减少重分配的次数，提高性能。

（8）先扩容，再插入元素。【数组容量满了之后才会触发扩容】

先看类中定义的变量和常用的构造函数：

/** * Default initial capacity. */
        private static final int DEFAULT_CAPACITY = 10;
    
        /** * Shared empty array instance used for empty instances. */
        private static final Object[] EMPTY_ELEMENTDATA = { };
    
        /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */
        private static final Object[] DEFAULTCAPACITY_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 == 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
    
        /** * The size of the ArrayList (the number of elements it contains). * * @serial */
        private int size;
    
        /** * 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);
            }
        }
    
        /** * Constructs an empty list with an initial capacity of ten. */
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

本篇的着重点在于扩容部分。

以add方法为例：

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
        public boolean add(E e) { 
        	//
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
        
        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);
        }

再看扩容方法的核心：

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
        private void grow(int minCapacity) { 
            // overflow-conscious code
            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 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;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0x1eWFuYw_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e3fea60ff1d04b3696487210d30859f5.png