JDK1.8 ArrayList详解

怼烎@ 2023-06-20 06:22 33阅读 0赞

### 1 ArrayList类定义 ###

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        }

从ArrayList的定义可以得出：

> 1.  ArrayList<E>：说明ArrayList支持泛型。
> 2.  ArrayList继承了AbstractList。AbstractList是List接口的骨干实现，以最大限度地减少“随机访问”数据存储（如ArrayList）实现Llist所需的工作。
> 3.  implements List<E>：实现了List接口。实现了所有可选列表操作。
> 4.  implements RandomAccess：实现RandomAccess接口，说明ArrayList支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
> 5.  implements Cloneable：实现Cloneable接口，表明其可以调用clone()方法来返回实例的field-for-field拷贝。
> 6.  implements java.io.Serializable：实现Serializable接口，说明ArrayList具有序列化功能。

### 2 属性值 ###

ArrayList中主要包含以下属性，对于属性的说明在代码注释中。

// 初始化时容器的默认大小为10。
    private static final int DEFAULT_CAPACITY = 10;
    
    // 指定该ArrayList容量为0时，返回该空数组。
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    /**
     * 当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时，其内数据量为0。
     * 它与EMPTY_ELEMENTDATA的区别就是：该数组是默认返回的，而后者是在用户指定容量为0时返回。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * 保存添加到ArrayList中的元素。
     * ArrayList的容量就是该数组的长度。
     * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，数组将扩容值DEFAULT_CAPACITY。
     * 被标记为transient，在对象被序列化的时候不会被序列化。
     */
    transient Object[] elementData; 
    
    // 容器中实际存储的元素个数
    private int size;

`elementData`对象标记为`transient`，表明在对象被序列化的时候不会被序列化。那么该对象的序列化和反序列化过程就需要由ArrayList实现，下面为ArrayList中实现`elementData`序列化的过程。

private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{
            // Write out element count, and any hidden stuff
            int expectedModCount = modCount;
            s.defaultWriteObject();
    
            // Write out size as capacity for behavioural compatibility with clone()
            s.writeInt(size);
    
            // Write out all elements in the proper order.
            for (int i=0; i<size; i++) {
                s.writeObject(elementData[i]);
            }
    
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
    
        /**
         * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
         * deserialize it).
         */
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            elementData = EMPTY_ELEMENTDATA;
    
            // Read in size, and any hidden stuff
            s.defaultReadObject();
    
            // Read in capacity
            s.readInt(); // ignored
    
            if (size > 0) {
                // be like clone(), allocate array based upon size not capacity
                int capacity = calculateCapacity(elementData, size);
                SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
                ensureCapacityInternal(size);
    
                Object[] a = elementData;
                // Read in all elements in the proper order.
                for (int i=0; i<size; i++) {
                    a[i] = s.readObject();
                }
            }
        }

### 4 构造函数 ###

1）无参数构造，初始容量采用默认值为10

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

2）指定初始化容量为`capacity`

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

3）使用集合创建

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

### 5 核心方法 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <th>方法名</th> 
   <th>含义</th> 
   <th>时间复杂度</th> 
  </tr> 
  <tr> 
   <td>get(int index)</td> 
   <td>根据索引获取元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>add(E e)</td> 
   <td>添加元素</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>add(int index, E element)</td> 
   <td>添加元素到指定位置</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>remove(int index)</td> 
   <td>删除索引为index的元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>set(int index, E element)</td> 
   <td>设置索引为index的元素值</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回当前容器元素大小</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>isEmpty()</td> 
   <td>判断容器是否为空</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>contains(Object o)</td> 
   <td>判断是否包含某个元素</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>indexOf(Object o)</td> 
   <td>获取某元素在列表中索引</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>clear()</td> 
   <td>清空列表</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

### 6 add()方法 ###

//添加元素到list末尾.
    public boolean add(E e) {
            //确保list的容量大小，如果当前空间不足，容量加1。
            ensureCapacityInternal(size + 1); 
            //将新元素添加在末尾位置     
            elementData[size++] = e;
            return true;
        }
    
    //在制定位置插入元素。当前位置的元素和index之后的元素向后移一位
    public void add(int index, E element) {
            rangeCheckForAdd(index);
            
            //确保list的容量大小，如果当前空间不足，容量加1。
            ensureCapacityInternal(size + 1);  
            //将index位置之后的元素后移
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            //将元素添加在index位置
            elementData[index] = element;
            //容量加1
            size++;
        }
    
    private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

// 数组容量检查，不够时则进行扩容
    private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    
    // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }
    
    // 数组容量检查，不够时则进行扩容
    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // 确保指定的最小容量 > 数组缓冲区当前的长度 
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
    //扩容，保证ArrayList至少能存储minCapacity个元素
    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);
             //元素内容复制
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
    // 进行大容量分配
    private static int hugeCapacity(int minCapacity) {
            //如果minCapacity<0，抛出异常
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            //如果想要的容量大于MAX_ARRAY_SIZE，则分配Integer.MAX_VALUE，否则分配MAX_ARRAY_SIZE
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

综合上述过程：`add()`方法在添加元素时首先会检查容量空间是否足够，如果不够则进行扩容，扩容之后将元素添加至集合中。

### 7 get()方法 ###

`get()`方法相对简单，不再赘述。

//返回list中索引为index的元素
    public E get(int index) {
            // 检查是否越界
            rangeCheck(index);
            //根据索引返回元素
            return elementData(index);
        }
    
    private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

### 8 remove()方法 ###

`remove()`方法的详细说明已加在源码注释中。

//删除list中位置为指定索引index的元素
    public E remove(int index) {
            //检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
            rangeCheck(index);
            //结构性修改次数+1
            modCount++;
            //记录索引为inde处的元素
            E oldValue = elementData(index);
            // 删除指定元素后，需要左移的元素个数
            int numMoved = size - index - 1;
            //如果有需要左移的元素，就移动（移动后，该删除的元素就已经被覆盖了）
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            // size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
            elementData[--size] = null; // clear to let GC do its work
            //返回被删除的元素
            return oldValue;
        }
    
    private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

### 9 set()方法 ###

//替换指定索引的元素
    public E set(int index, E element) {
            //检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
            rangeCheck(index);
    
            //记录被替换的元素
            E oldValue = elementData(index);
            //替换元素
            elementData[index] = element;
            //返回被替换的元素
            return oldValue;
        }

本篇文章主要分析了ArrayList中数据的增删改查的方法，重点在于ArrarList的扩容方法。