标签：des com http blog style class div img code java size
java 集合系列目录：
Java 集合系列 01
总体框架
Java
集合系列 02 Collection架构
Java
集合系列 03 ArrayList详细介绍(源码解析)和使用示例
Java
集合系列 04 LinkedList详细介绍(源码解析)和使用示例
概要
上一章，我们学习了Collection的架构。这一章开始，我们对Collection的具体实现类进行讲解；首先，讲解List，而List中ArrayList又最为常用。因此，本章我们讲解ArrayList。先对ArrayList有个整体认识，再学习它的源码，最后再通过例子来学习如何使用它。内容包括：
第1部分
ArrayList简介
第2部分 ArrayList数据结构
第3部分 ArrayList源码解析(基于JDK1.6.0_45)
第4部分
ArrayList遍历方式
第5部分 toArray()异常
第6部分 ArrayList示例
第1部分 ArrayList介绍
ArrayList简介
ArrayList
是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List,
RandomAccess, Cloneable, java.io.Serializable这些接口。
ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。
ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList
实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
ArrayList构造函数
// 默认构造函数
ArrayList()
// capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时，容量会添加上一次容量大小的一半。
ArrayList(int capacity)
// 创建一个包含collection的ArrayList
ArrayList(Collection extends E> collection)
ArrayList的API
// Collection中定义的API
boolean add(E object)
boolean addAll(Collection extends E> collection)
void clear()
boolean contains(Object object)
boolean containsAll(Collection> collection)
boolean equals(Object object)
int hashCode()
boolean isEmpty()
Iterator iterator()
boolean remove(Object object)
boolean removeAll(Collection> collection)
boolean retainAll(Collection> collection)
int size()
T[] toArray(T[] array)
Object[] toArray()
// AbstractCollection中定义的API
void add(int location, E object)
boolean addAll(int location, Collection extends E> collection)
E get(int location)
int indexOf(Object object)
int lastIndexOf(Object object)
ListIterator listIterator(int location)
ListIterator listIterator()
E remove(int location)
E set(int location, E object)
List subList(int start, int end)
// ArrayList新增的API
Object clone()
void ensureCapacity(int minimumCapacity)
void trimToSize()
void removeRange(int fromIndex, int toIndex)
第2部分 ArrayList数据结构
ArrayList的继承关系
java.lang.Object
? java.util.AbstractCollection
? java.util.AbstractList
? java.util.ArrayListpublic class ArrayListextends AbstractListimplements List, RandomAccess, Cloneable, java.io.Serializable {}
ArrayList与Collection关系如下图：
ArrayList包含了两个重要的对象：elementData 和 size。
(01) elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数
ArrayList(int
initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，请参考源码分析中的ensureCapacity()函数。
(02) size 则是动态数组的实际大小。
第3部分 ArrayList源码解析(基于JDK1.6.0_45)
为了更了解ArrayList的原理，下面对ArrayList源码代码作出分析。ArrayList是通过数组实现的，源码比较容易理解。
1 package java.util;
2
3 public class ArrayListextends AbstractList 4 implements List, RandomAccess, Cloneable, java.io.Serializable
5 {
6 // 序列版本号
7 private static final long serialVersionUID = 8683452581122892189L;
8
9 // 保存ArrayList中数据的数组
10 private transient Object[] elementData;
11
12 // ArrayList中实际数据的数量
13 private int size;
14
15 // ArrayList带容量大小的构造函数。
16 public ArrayList(int initialCapacity) {
17 super();
18 if (initialCapacity )
19 throw new IllegalArgumentException("Illegal Capacity: "+
20 initialCapacity);
21 // 新建一个数组
22 this.elementData = new Object[initialCapacity];
23 }
24
25 // ArrayList构造函数。默认容量是10。
26 public ArrayList() {
27 this(10);
28 }
29
30 // 创建一个包含collection的ArrayList
31 public ArrayList(Collection extends E> c) {
32 elementData = c.toArray();
33 size = elementData.length;
34 // c.toArray might (incorrectly) not return Object[] (see 6260652)
35 if (elementData.getClass() != Object[].class)
36 elementData = Arrays.copyOf(elementData, size, Object[].class);
37 }
38
39
40 // 将当前容量值设为 =实际元素个数
41 public void trimToSize() {
42 modCount++;
43 int oldCapacity = elementData.length;
44 if (size oldCapacity) {
45 elementData = Arrays.copyOf(elementData, size);
46 }
47 }
48
49
50 // 确定ArrarList的容量。
51 // 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1”
52 public void ensureCapacity(int minCapacity) {
53 // 将“修改统计数”+1
54 modCount++;
55 int oldCapacity = elementData.length;
56 // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1”
57 if (minCapacity > oldCapacity) {
58 Object oldData[] = elementData;
59 int newCapacity = (oldCapacity * 3)/2 + 1;
60 if (newCapacity minCapacity)
61 newCapacity = minCapacity;
62 elementData = Arrays.copyOf(elementData, newCapacity);
63 }
64 }
65
66 // 添加元素e
67 public boolean add(E e) {
68 // 确定ArrayList的容量大小
69 ensureCapacity(size + 1); // Increments modCount!!
70 // 添加e到ArrayList中
71 elementData[size++] = e;
72 return true;
73 }
74
75 // 返回ArrayList的实际大小
76 public int size() {
77 return size;
78 }
79
80 // 返回ArrayList是否包含Object(o)
81 public boolean contains(Object o) {
82 return indexOf(o) >= 0;
83 }
84
85 // 返回ArrayList是否为空
86 public boolean isEmpty() {
87 return size == 0;
88 }
89
90 // 正向查找，返回元素的索引值
91 public int indexOf(Object o) {
92 if (o == null) {
93 for (int i = 0; i )
94 if (elementData[i]==null)
95 return i;
96 } else {
97 for (int i = 0; i )
98 if (o.equals(elementData[i]))
99 return i;
100 }
101 return -1;
102 }
103
104 // 反向查找，返回元素的索引值
105 public int lastIndexOf(Object o) {
106 if (o == null) {
107 for (int i = size-1; i >= 0; i--)
108 if (elementData[i]==null)
109 return i;
110 } else {
111 for (int i = size-1; i >= 0; i--)
112 if (o.equals(elementData[i]))
113 return i;
114 }
115 return -1;
116 }
117
118 // 反向查找(从数组末尾向开始查找)，返回元素(o)的索引值
119 public int lastIndexOf(Object o) {
120 if (o == null) {
121 for (int i = size-1; i >= 0; i--)
122 if (elementData[i]==null)
123 return i;
124 } else {
125 for (int i = size-1; i >= 0; i--)
126 if (o.equals(elementData[i]))
127 return i;
128 }
129 return -1;
130 }
131
132
133 // 返回ArrayList的Object数组
134 public Object[] toArray() {
135 return Arrays.copyOf(elementData, size);
136 }
137
138 // 返回ArrayList的模板数组。所谓模板数组，即可以将T设为任意的数据类型
139 public T[] toArray(T[] a) {
140 // 若数组a的大小 141 // 则新建一个T[]数组，数组大小是“ArrayList的元素个数”，并将“ArrayList”全部拷贝到新数组中
142 if (a.length size)
143 return (T[]) Arrays.copyOf(elementData, size, a.getClass());
144
145 // 若数组a的大小 >= ArrayList的元素个数；
146 // 则将ArrayList的全部元素都拷贝到数组a中。
147 System.arraycopy(elementData, 0, a, 0, size);
148 if (a.length > size)
149 a[size] = null;
150 return a;
151 }
152
153 // 获取index位置的元素值
154 public E get(int index) {
155 RangeCheck(index);
156
157 return (E) elementData[index];
158 }
159
160 // 设置index位置的值为element
161 public E set(int index, E element) {
162 RangeCheck(index);
163
164 E oldValue = (E) elementData[index];
165 elementData[index] = element;
166 return oldValue;
167 }
168
169 // 将e添加到ArrayList中
170 public boolean add(E e) {
171 ensureCapacity(size + 1); // Increments modCount!!
172 elementData[size++] = e;
173 return true;
174 }
175
176 // 将e添加到ArrayList的指定位置
177 public void add(int index, E element) {
178 if (index > size || index )
179 throw new IndexOutOfBoundsException(
180 "Index: "+index+", Size: "+size);
181
182 ensureCapacity(size+1); // Increments modCount!!
183 System.arraycopy(elementData, index, elementData, index + 1,
184 size - index);
185 elementData[index] = element;
186 size++;
187 }
188
189 // 删除ArrayList指定位置的元素
190 public E remove(int index) {
191 RangeCheck(index);
192
193 modCount++;
194 E oldValue = (E) elementData[index];
195
196 int numMoved = size - index - 1;
197 if (numMoved > 0)
198 System.arraycopy(elementData, index+1, elementData, index,
199 numMoved);
200 elementData[--size] = null; // Let gc do its work
201
202 return oldValue;
203 }
204
205 // 删除ArrayList的指定元素
206 public boolean remove(Object o) {
207 if (o == null) {
208 for (int index = 0; index )
209 if (elementData[index] == null) {
210 fastRemove(index);
211 return true;
212 }
213 } else {
214 for (int index = 0; index )
215 if (o.equals(elementData[index])) {
216 fastRemove(index);
217 return true;
218 }
219 }
220 return false;
221 }
222
223
224 // 快速删除第index个元素
225 private void fastRemove(int index) {
226 modCount++;
227 int numMoved = size - index - 1;
228 // 从"index+1"开始，用后面的元素替换前面的元素。
229 if (numMoved > 0)
230 System.arraycopy(elementData, index+1, elementData, index,
231 numMoved);
232 // 将最后一个元素设为null
233 elementData[--size] = null; // Let gc do its work
234 }
235
236 // 删除元素
237 public boolean remove(Object o) {
238 if (o == null) {
239 for (int index = 0; index )
240 if (elementData[index] == null) {
241 fastRemove(index);
242 return true;
243 }
244 } else {
245 // 便利ArrayList，找到“元素o”，则删除，并返回true。
246 for (int index = 0; index )
247 if (o.equals(elementData[index])) {
248 fastRemove(index);
249 return true;
250 }
251 }
252 return false;
253 }
254
255 // 清空ArrayList，将全部的元素设为null
256 public void clear() {
257 modCount++;
258
259 for (int i = 0; i )
260 elementData[i] = null;
261
262 size = 0;
263 }
264
265 // 将集合c追加到ArrayList中
266 public boolean addAll(Collection extends E> c) {
267 Object[] a = c.toArray();
268 int numNew = a.length;
269 ensureCapacity(size + numNew); // Increments modCount
270 System.arraycopy(a, 0, elementData, size, numNew);
271 size += numNew;
272 return numNew != 0;
273 }
274
275 // 从index位置开始，将集合c添加到ArrayList
276 public boolean addAll(int index, Collection extends E> c) {
277 if (index > size || index )
278 throw new IndexOutOfBoundsException(
279 "Index: " + index + ", Size: " + size);
280
281 Object[] a = c.toArray();
282 int numNew = a.length;
283 ensureCapacity(size + numNew); // Increments modCount
284
285 int numMoved = size - index;
286 if (numMoved > 0)
287 System.arraycopy(elementData, index, elementData, index + numNew,
288 numMoved);
289
290 System.arraycopy(a, 0, elementData, index, numNew);
291 size += numNew;
292 return numNew != 0;
293 }
294
295 // 删除fromIndex到toIndex之间的全部元素。
296 protected void removeRange(int fromIndex, int toIndex) {
297 modCount++;
298 int numMoved = size - toIndex;
299 System.arraycopy(elementData, toIndex, elementData, fromIndex,
300 numMoved);
301
302 // Let gc do its work
303 int newSize = size - (toIndex-fromIndex);
304 while (size != newSize)
305 elementData[--size] = null;
306 }
307
308 private void RangeCheck(int index) {
309 if (index >= size)
310 throw new IndexOutOfBoundsException(
311 "Index: "+index+", Size: "+size);
312 }
313
314
315 // 克隆函数
316 public Object clone() {
317 try {
318 ArrayList v = (ArrayList) super.clone();
319 // 将当前ArrayList的全部元素拷贝到v中
320 v.elementData = Arrays.copyOf(elementData, size);
321 v.modCount = 0;
322 return v;
323 } catch (CloneNotSupportedException e) {
324 // this shouldn‘t happen, since we are Cloneable
325 throw new InternalError();
326 }
327 }
328
329
330 // java.io.Serializable的写入函数
331 // 将ArrayList的“容量，所有的元素值”都写入到输出流中
332 private void writeObject(java.io.ObjectOutputStream s)
333 throws java.io.IOException{
334 // Write out element count, and any hidden stuff
335 int expectedModCount = modCount;
336 s.defaultWriteObject();
337
338 // 写入“数组的容量”
339 s.writeInt(elementData.length);
340
341 // 写入“数组的每一个元素”
342 for (int i=0; i)
343 s.writeObject(elementData[i]);
344
345 if (modCount != expectedModCount) {
346 throw new ConcurrentModificationException();
347 }
348
349 }
350
351
352 // java.io.Serializable的读取函数：根据写入方式读出
353 // 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
354 private void readObject(java.io.ObjectInputStream s)
355 throws java.io.IOException, ClassNotFoundException {
356 // Read in size, and any hidden stuff
357 s.defaultReadObject();
358
359 // 从输入流中读取ArrayList的“容量”
360 int arrayLength = s.readInt();
361 Object[] a = elementData = new Object[arrayLength];
362
363 // 从输入流中将“所有的元素值”读出
364 for (int i=0; i)
365 a[i] = s.readObject();
366 }
367 }
总结：
(01) ArrayList
实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。
(02)
当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 +
1”。
(03)
ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
(04)
ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
第4部分 ArrayList遍历方式
ArrayList支持3种遍历方式
(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
(02)
第二种，随机访问，通过索引值去遍历。
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。
Integer value = null;
int size = list.size();
for (int i=0; i) {
value = (Integer)list.get(i);
}
(03) 第三种，for循环遍历。如下：
Integer value = null;
for (Integer integ:list) {
value = integ;
}
下面通过一个实例，比较这3种方式的效率，实例代码(ArrayListRandomAccessTest.java)如下：
1 import java.util.*;
2 import java.util.concurrent.*;
3
4 /*
5 * @desc ArrayList遍历方式和效率的测试程序。
6 *
7 * @author
8 */
9 public class ArrayListRandomAccessTest {
10
11 public static void main(String[] args) {
12 List list = new ArrayList();
13 for (int i=0; i)
14 list.add(i);
15 //isRandomAccessSupported(list);
16 iteratorThroughRandomAccess(list) ;
17 iteratorThroughIterator(list) ;
18 iteratorThroughFor2(list) ;
19
20 }
21
22 private static void isRandomAccessSupported(List list) {
23 if (list instanceof RandomAccess) {
24 System.out.println("RandomAccess implemented!");
25 } else {
26 System.out.println("RandomAccess not implemented!");
27 }
28
29 }
30
31 public static void iteratorThroughRandomAccess(List list) {
32
33 long startTime;
34 long endTime;
35 startTime = System.currentTimeMillis();
36 for (int i=0; i) {
37 list.get(i);
38 }
39 endTime = System.currentTimeMillis();
40 long interval = endTime - startTime;
41 System.out.println("iteratorThroughRandomAccess：" + interval+" ms");
42 }
43
44 public static void iteratorThroughIterator(List list) {
45
46 long startTime;
47 long endTime;
48 startTime = System.currentTimeMillis();
49 for(Iterator iter = list.iterator(); iter.hasNext(); ) {
50 iter.next();
51 }
52 endTime = System.currentTimeMillis();
53 long interval = endTime - startTime;
54 System.out.println("iteratorThroughIterator：" + interval+" ms");
55 }
56
57
58 public static void iteratorThroughFor2(List list) {
59
60 long startTime;
61 long endTime;
62 startTime = System.currentTimeMillis();
63 for(Object obj:list)
64 ;
65 endTime = System.currentTimeMillis();
66 long interval = endTime - startTime;
67 System.out.println("iteratorThroughFor2：" + interval+" ms");
68 }
69 }
运行结果：
iteratorThroughRandomAccess：3
ms
iteratorThroughIterator：8
ms
iteratorThroughFor2：5 ms
由此可见，遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！
第5部分 toArray()异常
当我们调用ArrayList中的 toArray()，可能遇到过抛出“java.lang.ClassCastException”异常的情况。下面我们说说这是怎么回事。
ArrayList提供了2个toArray()函数：
Object[] toArray()
T[] toArray(T[] contents)
调用 toArray() 函数会抛出“java.lang.ClassCastException”异常，但是调用 toArray(T[]
contents) 能正常返回 T[]。
toArray() 会抛出异常是因为 toArray() 返回的是 Object[] 数组，将 Object[]
转换为其它类型(如如，将Object[]转换为的Integer[])则会抛出“java.lang.ClassCastException”异常，因为Java不支持向下转型。具体的可以参考前面ArrayList.java的源码介绍部分的toArray()。
解决该问题的办法是调用
T[] toArray(T[] contents) ， 而不是 Object[] toArray()。
调用 toArray(T[] contents) 返回T[]的可以通过以下几种方式实现。
// toArray(T[] contents)调用方式一
public static Integer[] vectorToArray1(ArrayList v) {
Integer[] newText = new Integer[v.size()];
v.toArray(newText);
return newText;
}
// toArray(T[] contents)调用方式二。最常用！
public static Integer[] vectorToArray2(ArrayList v) {
Integer[] newText = (Integer[])v.toArray(new Integer[0]);
return newText;
}
// toArray(T[] contents)调用方式三
public static Integer[] vectorToArray3(ArrayList v) {
Integer[] newText = new Integer[v.size()];
Integer[] newStrings = (Integer[])v.toArray(newText);
return newStrings;
}
下面使用上述方式二，
1 public class test_1 {
2 public static void main(String[] args){
3 ArrayList ls = new ArrayList();
4 ls.add("a");
5 ls.add("b");
6 ls.add("c");
7 ls.add("d");
8 //重点看下 toArray 的方法
9 String[] obj = (String[]) ls.toArray(new String[0]);
10 for(int i=0;i){
11 System.out.println(obj[i]);
12 }
13 }
14 }
这里重点把 java.util.ArrayList.toArray源码看下：
public T[] toArray(T[] a) {
if (a.length size)
// Make a new array of a‘s runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);