ArrayList源码分析
ArrayList集合底层数据结构
ArrayList是由可调整大小的数组实现的，与数组不同的是：数组一旦初始化长度就不可以发生改变，而ArrayList长度可变。
数组特点：
- 增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
- 查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。
ArrayList继承关系
1 | public class ArrayList<E> extends AbstractList<E> |
Serializable标记性接口
- 类的序列化由实现java.io.Serializable接口的类启用。 不实现此接口的类将不会使任何状态序列化或反序列化。 可序列化类的所有子类型都是可序列化的。 序列化接口没有方法或字段，仅用于标识可串行化的语义。
序列化：将对象的数据写入到文件(写对象)。
反序列化：将文件中对象的数据读取出来(读对象)。
Serializable源码：
1
2public interface Serializable {
}
Cloneable 标记性接口
一个类实现 Cloneable 接口来指示 Object.clone() 方法，该方法对于该类的实例进行字段的复制是合法的。在不实现 Cloneable 接口的实例上调用对象的克隆方法会导致异常 CloneNotSupportedException 被抛出。简言：克隆就是依据已经有的数据，创造一份新的完全一样的数据拷贝。
Cloneable源码：
1 | public interface Cloneable { |
- 克隆的前提条件
被克隆对象所在的类必须实现 Cloneable 接口
必须重写 clone 方法
clone源码：
1
2
3
4
5
6
7
8
9
10
11public 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);
}
}
RandomAccess标记接口
此标记接口由 List 实现使用，以表明它们支持快速（通常为恒定时间）随机访问。
此接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能。
AbstractList抽象类
- 该类提供了List接口的骨架实现，以最小化实现由”随机存取”数据存储(如阵列)支持的此接口所需的工作量。对于顺序访问数据 (例如链接列表) ，应该使用AbstractSequentialist优先于此类。
- 要实现一个不可修改的列表，程序员只需要扩展这个类并提供get (int)和size ()方法的实现。
- 要实现可修改的列表，程序员必须另外覆盖set (int, E)方法 (否则将抛出一个UnsupportedoperationException)。如果列表是可变大小， 则程序员必须另外覆盖add (int, E)和remove (int)方法。
ArrayList源码分析
构造方法
| Constructor | Constructor描述 |
|---|---|
| ArrayList() | 构造一个初始容量为十的空列表。 |
| ArrayList(int initialCapacity) | 构造具有指定初始容量的空列表。 |
| ArrayList(Collection<? extends E> c) | 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回 的顺序。 |
在源码分析时首先会将涉及的变量、方法等列出来，之后一块进行详细分析！
无参构造方法
1 | public class ArrayList<E> { |
有参构造方法一
1 | public class ArrayList<E> { |
有参构造方法二
1 |
|
添加方法
| 方法名 | 描述 |
|---|---|
| public boolean add(E e) | 将指定的元素追加到此列表的末尾。 |
| public void add(int index, E element) | 在此列表中的指定位置插入指定的元素。 |
| public boolean addAll(Collection<? extends E> c) | 按指定集合的Iterator返回的顺序将指定集合中的所有元素 追加到此列表的末尾。 |
| public boolean addAll(int index, Collection<? extends E> c) | 将指定集合中的所有元素插入到此列表中，从指定的位置 开始。 |
public boolean add(E e) 添加单个元素：
1
2
3
4
5
6public class ArrayTest {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("程序员");
}
}源码：
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
64public class ArrayList<E> {
//长度为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量为空的数组（无参构造调用）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合真实存元素的数组
Object[] elementData;
//集合的长度
private int size;
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
//将添加的数据传入给 e
public boolean add(E e) {
//调用方法对内部容量进行校验
ensureCapacityInternal(size + 1); //minCapacity=1
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//判断集合存数据的数组是否等于空容量的数组（无参构造肯定两者相等）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//通过最小容量和默认容量 求出较大值 (用于第一次扩容)
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//minCapacity=10
}
//将if中计算出来的容量传递给下一个方法,继续校验
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//实际修改集合次数++ (在扩容的过程中没用,主要是用于迭代器中)
modCount++;
//判断最小容量 - 数组长度是否大于 0
if (minCapacity - elementData.length > 0)
//将第一次计算出来的容量传递给 核心扩容方法(grow)
grow(minCapacity);
}
private void grow(int minCapacity) {
//记录数组的实际长度,此时由于木有存储元素,长度为0
int oldCapacity = elementData.length;
// >> : 右移,右移几位就相当于除以2的几次幂
// << : 左移,左移几位就相当于乘以2的几次幂
//扩容的核心算法: 原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//判断新容量 - 最小容量 是否小于 0, 如果是第一次调用add方法必然小于0
if (newCapacity - minCapacity < 0)
//还是将最小容量赋值给新容量
newCapacity = minCapacity; //newCapacity=10
//判断新容量-最大数组大小 是否>0,如果条件满足就计算出一个超大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给elementData
elementData = Arrays.copyOf(elementData, newCapacity);
}
}public void add(int index, E element) 在指定索引处添加元素 ：
1
2
3
4
5
6
7
8
9
10public class ArrayTest {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("黑马程序员");
list.add("传智播客");
list.add("传智大学");
list.add(1,"长沙校区");
System.out.println(list);
}
}源码：
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
51public class ArrayList<E> {
//长度为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合存元素的数组
Object[] elementData;
//集合的长度
private int size;
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
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++;
}
private void rangeCheckForAdd(int index) {
//超出指定范围就报错
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//增量++ (也就是实际修改集合的次数)
modCount++;
//只有容量不够的情况下才会调用 核心扩容的grow方法
//如果再调用 add(index,element) 方法之前已经扩容,那么源码跟踪到此结束
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
}
public boolean addAll(Collection<? extends E> c)将集合的所有元素一次性添加到集合：
1
2
3
4
5
6
7
8
9
10
11public class ArrayTest {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("黑马程序员");
list.add("传智播客");
list.add("传智大学");
ArrayList<String> list1 = new ArrayList<>();
list1.addAll(list);
}
}源码：
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
34public class ArrayList<E> {
//长度为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合存元素的数组
Object[] elementData;
//集合的长度
private int size;
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
public boolean addAll(Collection<? extends E> c) {
//把有数据的集合转成数组
Object[] a = c.toArray();
//有数据集合长度赋值给numNew
int numNew = a.length;
//调用方法检验是否要扩容,且让增量++
ensureCapacityInternal(size + numNew); // Increments modCount
//调用方法将a数组的元素拷贝到elementData数组中
System.arraycopy(a, 0, elementData, size, numNew);
//集合的长度+=a数组的长度
size += numNew;
//只要a数组的长度不等于0,即说明添加成功
return numNew != 0;
}
}
//结论:底层使用了System.arraycopy方法进行了拷贝public boolean addAll(int index, Collection<? extends E> c) 在指定的索引位置添加集合：
1
2
3
4
5
6
7
8
9
10
11
12
13public class ArrayTest {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("黑马程序员");
list.add("传智播客");
list.add("传智大学");
ArrayList<String> list1 = new ArrayList<>();
list.add("酷丁鱼");
list.add("博学谷")
list1.addAll(l1,ist);
}
}源码：
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
56public class ArrayList<E> {
//长度为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合存元素的数组
Object[] elementData;
//集合的长度
private int size;
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
public boolean addAll(int index, Collection<? extends E> c) {
//校验索引
rangeCheckForAdd(index);
//将数据源转成数组
Object[] a = c.toArray();
//记录数据源的长度 3
int numNew = a.length;
//目的就是为了给集合存储数据的数组进行扩容
ensureCapacityInternal(size + numNew);
//numMoved: 要移动元素的个数 --> 1个
//numMoved: 集合list1的长度-调用addAll的第一个参数 (索引1)
int numMoved = size - index;
//判断需要移动的个数是否大于0
if (numMoved > 0)
//先使用System中的方法arraycopy将需要移动的数据进行移动
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
//将数据源(list)中的所有数据添加到list1中（中间空的位置中）
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
public final class System {
/*参数:
src - 源数组。
srcPos - 源数组中的起始位置。
dest - 目标数组。
destPos - 目的地数据中的起始位置。
length - 要复制的数组元素的数量。 */
public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int 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
25public class ArrayCopyMethodTest {
public static void main(String[] args) {
String[] a = {"黑马程序员","传智播客","传智大学"};
String[] arr = {"酷丁鱼","博学谷",null,null,null,null,null,null,null,null};
//获取数据源的长度 3
int numNew = a.length;
//numMoved = 集合真实长度 - 要存的索引位置
//要移动元素的个数为:1
int numMoved = 2 - 1;
//判断是否需要移动元素
if (numMoved > 0)
//src - 源数组。
//srcPos - 源数组中的起始位置。
//dest - 目标数组。
//destPos - 目的地数据中的起始位置。
//length - 要复制的数组元素的数量
System.arraycopy(arr, 1, arr, 4,
numMoved);
System.out.println(Arrays.toString(arr));
}
}输出：
1
[酷丁鱼, 博学谷, null, null, 博学谷, null, null, null, null, null]
删除方法
public E remove(int index) 根据索引删除元素：
1
2
3
4
5
6
7
8
9
10
11
12
13public class Test01 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("山东大李逵");
list.add("天魁星宋江");
list.add("天罡星卢俊义");
list.add("西门大人");
//根据索引删除元素
String value = list.remove(3);
System.out.println("删除的元素为: "+value);
System.out.println("集合的元素: "+list);
}
}输出：
1
2删除的元素为: 西门大人
集合的元素: [山东大李逵, 天魁星宋江, 天罡星卢俊义]源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public class ArrayList<E> {
public E remove(int index) {
//范围校验
rangeCheck(index);
//增量++
modCount++;
//将index对应的元素赋值给 oldValue
E oldValue = elementData(index);
//计算集合需要移动元素个数
int numMoved = size - index - 1;
//如果需要移动元素个数大于0,就使用arrayCopy方法进行拷贝
//注意:数据源和数据目的都ntData
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将源集合最后一个元素置为null,尽早让垃圾回收机制对其进行回收
elementData[--size] = null;
//返回被删除的元素
return oldValue;
}
}public boolean remove(Object o) 根据元素删除元素：
1
2
3
4
5
6
7
8
9
10
11
12
13public class Test01 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("山东大李逵");
list.add("天魁星宋江");
list.add("西门大人");
list.add("天罡星卢俊义");
//根据索引删除元素效果
boolean flag = list.remove("西门大人");
System.out.println("是否删除成功: "+flag);
System.out.println("集合的元素: "+list);
}
}输出：
1
2是否删除成功: true
集合的元素: [山东大李逵, 天魁星宋江, 天罡星卢俊义]源码：
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
37public class ArrayList<E> {
public boolean remove(Object o) {
//判断要删除的元素是否为null
if (o == null) {
//遍历集合
for (int index = 0; index < size; index++)
//判断集合的元素是否为null
if (elementData[index] == null) {
//如果相等,调用fastRemove方法快速删除
fastRemove(index);
return true;
}
} else {
//遍历集合
for (int index = 0; index < size; index++)
//用o对象的equals方法和集合每一个元素进行比较
if (o.equals(elementData[index])) {
//如果相等,调用fastRemove方法快速删除
fastRemove(index);
return true;
}
}
//如果集合没有o该元素,那么就会返回false
return false;
}
private void fastRemove(int index) {3.5 修改方法
//增量++
modCount++;
//计算集合需要移动元素的个数
int numMoved = size - index - 1;
//如果需要移动的个数大于0,调用arrayCopy方法进行拷贝
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
//将集合最后一个元素置为null,尽早被释放
elementData[--size] = null;
}
}
修改方法
public E set(int index, E element) 根据索引修改集合元素源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public class ArrayList<E> {
public E set(int index, E element) {
//校验索引
rangeCheck(index);
//根据索引取出元素 --> 被替换的元素
E oldValue = elementData(index);
//把element存入到elementData数组中
elementData[index] = element;
//返回被替换的元素
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
获取方法
public E get(int index) 根据索引获取元素源码：
1
2
3
4
5
6
7
8
9
10
11
12
13public class ArrayList<E> {
public E get(int index) {
//校验索引
rangeCheck(index);
//根据索引获取数组(集合)中的元素
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
转换方法
ArrayList中的toString方法继承于它的爷爷类AbstractCollection，继承关系如下：
public String toString() 把集合所有数据转换成字符串源码：
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
42public class ArrayList<E> {
//长度为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合存元素的数组
Object[] elementData;
//集合的长度
private int size;
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
}
//ArrayList集合的亲爷爷类
public abstract class AbstractCollection<E> {
public String toString() {
//获取迭代器
Iterator<E> it = iterator();
//判断迭代器是否有元素
if (! it.hasNext())
return "[]";
//创建StringBuilder
StringBuilder sb = new StringBuilder();
//先追加了'['
sb.append('[');
//无限循环
for (;;) {
//调用迭代器的next方法取出元素,且将光标向下移动
E e = it.next();
//三元判断
sb.append(e == this ? "(this Collection)" : e);//拼接元素
if (! it.hasNext())
//没有元素,在缓冲区的最后追加']',且把整个缓冲区的数据转成字符串
//然后再结束该方法
return sb.append(']').toString();
//有元素,就直接追加
sb.append(',').append(' ');
}
}
}
迭代器
public Iterator
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
62public class ArrayList<E> {
//长度为0的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量为空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合存元素的数组
Object[] elementData;
//集合的长度
private int size;
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
//获取迭代器的方法
public Iterator<E> iterator() {
//创建了一个对象
return new Itr();
}
//ArrayList集合的内部类 --> 迭代器的源码
private class Itr implements Iterator<E> {
int cursor; // 光标,默认值就是0,用来指向元素的位置
int lastRet = -1; // 记录-1
// 将集合实际修改次数赋值给预期修改次数，用来判断并发安全性
int expectedModCount = modCount;
//判断集合是否有元素
public boolean hasNext() {
//即光标不等于size时，证明集合还有元素没有遍历完，而光标等于size时，说明元素遍历完毕。
return cursor != size;
}
//遍历元素
public E next() {
checkForComodification();
//光标（0）赋值给i
int i = cursor; //i=0
//判断,如果大于集合的size就说明没有元素了
if (i >= size)
throw new NoSuchElementException();
//把集合存储数据数组的地址赋值给该方法的局部变量
Object[] elementData = ArrayList.this.elementData;
//进行判断,如果条件满足就会产生并发修改异常
if (i >= elementData.length)
throw new ConcurrentModificationException();
//光标自增
cursor = i + 1;
//从数组中取出元素且返回
return (E) elementData[lastRet = i];
}
//校验预期修改集合次数是否和实际修改集合次数一样
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}案例：已知集合：List list = new ArrayList();里面有三个元素：”hello”、”Java”、”PHP”，使用迭代器遍历集合看有没有”PHP”这个元素，如果有，就使用集合对象删除该元素：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public class Test01 {
public static void main(String[] args) {
//创建集合对象
List<String> list = new ArrayList<String>();
//添加元素
list.add("hello");
list.add("Java");
list.add("PHP");
//获取迭代器
Iterator<String> it = list.iterator();
//遍历集合
while (it.hasNext()) {
String s = it.next();
if(s.equals("PHP")) {
list.remove("PHP");
}
}
}
}控制台结果：并发修改异常：
1
2
3Exception in thread "main" java.util.ConcurrentModificationException at
java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901) at
java.util.ArrayList$Itr.next(ArrayList.java:851) at cn.heu.method.Test01.main(Test01.java:24)源码：
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
77public class ArrayList<E> {
public Iterator<E> iterator() {
return new Itr();
}
//ArrayList内部类
//一定要注意观察 Itr 类中的几个成员变量
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回元素的索引
int lastRet = -1; // 最后一个返回元素的索引
//将实际修改集合次数 赋值 给预期修改次数
//在迭代的过程中,只要实际修改次数和预期修改次数不一致就会产生并发修改异常
//由于expectedModCount是Itr的成员变量,那么只会被赋值一次!!!
//同时由于集合调用了三次add方法,那么实际修改集合次数就是 3,因此 expectedModCount的值也是 3
int expectedModCount = modCount;
//判断集合元素为后面是否还有元素
public boolean hasNext() {
return cursor != size;
}
//获取元素的方法
public E next() {
//每次获取元素,会先调用该方法校验 预期修改次数是否 == 实际修改次数
checkForComodification();
//把下一个元素的索引赋值给i
int i = cursor;
//判断是否有元素
if (i >= size)
throw new NoSuchElementException();
//将集合底层存储数据的数组赋值给迭代器的局部变量 elementData
Object[] elementData = ArrayList.this.elementData;
//再次判断,如果下一个元素的索引大于集合底层存储元素的长度 并发修改异常
if (i >= elementData.length)
throw new ConcurrentModificationException();
//每次成功获取到元素,下一个元素的索引都是当前索引+1
cursor = i + 1;
//返回元素
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
//如果预期修改次数 和 实际修改次数不相等 就产生并发修改异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
//集合的remove方法
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//快速删除方法
private void fastRemove(int index) {
//最最最关键的一个操作,集合实际修改次数++,那么这个时候由原来的3变成4
//but迭代器的预期修改次数还是3!!!
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//还有一个很关键的操作,集合的长度也发生了改变
elementData[--size] = null;
}
}案例二：已知集合：List list = new ArrayList();里面有三个元素：”hello”、”PHP”、”JavaSE”，使用迭代器遍历集合看有没有”PHP”这个元素，如果有，就使用集合对象删除该元素：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public class Test01 {
public static void main(String[] args) {
//创建集合对象
List<String> list = new ArrayList<String>();
//添加元素
list.add("hello");
list.add("PHP");
list.add("Java");
//获取迭代器
Iterator<String> it = list.iterator();
//遍历集合
while (it.hasNext()) {
String s = it.next();
if(s.equals("PHP")) {
list.remove("PHP");
}
}
}
}输出：
1
[hello,Java]
问题：使用迭代器遍历集合的时候，集合自身修改了长度，但是却没有产生并发修改异常！为什么？
default void remove() 迭代器中的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
48public class ArrayList<E> {
public Iterator<E> iterator() {
return new Itr();
}
//ArrayList内部类
//一定要注意观察 Itr 类中的几个成员变量
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回元素的索引
int lastRet = -1; // 最后一个返回元素的索引
//将实际修改集合次数 赋值 给预期修改次数
//在迭代的过程中,只要实际修改次数和预期修改次数不一致就会产生并发修改异常
//由于expectedModCount是Itr的成员变量,那么只会被赋值一次!!!
//同时由于集合调用了三次add方法,那么实际修改集合次数就是 3,因此 expectedModCount的值也是 3
int expectedModCount = modCount;
//判断集合元素为后面是否还有元素
public boolean hasNext() {
return cursor != size;
}
//迭代器删除元素方法
public void remove() {
//判断最后返回元素的索引是否小于0,满足条件就产生 非法状态异常
if (lastRet < 0)
throw new IllegalStateException();
//校验是否会产生并发修改异常,第一次调用不会,因为与其修改次数和实际修改次数一致
checkForComodification();
try {
//真正删除集合元素的方法,调用方法为ArrayList的方法remove,且将0作为参数进行传递
ArrayList.this.remove(lastRet);
//将lastRet赋值给cursor
cursor = lastRet;
//再次等于-1
lastRet = -1;
//再次将集合实际修改次数赋值给预期修改次数,那么这个时候不管集合自身是否删除成功
//那么实际修改次数和预期修改次数又一致了,所以并不会产生并发修改异常
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
//如果预期修改次数 和 实际修改次数不相等 就产生并发修改异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}结论：
- 迭代器remove方法底层调用的还是集合自身的remove方法删除元素；
- 之所以不会产生并发修改异常，其原因是因为在迭代器的remove方法中会再次将集合实际修改次数赋值给预期修改次数 。
清空方法
public void clear() 清空集合所有数据源码：
1
2
3
4
5
6
7
8
9
10
11public class ArrayList<E> {
public void clear() {
//实际修改集合次数++
modCount++;
//遍历集合,将集合每一个索引对应位置上的元素都置为null,尽早让其释放
for (int i = 0; i < size; i++)
elementData[i] = null;
//集合长度更改为0
size = 0;
}
}
包含方法
public boolean contains(Object o) 判断集合是否包含指定元素源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public class ArrayList<E> {
//源码contains方法
public boolean contains(Object o) {
//调用indexOf方法进行查找
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
//如果元素是null,也进行遍历操作
//因为集合中有可能够会存储null
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;
}
//如果没有走if,也没有走else,那么就说明o该元素在集合中不存在
return -1;
}
}
判断集合是否为空
源码分析：
1
2
3
4
5public class ArrayList<E> {
public boolean isEmpty() {
return size == 0;
}
}
面试题
ArrayList是如何扩容的？
见上面的构造方法，简单说就是：第一次扩容10，以后每次都是原容量的1.5倍。
ArrayList频繁扩容导致添加性能急剧下降，如何处理？
解决方法：直接指定一个大容量的集合。但这种优化方式只针对特定的场景，如果添加的元素是少量的、未知的，不推荐使用 。
ArrayList插入或删除元素一定比LinkedList慢么?
根据索引删除 ：ArrayList和LinkedList对比 ：
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
35public class Test02 {
public static void main(String[] args) {
//创建ArrayList集合对象
ArrayList<String> arrayList = new ArrayList<String>();
//添加500W个元素
for (int i = 0; i < 5000000; i++) {
arrayList.add(i+"小黑");
}
//获取开始时间
long startTime = System.currentTimeMillis();
//根据索引删除ArrayList集合元素
//删除索引5000对应的元素
String value = arrayList.remove(50000);
System.out.println(value);
//获取结束时间
long endTime = System.currentTimeMillis();
System.out.println("ArrayList集合删除元素的时间: "+(endTime-startTime));
//创建LinkedList集合对象
LinkedList<String> linkedList = new LinkedList<String>();
//添加500W个元素
for (int i = 0; i < 5000000; i++) {
linkedList.add(i+"小黑");
}
//获取开始时间
startTime = System.currentTimeMillis();
//根据索引删除LinkedList集合元素
//删除索引5000对应的元素
value = arrayList.remove(50000);
System.out.println(value);
endTime = System.currentTimeMillis();
System.out.println("LinkedList集合删除元素的时间: "+(endTime-startTime));
}
}输出：
1
2
3
450000小黑
ArrayList集合删除元素的时间: 10
50001小黑
LinkedList集合删除元素的时间: 44源码分析：
ArrayList根据索引删除元素源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public class ArrayList<E> {
public E remove(int index) {
//范围校验
rangeCheck(index);
//增量++
modCount++;
//将index对应的元素赋值给 oldValue
E oldValue = elementData(index);
//计算集合需要移动元素个数
int numMoved = size - index - 1;
//如果需要移动元素个数大于0,就使用arrayCopy方法进行拷贝
//注意:数据源和数据目的都ntData
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将源集合最后一个元素置为null,尽早让垃圾回收机制对其进行回收
elementData[--size] = null;
//返回被删除的元素
return oldValue;
}
}LinkedList根据索引删除元素源码：
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
84public class LinkedList<E> {
//LinkedList集合删除的方法
public E remove(int index) {
//调用方法校验元素的索引
checkElementIndex(index);
//先调用node(index)方法,找到需要删除的索引
//再调用unlink方法解开链条
return unlink(node(index));
}
//校验索引是否在合法范围之内,不在就报错
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//校验
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//获取要删除的元素
Node<E> node(int index) {
//不管索引是多少,在源码底层都会对整个链表上的元素进行折半的动作
//如果要删除元素的索引小于集合长度的一半,那么就从头节点一个个的往后找
//如果要删除元素的索引大于集合长度的一半,那么就从尾节点一个个的往后找
//(注:这个查找的效率相对于ArrayList集合来说较低)
if (index < (size >> 1)) {
Node<E> x = first;
//从头节点开始往后找
for (int i = 0; i < index; i++)
//获取下一个节点
x = x.next;
//返回找到的节点
return x;
} else {
Node<E> x = last;
//从最后一个位置往前找
for (int i = size - 1; i > index; i--)
//获取前一个节点
x = x.prev;
//返回找到的节点
return x;
}
}
//解开链表,让前后节点相互记录地址
E unlink(Node<E> x) {
//获取要删除的元素
final E element = x.item;
//获取被删除节点下一个节点的地址
final Node<E> next = x.next;
//获取被删除节点下一个节点的地址
final Node<E> prev = x.prev;
//如果被删除节点的上一个节点为null,就让被删除节点的下一个节点成为首节点
if (prev == null) {
first = next;
} else {
//否则,被删除元素上一个节点的 下一个节点 变成 被删除元素的下一个节点
prev.next = next;
//被删除元素的上一个节点置为null,即断开删除元素与上一个元素的链条
x.prev = null;
}
//如果被删除元素的下一个节点为null,最后一个节点就等于被删除元素的上一个节点
if (next == null) {
last = prev;
} else {
//否则,被删除节点的下一个节点 等于被删除节点的前一个节点
next.prev = prev;
//被删除元素的下一个节点置为null,即断开删除元素与后面元素的链条
x.next = null;
}
//被删除元素的内容置为null
x.item = null;
//集合长度--
size--;
//实际修改集合的次数自增
modCount++;
//返回被删除的元素
return element;
}
}结论：
数组删除元素确实要比链表慢，慢在需要创建新数组，还有比较麻烦的数据拷贝，但是在ArrayList底层不是每次操作元素都需要扩容，因此在这个方面相对于链表来说数组的性能更好。
LinkedList删除元素之所以效率并不高，其原理在于底层先需要对整个集合进行折半的动作，然后又需要对集合进行遍历一次，这些操作导致效率变低 。
根据元素删除：ArrayList和LinkedList对比：
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
33public class ArrayTest {
public static void main(String[] args) {
//创建ArrayList集合对象
ArrayList<String> arrayList = new ArrayList<String>();
//添加500W个元素
for (int i = 0; i < 5000000; i++) {
arrayList.add(i+"XXX");
} //获取开始时间
long startTime = System.currentTimeMillis();
//根据元素删除ArrayList集合元素
//删除元素为 "5000XXX"
boolean b = arrayList.remove("5000XXX");
System.out.println("删除的状态: "+b);
//获取结束时间
long endTime = System.currentTimeMillis();
System.out.println("ArrayList集合删除元素的时间: "+(endTime-startTime));
//创建LinkedList集合对象
LinkedList<String> linkedList = new LinkedList<String>();
//添加500W个元素
for (int i = 0; i < 5000000; i++) {
linkedList.add(i+"XXX");
}
//获取开始时间
startTime = System.currentTimeMillis();
//根据元素删除LinkedList集合元素
//删除元素为 "5000XXX"
b = linkedList.remove("5000XXX");
System.out.println("删除的状态: "+b);
endTime = System.currentTimeMillis();
System.out.println("LinkedList集合删除元素的时间: "+(endTime-startTime));
}
}输出：
1
2
3
4删除的状态: true
ArrayList集合删除元素的时间: 10
删除的状态: true
LinkedList集合删除元素的时间: 5ArrayList根据元素删除元素的源码见上面解析！
LinkedList根据元素删除元素 ：
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
49public class LinkedList<E> {
public boolean remove(Object o) {
//判断要删除的元素是否为null
//不管是否为null都从第一个元素开始,从头部往后找
//找到之后,调用unlink方法进行解绑,更改节点和节点之间记录的地址
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
}
ArrayList是线程安全的么？
- ArrayList不是线程安全的。
- 需要线程安全怎么办?
- 使用Collections.synchronizedList(list)
- 使用Vector
如何复制某个ArrayList到另一个ArrayList中去？
- 使用clone()方法
- 使用ArrayList构造方法
- 使用addAll方法
已知成员变量集合存储N多用户名称,在多线程的环境下,使用迭代器在读取集合数据的同时如何保证还可以正常的写入数据到集合？
使用读写分离集合（CopyOnWriteArrayList ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class CollectionThread implements Runnable{
//private static ArrayList<String> list = new ArrayList<String>();
private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
static{
list.add("Jack");
list.add("Lucy");
list.add("Jimmy");
}
public void run() {
for (String value : list) {
System.out.println(value);
//在读取数据的同时又向集合写入数据
list.add("coco");
}
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ZC的学习录！
微信
支付宝
评论