Java中ArrayList实现原理
简述：
- 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
构造方法：
提供了三种方式的构造器：
- public ArrayList() 可以构造一个空列表；
- public ArrayList(int initialCapacity) 构造一个指定初始容量的空列表；
- public ArrayList(Collection<? extends E> c) 构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列；
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方法。
以上是 Java中ArrayList实现原理 的全部内容， 来源链接： utcz.com/z/392000.html
