Java中ArrayList实现原理

时间:2021-02-20 22:06:03

简述:

  • ArrayList可以理解为动态数组,与Java中的数组相比,它的容量能动态增长。超出限制时会增加50%容量,用System.arraycopy()复制到新的数组中,因此最好能给出数组大小的预估值;
  • 容量大小也可以在程序中通过ensureCapacity(int minCapacity)方法来调整;
  • 默认第一次插入元素时创建大小为10的数组(注意,是在插入元素时,而不是new ArrayList时);
  • ArrayList继承了AbstractList,实现了List;实现了RandomAccess接口,即提供了随机访问功能;实现了Cloneable接口,覆盖了clone()方法,能被克隆;实现了Serializable接口,支持序列化;

数据结构:

  使用Object数组实现

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

构造方法:

  提供了三种方式的构造器:

  1. public ArrayList() 可以构造一个空列表;
  2. public ArrayList(int initialCapacity) 构造一个指定初始容量的空列表;
  3. public ArrayList(Collection<? extends E> c) 构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列;
Java中ArrayList实现原理Java中ArrayList实现原理
 1 /**
 2      * Constructs an empty list with the specified initial capacity.
 3      * @param  initialCapacity  the initial capacity of the list
 4      * @throws IllegalArgumentException if the specified initial capacity
 5      *         is negative
 6      */
 7     public ArrayList(int initialCapacity) {
 8         if (initialCapacity > 0) {
 9             this.elementData = new Object[initialCapacity];
10         } else if (initialCapacity == 0) {
11             this.elementData = EMPTY_ELEMENTDATA;
12         } else {
13             throw new IllegalArgumentException("Illegal Capacity: "+
14                                                initialCapacity);
15         }
16     }
17     /**
18      * Constructs an empty list with an initial capacity of ten.
19      */
20     public ArrayList() {
21         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
22     }
23     /**
24      * Constructs a list containing the elements of the specified
25      * collection, in the order they are returned by the collection's
26      * iterator.
27      * @param c the collection whose elements are to be placed into this list
28      * @throws NullPointerException if the specified collection is null
29      */
30     public ArrayList(Collection<? extends E> c) {
31         elementData = c.toArray();
32         if ((size = elementData.length) != 0) {
33             // c.toArray might (incorrectly) not return Object[] (see 6260652)
34             if (elementData.getClass() != Object[].class)
35                 elementData = Arrays.copyOf(elementData, size, Object[].class);
36         } else {
37             // replace with empty array.
38             this.elementData = EMPTY_ELEMENTDATA;
39         }
40     }
View Code

存储:

  1.set(int index, E element)

  该方法首先通过rangeCheck(index)来校验index变量是否超出数组范围,超出则抛出异常。然后取出原index位置的值作为oldValue,并将新的element放入index位置,最后返回oldValue。

 1   public E set(int index, E element) {
 2         rangeCheck(index);
 3         E oldValue = elementData(index);
 4         elementData[index] = element;
 5         return oldValue;
 6     }
 7     private void rangeCheck(int index) {
 8         if (index >= size)
 9             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
10     }
11     E elementData(int index) {
12         return (E) elementData[index];
13     }

  2.add(E e)

  该方法是将指定的元素添加到列表的尾部。首先判断list是否需要扩容,然后再将元素添加到数组中。

 1   public boolean add(E e) {
 2         ensureCapacityInternal(size + 1);  // Increments modCount!!
 3         elementData[size++] = e;
 4         return true;
 5     }
 6     private void ensureCapacityInternal(int minCapacity) {
 7         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 8             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 9         }
10         ensureExplicitCapacity(minCapacity);
11     }
12     private void ensureExplicitCapacity(int minCapacity) {
13         modCount++;
14         // overflow-conscious code
15         if (minCapacity - elementData.length > 0)
16             grow(minCapacity);
17     }
18     private void grow(int minCapacity) {
19         // overflow-conscious code
20         int oldCapacity = elementData.length;
21         // 扩展为原来size的1.5倍大小
22         int newCapacity = oldCapacity + (oldCapacity >> 1);
23         // 如果扩为1.5倍大小仍不能满足需求,则直接扩为需求值(minCapacity)
24         if (newCapacity - minCapacity < 0)
25             newCapacity = minCapacity;
26         if (newCapacity - MAX_ARRAY_SIZE > 0)
27             newCapacity = hugeCapacity(minCapacity);
28         // minCapacity is usually close to size, so this is a win:
29         elementData = Arrays.copyOf(elementData, newCapacity);
30     }
31     private static int hugeCapacity(int minCapacity) {
32         if (minCapacity < 0) // overflow
33             throw new OutOfMemoryError();
34         return (minCapacity > MAX_ARRAY_SIZE) ?
35             Integer.MAX_VALUE :
36             MAX_ARRAY_SIZE;
37     }

删除:

  ArrayList提供了根据下标或者指定对象两种方式的删除功能:

  1.public E remove(int index)

 1     public E remove(int index) {
 2         rangeCheck(index);
 3         modCount++;
 4         E oldValue = elementData(index);
 5         int numMoved = size - index - 1;
 6         if (numMoved > 0)
 7             System.arraycopy(elementData, index+1, elementData, index,
 8                              numMoved);
 9         elementData[--size] = null; // clear to let GC do its work
10         return oldValue;
11     }

  2.public boolean remove(Object o)

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

读取:

  1.get(int index)

  该方法会判断输入的index是否越界,然后将数组的index位置的元素返回即可。

1     public E get(int index) {
2         rangeCheck(index);
3         return elementData(index);
4     }
5     private void rangeCheck(int index) {
6         if (index >= size)
7             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
8     }

扩容:

  扩容代码上边提到过,不再赘述。

  数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长是原容量的1.5倍。

  这种操作的代价还是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。

  如果我们可预知要保存的元素是多少时,要在构造ArrayList实例时,就指定其容量,以避免数组扩容的发生。

  或者根据实际需求,在程序中通过调用ensureCapacity(int minCapacity)方法来手动调整ArrayList实例的容量,如想调整容量的增长策略,可继承ArrayList,并覆盖ensureCapacity方法。