概述
本文是基于jdk8_271版本进行分析的。
ArrayList是Java集合中出场率最多的一个类。底层是基于数组实现，根据元素的增加而动态扩容，可以理解为它是加强版的数组。ArrayList允许元素为null。它是线程不安全的。
数据结构
-
实现继承关系
1 public class ArrayList extends AbstractList
2 implements List, RandomAccess, Cloneable, java.io.Serializable
- AbstractList：继承AbstractList抽象类，使用实现的公共方法
- List：实现List接口操作规范，增、删、遍历等操作
- RandomAccess：提供随机访问功能
- Cloneable：提供可拷贝功能
- Serializable：提供可序列化功能
这里有人会问为什么继承了AbstractList还要实现List接口（这个问题无关紧要，可以忽略），我在stackoverflow一个帖子看到了这个问题，有兴趣可以点击查看。
-
静态变量
1 // 默认初始化容量的大小
2 private static final int DEFAULT_CAPACITY = 10; 3 // 空数组
4 private static final Object[] EMPTY_ELEMENTDATA = {}; 5 // 空数组，与EMPTY_ELEMENTDATA 区分开，无参构造时候会使用该空数组（jdk1.7是只有EMPTY_ELEMENTDATA的）
6 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 7 // 容量最大值。-8是因为一些虚拟机在数组中保留一些标题字，尝试分配更大的数组可能会导致OOM
8 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
-
成员变量
1 transient Object[] elementData; //存放数组元素，transient表示该字段不进行序列化操作
2 private int size; //数组中实际存放元素的个数
-
构造方法
无参构造使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组；带参构造初始化长度为0，使用的是EMPTY_ELEMENTDATA空数组。
1 // 带参构造，指定初始化容量大小
2 public ArrayList(int initialCapacity) { 3 if (initialCapacity > 0) {
4 this.elementData = new Object[initialCapacity]; 5 } else if (initialCapacity == 0) {
6 this.elementData = EMPTY_ELEMENTDATA; 7 } else { 8 throw new IllegalArgumentException("Illegal Capacity: "+
9 initialCapacity); 10 } 11 } 12
13 // 无参构造，elementData 使用默认空数组
14 public ArrayList() { 15 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 16 } 17
18 // 有参构造。传入一个集合
19 public ArrayList(Collection<? extends E> c) { 20 Object[] a = c.toArray(); 21 if ((size = a.length) != 0) { 22 if (c.getClass() == ArrayList.class) { 23 elementData = a; 24 } else { 25 elementData = Arrays.copyOf(a, size, Object[].class); 26 } 27 } else { 28 // 如果传入集合长度为0，elementData 用EMPTY_ELEMENTDATA替换
29 elementData = EMPTY_ELEMENTDATA; 30 } 31 }
主要方法解析
- calculateCapacity–扩容方法
// 计算需要的最小容量大小
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity);
} return minCapacity;
} // 确保内部容量，如果容量不足则进行扩容处理
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
} private void ensureExplicitCapacity(int minCapacity) {
modCount++; if (minCapacity - elementData.length > 0) // 如果所需的最小容量值大于现在数组长度，表示需要进行扩容处理
grow(minCapacity);
} // 真正扩容方法
private void grow(int minCapacity) { int oldCapacity = elementData.length; // 原容量大小
int newCapacity = oldCapacity + (oldCapacity >> 1); // 预计扩容的大小；位运算（1.5倍向下取整） // 预计扩容的值与通过计算需要的最小容量值比较，取最大值
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) { if (minCapacity < 0) // overflow
throw new OutOfMemoryError(); // 容量最大值为MAX_ARRAY_SIZE，为什么还会返回 Integer.MAX_VALUE呢？ // 如果minCapacity > MAX_ARRAY_SIZE，说明此时容器大小已经为MAX_ARRAY_SIZE。静态变量说到MAX_ARRAY_SIZE=Integer.MAX_VALUE-8，一些虚拟机在数组中保留一些标题字，尝试分配更大的数组可能会导致OOM。注意只是可能，不是所有的，因为此时数组长度已经是MAX_ARRAY_SIZE了，不如尝试去进行扩容到Integer.MAX_VALUE，说不定就成功了
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
- add–添加元素
注意：在进行添加操作之前，都会先进行判断数组是否需要扩容；入参如果涉及索引，还会判断索引是否越界。
1 public boolean add(E e) { 2 ensureCapacityInternal(size + 1); // Increments modCount!!
3 elementData[size++] = e; 4 return true;
5 }
6 public void add(int index, E element) { 7 rangeCheckForAdd(index);
8
9 ensureCapacityInternal(size + 1); // Increments modCount!!
10 System.arraycopy(elementData, index, elementData, index + 1,size - index); 11 elementData[index] = element; 12 size++; 13 } 14
15 public boolean addAll(Collection<? extends E> c) { 16 Object[] a = c.toArray(); 17 int numNew = a.length; 18 ensureCapacityInternal(size + numNew); // Increments modCount
19 System.arraycopy(a, 0, elementData, size, numNew); 20 size += numNew; 21 return numNew != 0; 22 } 23 public boolean addAll(int index, Collection<? extends E> c) { 24 rangeCheckForAdd(index); 25
26 Object[] a = c.toArray(); 27 int numNew = a.length; 28 ensureCapacityInternal(size + numNew); // Increments modCount
29
30 int numMoved = size - index; 31 if (numMoved > 0) 32 System.arraycopy(elementData, index, elementData, index + numNew, 33 numMoved); 34
35 System.arraycopy(a, 0, elementData, index, numNew); 36 size += numNew; 37 return numNew != 0; 38 }
- remove–删除元素
删除元素时，如果该索引位后面有元素，则将后面元素向前移动一位（如果删除n个，则向后面元素向前移动n位），同时将数组最后一位数值置为null。
1 public E remove(int index) { 2 rangeCheck(index);
3
4 modCount++;
5 E oldValue = elementData(index); 6
7 int numMoved = size - index - 1;
8 if (numMoved > 0)
9 System.arraycopy(elementData, index+1, elementData, index,
10 numMoved);
11 elementData[--size] = null; // clear to let GC do its work
12
13 return oldValue; 14 }
15 public boolean remove(Object o) { 16 if (o == null) {
17 for (int index = 0; index < size; index++)
18 if (elementData[index] == null) {
19 fastRemove(index);
20 return true;
21 }
22 } else { 23 for (int index = 0; index < size; index++)
24 if (o.equals(elementData[index])) { 25 fastRemove(index);
26 return true;
27 }
28 }
29 return false;
30 }
31
32 private void fastRemove(int index) { 33 modCount++;
34 int numMoved = size - index - 1;
35 if (numMoved > 0)
36 System.arraycopy(elementData, index+1, elementData, index,
37 numMoved);
38 elementData[--size] = null; // clear to let GC do its work
39 }
40
41 public void clear() { 42 modCount++;
43
44 // clear to let GC do its work
45 for (int i = 0; i < size; i++)
46 elementData[i] = null;
47
48 size = 0;
49 }
50
51 protected void removeRange(int fromIndex, int toIndex) { 52 modCount++;
53 int numMoved = size - toIndex; 54 System.arraycopy(elementData, toIndex, elementData, fromIndex,
55 numMoved);
56
57 // clear to let GC do its work
58 int newSize = size - (toIndex-fromIndex);
59 for (int i = newSize; i < size; i++) {
60 elementData[i] = null;
61 }
62 size = newSize; 63 }
64
65 // 从此列表中删除指定集合c中包含的所有元素
66 public boolean removeAll(Collection<?> c) { 67 Objects.requireNonNull(c);
68 return batchRemove(c, false);
69 }
70 // 此列表中仅保留包含在指定集合中的元素
71 public boolean retainAll(Collection<?> c) { 72 Objects.requireNonNull(c);
73 return batchRemove(c, true);
74 }
75 // ArrayList的批量删除算法
76 private boolean batchRemove(Collection<?> c, boolean complement) { 77 final Object[] elementData = this.elementData;
78 int r = 0, w = 0;
79 boolean modified = false;
80 try { 81 for (; r < size; r++)
82 if (c.contains(elementData[r]) == complement) 83 elementData[w++] = elementData[r]; 84 } finally { 85 // Preserve behavioral compatibility with AbstractCollection, 86 // even if c.contains() throws.
87 if (r != size) { 88 System.arraycopy(elementData, r,
89 elementData, w,
90 size - r); 91 w += size - r; 92 }
93 if (w != size) { 94 // clear to let GC do its work
95 for (int i = w; i < size; i++)
96 elementData[i] = null;
97 modCount += size - w; 98 size = w; 99 modified = true; 100 } 101 } 102 return modified; 103 }
- clone–拷贝方法
public Object clone() { try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0; return v;
} catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
- writeObject/readObject–序列化方法
1 private void writeObject(java.io.ObjectOutputStream s) 2 throws java.io.IOException{ 3 // Write out element count, and any hidden stuff
4 int expectedModCount = modCount; 5 s.defaultWriteObject();
6
7 // Write out size as capacity for behavioural compatibility with clone()
8 s.writeInt(size);
9
10 // Write out all elements in the proper order.
11 for (int i=0; i<size; i++) { 12 s.writeObject(elementData[i]); 13 } 14
15 if (modCount != expectedModCount) { 16 throw new ConcurrentModificationException(); 17 } 18 } 19
20 private void readObject(java.io.ObjectInputStream s) 21 throws java.io.IOException, ClassNotFoundException { 22 elementData = EMPTY_ELEMENTDATA; 23
24 // Read in size, and any hidden stuff
25 s.defaultReadObject(); 26
27 // Read in capacity
28 s.readInt(); // ignored
29
30 if (size > 0) { 31 // be like clone(), allocate array based upon size not capacity
32 ensureCapacityInternal(size); 33
34 Object[] a = elementData; 35 // Read in all elements in the proper order.
36 for (int i=0; i<size; i++) { 37 a[i] = s.readObject(); 38 } 39 } 40 }
附录
ArrayList源码详细注释Github地址：https://github.com/y2ex/jdk-source/blob/jdk1.8.0_271/src/main/java/java/util/ArrayList.java
jdk1.8源码Github地址：https://github.com/y2ex/jdk-source/tree/jdk1.8.0_271
作者：Yanci丶
出处：https://www.cnblogs.com/Y2EX/p/14784959.html
點(diǎn)擊查看更多內(nèi)容
為 TA 點(diǎn)贊
評論
評論
共同學(xué)習(xí)，寫下你的評論
評論加載中...
作者其他優(yōu)質(zhì)文章
正在加載中
感謝您的支持，我會繼續(xù)努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進(jìn)行掃碼打賞哦