ArrayList源码分析

Java版本:

1
2
3
java version "1.7.0_79"
Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)

ArrayList采用动态数组实现。

ArrayList主要成员变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 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 == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
* 底层存储数据的数组
*/
private transient Object[] elementData;

/**
* The size of the ArrayList (the number of elements it contains).
* 大小
* @serial
*/
private int size;

其中,transient表示: java 的transient关键字为我们提供了便利,你只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。

ArrayList扩容核心代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  /**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @paramminCapacity the desired minimum capacity
*/
privatevoid grow(int minCapacity) {
// overflow-conscious code
intoldCapacity=elementData.length;
intnewCapacity=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);
}

ArrayList默认初始容量为10,扩容机制:oldCapacity+ (oldCapacity>> 1); (初始容量*1.5),
最终的数组复制均是通过System.arraycopy()方法来复制,
其中native表示 “A native method is a Java method whose implementation is provided by non-java code.”
public static native void arraycopy(Object src,int srcPos,Object dest,int destPos,int length);

add()、remove()方法最终均调用System.arraycopy()来实现。

add()/get()/remove()方法举例:

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
/**
* Appends the specified element to the end of this list.
*
*@parame 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;
returntrue;
}

private void ensureCapacityInternal(int minCapacity) {
if(elementData==EMPTY_ELEMENTDATA) {
minCapacity= Math.max(DEFAULT_CAPACITY,minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

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

/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
*@paramindex the index of the element to be removed
*@returnthe element that was removed from the list
*@throwsIndexOutOfBoundsException{@inheritDoc}
*/
publicE remove(int index) {
rangeCheck(index);

modCount++;
EoldValue= elementData(index);

intnumMoved=size-index- 1;
if(numMoved> 0)
System.arraycopy(elementData,index+1,elementData,index,
numMoved);
elementData[--size] =null;// clear to let GC do its work

returnoldValue;
}

@SuppressWarnings("unchecked")
E elementData(int index) {
return (E)elementData[index];
}

/**
* Returns the element at the specified position in this list.
*
*@param index index of the element to return
*@returnthe element at the specified position in this list
*@throwsIndexOutOfBoundsException{@inheritDoc}
*/
publicE get(int index) {
rangeCheck(index);

return elementData(index);
}