Java 集合 ArrayList 源码 学习 (JDK-1.8)

首先看ArrayList的构造方法

1
2
3
4
5
6
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;


/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}


/**
* Returns <tt>true</tt> if this list contains no elements.
*
* @return <tt>true</tt> if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* 存储ArrayList元素的数组缓冲区。
 * ArrayList的容量是这个数组缓冲区的长度。 任何
 * 使用elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA清空ArrayList
 * 当第一个元素被添加时,将被扩展为DEFAULT_CAPACITY。
*/
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access


/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


/**
* Default initial capacity.
*/
/** 默认长度是10 */
private static final int DEFAULT_CAPACITY = 10;


/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}


/** 确保内部容量 */
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, 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++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}


/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新的容量 = 旧容量 + 旧容量的0.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}


private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

可以看到在调用add方法时,首先检查内部容量,然后再赋值
在扩容时可以看到扩容后是扩容前的1.5倍,原因:int newCapacity = oldCapacity + (oldCapacity >> 1);
在扩容时进行了数组拷贝,所有扩容时非常费内存 elementData = Arrays.copyOf(elementData, newCapacity);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);

return elementData(index);
}


/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}


@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
1
2
3
4
5
6
7
8
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
1
2
3
4
5
6
7
8
/**
* Returns <tt>true</tt> if this list contains no elements.
*
* @return <tt>true</tt> if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

找lastIndexOf的时候倒着找,确实挺优雅的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
*
* @return a clone of this <tt>ArrayList</tt> instance
*/
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);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
* @exception IndexOutOfBoundsException if copying would cause
* access of data outside array bounds.
* @exception ArrayStoreException if an element in the <code>src</code>
* array could not be stored into the <code>dest</code> array
* because of a type mismatch.
* @exception NullPointerException if either <code>src</code> or
* <code>dest</code> is <code>null</code>.
*/
System.arraycopy(Object src, int srcPos,
Object dest, int destPos, int length)

src 原数组
srcPos 原数组开始复制的位置
dest 目标数组
destPos 目标数组起始位置
length 要复制的数组元素个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* Copies the specified array, truncating or padding with nulls (if necessary)
* so the copy has the specified length. For all indices that are
* valid in both the original array and the copy, the two arrays will
* contain identical values. For any indices that are valid in the
* copy but not the original, the copy will contain <tt>null</tt>.
* Such indices will exist if and only if the specified length
* is greater than that of the original array.
* The resulting array is of exactly the same class as the original array.
*
* @param <T> the class of the objects in the array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @since 1.6
*/
@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}


/**
* Copies the specified array, truncating or padding with nulls (if necessary)
* so the copy has the specified length. For all indices that are
* valid in both the original array and the copy, the two arrays will
* contain identical values. For any indices that are valid in the
* copy but not the original, the copy will contain <tt>null</tt>.
* Such indices will exist if and only if the specified length
* is greater than that of the original array.
* The resulting array is of the class <tt>newType</tt>.
*
* @param <U> the class of the objects in the original array
* @param <T> the class of the objects in the returned array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @param newType the class of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @throws ArrayStoreException if an element copied from
* <tt>original</tt> is not of a runtime type that can be stored in
* an array of class <tt>newType</tt>
* @since 1.6
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}


original 要复制的数组
newLength 新数组的长度
newType 新数组的类型

关于对象拷贝有两种方式:浅拷贝(Shallow Copy)和深拷贝(Deep Copy)。顾名思义,浅拷贝,并不拷贝对象本身,仅仅是拷贝指向对象的指针;深拷贝是直接拷贝整个对象内存到另一块内存中。

简单些说:浅拷贝就是指针拷贝;深拷贝就是内容拷贝。

ArrayList总体来说比较简单,不过ArrayList还有以下一些特点:

ArrayList自己实现了序列化和反序列化的方法,因为它自己实现了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法

ArrayList基于数组方式实现,无容量的限制(会扩容)

添加元素时可能要扩容(所以最好预判一下),删除元素时不会减少容量(若希望减少容量,trimToSize()),删除元素时,将删除掉的位置元素置为null,下次gc就会回收这些元素所占的内存空间。

线程不安全

add(int index, E element):添加元素到数组中指定位置的时候,需要将该位置及其后边所有的元素都整块向后复制一位

get(int index):获取指定位置上的元素时,可以通过索引直接获取(O(1))

remove(Object o)需要遍历数组

remove(int index)不需要遍历数组,只需判断index是否符合条件即可,效率比remove(Object o)高

contains(E)需要遍历数组

使用iterator遍历可能会引发多线程异常

1、ArrayList的大小是如何自动增加的?

这是最有技巧性的的一个问题,大多数人都无法回答。事实上,当有人试图在arraylist中增加一个对象的时候,Java会去检查arraylist,以确保已存在的数组中有足够的容量来存储这个新的对象。如果没有足够容量的话,那么就会新建一个长度更长的数组,旧的数组就会使用Arrays.copyOf方法被复制到新的数组中去,现有的数组引用指向了新的数组。看如下的代码段(摘自GrepCode.com中的Java ArrayList Code):

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java

//ArrayList Add方法:
public boolean add(E e){
ensureCapacity(size+1); //Increment modCount!!
elementData[size++] = e;
return true;
}

//ensureCapacity方法:处理ArrayList的大小
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}

请注意这样一个情况:新建了一个数组;新数组长度是旧数组的1.5倍,旧数组的对象被复制到了新的数组中,并且现有的数组指向新的数组。

2、什么情况下会使用ArrayList?什么时候会选择LinkedList?

多数情况下,当你遇到访问元素比插入或者是删除元素更加频繁的时候,你应该使用ArrayList。
另外一方面,当你在某个特别的索引中,插入或者是删除元素更加频繁,或者你压根就不需要访问元素的时候,会选择LinkedList。
在ArrayList中访问元素的最糟糕的时间复杂度是”1″,而在LinkedList中可能就是”n”了。
在ArrayList中增加或者删除某个元素,通常会调用System.arraycopy方法,这是一种极为消耗资源的操作,
因此,在频繁的插入或者是删除元素的情况下,LinkedList的性能会更加好一点。

3、当传递ArrayList到某个方法中,或者某个方法返回ArrayList,什么时候要考虑安全隐患?如何修复安全违规这个问题呢?

当array被当做参数传递到某个方法中,如果array在没有被复制的情况下直接被分配给了成员变量,那么就可能发生这种情况,即当原始的数组被调用的方法改变的时候,传递到这个方法中的数组也会改变。下面的这段代码展示的就是安全违规以及如何修复这个问题。

ArrayList被直接赋给成员变量——安全隐患:

修复这个安全隐患:

4、如何复制某个ArrayList到另一个ArrayList中去?

下面就是把某个ArrayList复制到另一个ArrayList中去的几种技术:

使用clone()方法,比如ArrayList newArray = oldArray.clone();
使用ArrayList构造方法,比如:ArrayList myObject = new ArrayList(myTempObject);
使用Collection的copy方法。

注意1和2是浅拷贝(shallow copy)。

5、在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?

在ArrayList中增加或者是删除元素,要调用System.arraycopy这种效率很低的操作,
如果遇到了需要频繁插入或者是删除的时候,可以选择其他的Java集合,比如LinkedList。

References

[1] ArrayList源码分析(基于JDK8)
[2] 浅拷贝(Shallow Copy)与深拷贝(Deep Copy)
[3] Java中shallow clone 与deep Clone的区别