JDK1.8 ArrayList底层分析

1.概览

ArrayList底层是由数组实现的。实现RandomAccess接口,因此支持随机访问。也就是说获取元素的时间复杂度为O(1)。而删除或者增加会造成数组元素的移动,时间复杂度为O(N)。

2.扩容

当添加元素后长度大于当前的Capacity容量时,会对原来的长度扩容1.5倍。oldCapacity + (oldCapacity >> 1), 调用Array.copyOf( elementData , newCapacity ),该操作比较耗时间和性能,所以避免扩容。可以在已知长度情况下,指定长度初始化ArrayList。

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
public boolean add(E e) { 

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

private void ensureCapacityInternal(int minCapacity) {

if (elementData == DEFAULTCAPACITY_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);

}

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

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);

}

3.删除元素

是利用System.arrayCopy(),将index+1后面的元素复杂到index位置上,而该操作的时间复杂度为O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E remove(int index) { 

rangeCheck(index);

modCount++;

E oldValue = elementData(index);

int numMoved = size - index - 1;

if (numMoved > 0)

System.arraycopy(elementData, index+1, elementData, index, numMoved);

elementData[--size] = null; // clear to let GC do its work

return oldValue;

}

以下LinArrayList是我自己实现的基础增删改查的ArrayList。附上了每个步骤的说明解释,用于理解ArrayList。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
public class LinArrayList<E> implements java.io.Serializable {

/* 数组大小 */

private int size;

/** 存放数据的数组 */

private Object[] elementData;

/**

* 空数据

*/

private static Object[] EMPTY_ELEMENT_DATA = {};

/**

* 初始容量

*/

private static int INIT_ARRAY_MIN_CAPACITY = 10;

/**

* 最大容量

*/

private static int ARRAY_MAX_CAPACITY = Integer.MAX_VALUE - 8;

public LinArrayList() {

elementData = EMPTY_ELEMENT_DATA;

}

public E add(E element){

/**

* 一、判断当前是否需要扩容,需则扩容

* 若当前列表为空,则扩容最小的size值

* 判断++size是否大于elementData.length

* 二、扩容

* 1.让当前elementData.length扩容到1.5倍。 newCapacity = length + length >> 1

* 2.若NewCapacity > MAX_CAPACITY_SIZE,则 NewCapacity = MAX_CAPACITY_SIZE

* 3.调用Array.copyof(elementData , newCapacity)

*

* 三、赋值

* elementData[size++] = element;

*/

int minCapacity = size + 1;

if( elementData == EMPTY_ELEMENT_DATA ){

minCapacity = Math.max( INIT_ARRAY_MIN_CAPACITY , minCapacity );

}

if( minCapacity - elementData.length > 0 ){

//扩容1.5倍 = e + ( 0.5 = e >> 1)

int newCapacity = elementData.length + ( elementData.length >> 1 );

//初始化时10会大于newCapacity

if( newCapacity < minCapacity ){

newCapacity = minCapacity;

}

//若新的容量大于最大容量

if( newCapacity > ARRAY_MAX_CAPACITY ){

newCapacity = ARRAY_MAX_CAPACITY;

}

//扩容

elementData = Arrays.copyOf( elementData , newCapacity );

}

elementData[ size++ ] = element;

return element;

}

public E remove(int index){

/**

* 一、获取index的element

* 二、调用System.arrayCopy(elementData , srcPos , elementData , index , numMoved);

* 从srcPos开始的numMoved个元素移到到从index开始的元素

* 三、将最后一个元素致空,让gc回收。elementData[--size] = null

*/

E element = get( index );

System.arraycopy( elementData , index + 1 , elementData , index , size - index - 1 );

//让gc回收

elementData[ --size ] = null;

return element;

}

public E get(int index){

/**

* 1.判断index - size > 0

* 2.return elementData[index]

*/

if( index >= size ){

throw new IndexOutOfBoundsException("out of length ");

}

return (E) elementData[ index ];

}

public int size(){

return size;

}

}

常见面试题

1.什么情况下会发生ConcurrentModificationException异常?

首先要明白为什么会发生ConcurrentModificationException异常?

是modCount和expectedModCount不相等造成的

modCount是记录list中修改的次数

expectedModCount是Iterator类的一个属性,用来比较当前Iterator与List的ModCount是否相等,不相等则证明原List被修改了,与Iterator不一致。

1
2
3
4
5
6
7
final void checkForComodification() { 

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

而modCount在list增加或者删除时会+1

那expectedModcount什么时候被修改呢?

1.当初始化Iteraotr时

1
2
3
4
5
6
7
private class Itr implements Iterator<E> { 

int cursor; // index of next element to return

int lastRet = -1; // index of last element returned; -1 if no such

int expectedModCount = modCount;

2.当Iterator调用remove()时,会将list中modCount赋值给expectedModCount。前提是expectedModCount=modCount,因为赋值之前调用了checkForComodification方法

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
public void remove() { 

if (lastRet < 0)

throw new IllegalStateException();

checkForComodification();

try {

ArrayList.this.remove(lastRet);

cursor = lastRet;

lastRet = -1;

expectedModCount = modCount;

} catch (IndexOutOfBoundsException ex) {

throw new ConcurrentModificationException();

}

}

1.2可得,如果初始化完Iterator后,list有修改则会发生expectedModCount与modCount不相等的情况

下面有几个删除list中元素的例子,来说明下modCount和expectedModCount的变化,参考了关于面试题“ArrayList循环remove()要用Iterator”的研究

可以先看上面那一篇文章的代码分析。接下来的说明是建立那篇文章而进行总结。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
List<Integer> list = new ArrayList<>(); 

list.add(1);

list.add(2);

list.add(3);

list.add(4);

//循环remove()的4种情况的代码片段:

//当前modCount = 5

//#1

//初始化Iterator后, modCount = 5, expectedModCount = 5

Iterator<Integer> iterator = list.iterator();

while(iterator.hasNext()) {

Integer integer = iterator.next();

list.remove(integer);//因为list.remove会修改list,则modcount + = 1 ,现在modCount = 6 , expectedModCount = 5,结果modCount!=expectedModCount

}

结果:

Exception in thread "main" java.util.ConcurrentModificationException

at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)

at java.util.ArrayList$Itr.next(ArrayList.java:851);

//#2

//foreach循环实际也是用的也是Iterator,所以跟#1一样

for (Integer integer : list) {

list.remove(integer);

}

结果:

Exception in thread "main" java.util.ConcurrentModificationException

at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)

at java.util.ArrayList$Itr.next(ArrayList.java:851);

//#3

//虽然没报错,但是与我们实际要的结果不一样

for (int i = 0; i < list.size(); i++) {

list.remove(i);

}

System.out.println(list);

结果:

[2, 4] ;

//#4

Iterator<Integer> iterator = list.iterator();//初始化Iterator,modCount = 5, expectedModCount = 5

while (iterator.hasNext()){

iterator.next();

iterator.remove();//remove方法内部实现,modCount += 1 , expectedModCount = modCount

}

System.out.println(list.size());

结果:正确 ;

0 ;

//#5

//从后往前删除元素

for(int i= list.size() -1 ; i >= 0 ; i--){

list.remove(i);

}

System.out.println(list.size());

结果:正确 ;

0 ;

//#6

//一直删除第一个元素

for(int i= list.size() ; i > 0 ; i--){

list.remove(0);

}

System.out.println(list.size());

结果:正确 ;

0 ;

  集合

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×