Java集合(一)——ArrayList的源码解读

前言

本文为序列文章:

对于Java中的集合,大致可以分为Set、List、Queue和Map,其中Set是不重复且无序的集合,List是有序,可重复的集合,而Map则代表的是具有映射关系的集合,Java5后增加了Queue集合,代表一种队列集合的实现。

本文主要介绍总结List集合。List是一个有序(插入有序)的Collection(序列),可以包含重复的元素。

List是实现了Collection接口的,所以实现了Collection的方法:

Collection的方法:

QQ截图20180917203606-2018917

List中的方法

QQ截图20180917203750-2018917

操作总结:

  • 位置访问:基于元素的位置来操作元素:如get、set、add、remove等;
  • 搜索:从List中搜索指定的位置,并且返回其位置的索引:如indexOf等;
  • 迭代:Collection继承自Iterable,由于继承的传递性,可以通过Iterable来实现一些遍历操作。listIteratorf方法返回迭代器用于迭代;

Java中的有两种常见的List的实现:ArrayListLinkedList

本文主要介绍ArrayList

ArrayList

ArrayList是基于数组实现的,因为每次add的时候都会去检查容量,自动扩容,那么也可以说是动态扩容的。每个ArrayList实例都有一个变量,用来指向当前List的大小,这个变量就是size。

随着往ArrayList中添加数据的时候,其容量也会自动增加,自动增加会带来数组的拷贝,拷贝会带来额外的空间消耗,那么怎么增加就是一个值得思考的问题了,

QQ截图20180917205342-2018917

如图所示,这里是增加为原来的1.5倍。>>是位操作,表示除以2;

ArrayList的实现

ArrayList内部是基于数组实现的:

QQ截图20180917205541-2018917

构造方法

  • 根据传入的initialCapacity构造一个空的list

QQ截图20180917205731-2018917

  • 默认初始化容量为10的list

QQ截图20180917205738-2018917

ps:这里看不到是默认初始化容量为10的,因为这里的DEFALUTCAPACITY_EMPTY_ELEMENTDATA是一个空的数组,如下:

QQ截图20180917210431-2018917

那么这个构造器的注释说的是初始化为10的容量的数组是在哪实现的呢?

对List的操作需要首先往里面填充数据,那么当填充数据的时候,也就是add方法中,首先会检查容量,ensureCapacityInternal,传入的值为当前的size+1,

QQ截图20180917210723-2018917

随后是这个方法,在这个方法中,如果判断为当前ArrayList底层维护的数组为一个默认的空的数组,就会使用DEFAULT_CAPACITY初始化这个数组。

QQ截图20180917210749-2018917
这就是默认初始化为10的出处。

  • 使用一个Collection集合进行初始化,实际上是调用了Arrays工具类的Copyof方法。

QQ截图20180917205745-2018917

存储

ArrayList提供了如下方法来进行元素的添加:

  • public E set(int index, E element);使用指定的元素替换掉目标位置的元素

首先是边界检查,然后保存原来的位置元素,然后替换,最后返回原来位置的元素。

QQ截图20180917211508-2018917

  • public boolean add(E e);在底层维护的数组的最后添加一个元素e

QQ截图20180917211649-2018917

  • public void add(int index, E element); 在底层维护的数组的指定位置添加一个元素,如果该位置的后面还有元素,调用arrayCopy方法进行后移操作。

QQ截图20180917211733-2018917

  • public boolean addAll(Collection<? extends E> c);在Arraylist底层维护的数组的最后一个位置追加传入的集合。

还是调用的System.arrayCopy方法进行数组的扩充。

QQ截图20180917212017-2018917

  • public boolean addAll(int index, Collection<? extends E> c);在数组的指定位置插入传入的集合,然后原集合index之后的数向后移动。

QQ截图20180917212155-2018917

这里对System的arrayCopy说明一下:
语法如下:

1
2
3
4
5
public static void arraycopy(Object src,
int srcPos,
Object dest,
int destPos,
int length)

示例如下:

1
System.arraycopy(a, 0, elementData, size, numNew);

表示的是将a数组从下标为0开始的数复制到elementData的size位置,复制numNew个数。

读取

返回index位置的元素

QQ截图20180917213428-2018917

删除

ArrayList提供了以下几种删除的方式

  • public E remove(int index);
    删除指定位置的元素
    QQ截图20180917213739-2018917

  • public boolean remove(Object o);
    删除第一个出现o的位置的元素,如果ArrayList中没有这个元素o,那么什么都不会改变返回false

QQ截图20180917213824-2018917

这里的fastRemove的实现原理是直接进行数组的拷贝进行覆盖。

  • public void clear()
    直接清空数组,循环赋值为null,size=0
    QQ截图20180917214012-2018917

扩容

在进行数组的存储中,我们会遇到ensureCapacityInternal方法,该方法可以检查当前是否有足够的空间进行扩容,扩容是调用grow方法:
QQ截图20180917214528-2018917
该方法会将当前的数组的大小扩大为原来的1.5倍,然后调用Arrays的copyOf方法进行扩容,这种操作消耗的空间是比较大的,为此,ArrayList还提供了一个public的方法ensureCapacit允许开发者进行手动的进行扩容。
QQ截图20180917214853-2018917

总结:
对于数组的扩容来说,消耗的成本是比较大的,所以,我们在使用ArrayList的时候,建议根据实际情况调用构造进行初始化数组,或者根据实际情况调用ensureCapacity方法进行手动扩容操作,减少内存开销。

当开发者将数组进行扩容,当时并没有用到那么多的空间的时候,一般会采用trimToSize方法进行调整:

QQ截图20180917215235-2018917

Fail-Fast机制

ArrayList和HashMap一样是采用了Fail-Fast机制,通过记录modCount即操作次数,迭代器在进行操作的时候,如果发现,当前的modCount和自己保存的不一致的时候,那么就会ConcurrentModificationException,而不会冒在将来的不确定的时候出现的不确定行为的风险。

我们注意到

1
protected transient int modCount = 0;

modCount是采用的transient修饰,保证不同进程之间的可见性;
迭代器的操作源码如下:

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
/**
* An optimized version of AbstractList.Itr
这是一个Arraylist 的内部类
*/
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;

Itr() {}

public boolean hasNext() {
return cursor != size;
}

@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
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];
}

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

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。

总结

ArrayList

  • 基于数组,在数组中搜索和读取数据是很快的。因此 ArrayList 获取数据的时间复杂度是O(1);
  • 添加、删除时该元素后面的所有元素都要移动,所以添加/删除数据效率不高。
-------------The End-------------

本文标题:Java集合(一)——ArrayList的源码解读

文章作者:Dimple

发布时间:2018年09月17日 - 20:09

最后更新:2018年09月28日 - 17:09

原始链接:http://www.bianxiaofeng.com/2018/09/17/2018-9-17-20-16-54/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

na,给我一个棒棒糖!
0%