0%

Java-ArrayList

本章是整理知识内容,为强化知识长期更新。

List 是是一个有序的集合,是Collection的实现类之一。

概述

  • list接口是Java Collection Framework的成员。
  • 列队允许添加重复的元素。
  • 列队允许null存在。
  • 列队是从0开始,也就是列队头元素的下标是0。
  • 列队支持泛型,这样可以避免ClassCastException异常。

数组与数组列表

​ Array(数组)它是在内存中划分出一块连续的地址空间进行元素的存储,由于它直接操作内存,所以性能比其他的集合要高一点点。但是数组也有一个严重的缺陷,就是需要指定初始化大小,并且在后续的操作中不能修改数组的结构,这很不友好。

​ ArrayList可以很好的进行动态扩容,它会随之元素的不断增加而调整数组大小。它的底层是基于数据实现的,所以也集成了数组的一些特性。比如查找、修改很快,但是新增和删除比较慢。

Array数组

ArrayList底层是由数组实现的,那么就回顾下Java中数组的特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Array1Test {

@Test
public void test1() {
String[] arr = new String[5];
System.out.println("数组的长度" + arr.length);
for (int i = 0 ; i < arr.length ; i++) {
arr[i] = String.valueOf(i);
System.out.print(" ");
}
System.out.println(arr[0].toString());
// 打印出0 , 数组的下表是从0开始的。
arr[6] = null;
// 强行添加一个元素到6的位置,然后取出来抛出ArrayIndexOutOfBoundsException。数组的大小是不能修改的。
}
}

输出:

1
2
3
数组的长度5
0
java.lang.ArrayIndexOutOfBoundsException: 6

List列表

Java的List是一个有序的集合,List是Collection接口的扩展接口。

List特性

  • Java List接口是Java Collection Framework的成员。
  • 列表允许添加重复的元素。
  • 列表允许有null元素。
  • 列表索引是从0开始,和数组一样的。
  • 列表接受泛型,尽量使用它。以免出现ClassCastException

源码分析

ArrayList中的常量以及变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 默认初始化容器的大小
private static final int DEFAULT_CAPACITY = 10;

// 空的对象数组。
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认的对象数组。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 被transient修饰不会被序列化,集合中元素个数。
transient Object[] elementData; // non-private to simplify nested class access

// 容器中元素的个数
private int size;

// 容器的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

创建ArrayList的实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
@Test
public void test3(){
List list1 = new ArrayList();
List list2 = new ArrayList(3);
String[] vowels = {"a","e","i","o","u"};
// 使用Arrays工具将数组转换成列表。
List<String> vowelsList = Arrays.asList(vowels);
List list3 = new ArrayList(vowelsList);

System.out.println(list1.toString());
System.out.println(list2.toString());
System.out.println(list3.toString());
}
1
2
3
[]
[]
[a, e, i, o, u]

这分别使用了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
// list1
public ArrayList() {
// 参数为空的构造方法,元素是空的数组。
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// list2
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);
}
}

// 对应list3
public ArrayList(Collection<? extends E> c) {
// 将一个Collection容器的元素都复制进来。
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
@Test
public void test4(){
List list = new ArrayList(20);
}

题目是:生成list实例需要扩容几次。实际上是0次。因为创建的时候就指定了大小。

add方法

1
2
3
4
5
6
7
@Test
public void test4(){
List list = new ArrayList();
System.out.println(list.add(1));
list.add(0,2);
System.out.println(list.toString());
}

输出

1
2
true
[2, 1] // 是不是很神奇,下标0的位置是2,下标1位置值是1。

带着上面的疑问我们好好看看,顺便看看经常说ArrayList到底是如何扩容的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 直接添加元素
public boolean add(E e) {
// 确保内部容量足够,不够就扩容。 size 是当前容器的数量
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将元素添加到数组中
elementData[size++] = e;
return true;
}

// 在指定索引的位置添加元素。
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++;
}

System.arraycopy 是一个本地静态方法,使用它可以对数组之间进行复制。

1
2
3
public static native void 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
// 1
private void ensureCapacityInternal(int minCapacity) {
// 当前实际存储的数组是空的的时候
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 最小的数字 就是容量大小。
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

// 2
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果当前数组的长度小于 需要的最小容量大小就扩容。
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

// 3
private void grow(int minCapacity) {
// 增加最小扩容,保证元素能添加进容器。
// overflow-conscious code
int oldCapacity = elementData.length;
// 位运算 , 新的容量大小 = 当前数组长度 右移动一位 就是 newCapacity = oldCapacity + (oldCapacity / 2) 取整。也就是经常说的扩容1.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:
// 关键的时候来了,通过Arrays.copyOf复制元素并指定新的数组大小。这个方法最终还是调用了System.arraycopy方法,其它参数是由Array.copyOf预设好的。
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 4 抛出OutOfMemoryError异常咯。内存溢出
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

每次扩容都是通过Arrays.copyOf(elementData, newCapacity)的来实现的。

set方法

这个方法其实就是更新方法。

1
2
3
4
5
6
7
@Test
public void test5(){
List list = new ArrayList();
list.add(1);
System.out.println(list.set(0,1));
System.out.println(list.toString());
}

输出

1
2
1
[1]

看下源代码。

1
2
3
4
5
6
7
public E set(int index, E element) {
rangeCheck(index); //检查所以是否越界,这里要注意,该下标没有值会抛出越界异常。

E oldValue = elementData(index); // 获取下标原始的值
elementData[index] = element; // 将新值复制给对应的下标
return oldValue; // 返回原始的值
}

remove方法

1
2
3
4
5
6
7
8
9
10
11
12
@Test
public void test6(){
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("b");
list.add("c");
list.add("d");
System.out.println(list.toString());
list.remove("b"); //根据元素匹配删除
System.out.println(list.toString());
}

输出

1
2
[a, b, b, c, d]
[a, b, c, d] //会删除匹配到的第一个元素
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
// 根据下标删除元素。删除成功就返回被删除的元素。
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;
}

// 删除元素,如果删除成功返回true
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) {
modCount++;
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
}

这两个删除方法可以看出,动作都比较大。这种操作会慢很多。

get方法。

相比上面3种方法确实轻量级太多了。

1
2
3
4
5
public E get(int index) {
rangeCheck(index);

return elementData(index);
}

平时也就听大家说新增修改删除慢,也就访问速度比较快。看了源码之后才清晰很多。

contains方法

这也是一个重量级的方法

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 boolean contains(Object o) {
return indexOf(o) >= 0;
}

/**
* 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) {
// 当找不到该对象的时候返回-1,找到了就返回它的下标。
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
20
@Test
public void test2(){
// 1、创建一个二维数组
String[] vowels = {"a","e","i","o","u"};
// 2、将二维数组转换成列表,在转换成容器
Collection<String> collection = new ArrayList(Arrays.asList(vowels));
// 3、获取容器迭代器实例
Iterator<String> itr = collection.iterator();
// 4、逻辑判断itr 中下个元素是否存在。
while (itr.hasNext()){
String var = itr.next(); // 获取将要访问的下一个元素。
// 5、尝试修改其中的一个元素。
if(var == "a"){
// 5、删除掉 `a`
itr.remove();
}else{
System.out.print(var);
}
}
}

线程安全

由于所有的方法都没有进行同步。所以很直观的认为有线程安全的问题,还是亲自测试下避免迷迷糊糊的。

场景一:多线程对一个ArrayList进行操作。

假设我们需要添加10000个元素进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
public class ArrayListTest2 {

/**
* 10线程对一个ArrayList进行操作。
*
* @param args
*/
public static void main(String[] args) throws InterruptedException {
List list = new ArrayList();
ExecutorService executorService = Executors.newFixedThreadPool(20);
for (int sum = 0 ; sum < 10 ; sum ++){
executorService.execute(new Runnable() {
@Override
public void run() {
System.out.println("ThreadId:" + Thread.currentThread().getId() + " start!");
for (int i = 0 ; i < 1000 ; i++ ){
list.add(i);
}
System.out.println("ThreadId:" + Thread.currentThread().getId() + " stop!");

}
});
}
executorService.shutdown();
while (!executorService.isTerminated()){
try {
Thread.sleep(1000*5); // 这里睡眠下主线程,不然其它线程还没执行完就被关闭了。
}catch (InterruptedException e){
e.printStackTrace();
}
}
System.out.println("长度" + list.size());
}

}

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ThreadId:12 start!
ThreadId:11 start!
ThreadId:12 stop!
ThreadId:11 stop!
ThreadId:14 start!
ThreadId:14 stop!
ThreadId:15 start!
ThreadId:15 stop!
ThreadId:13 start!
ThreadId:16 start!
ThreadId:16 stop!
ThreadId:17 start!
ThreadId:17 stop!
ThreadId:13 stop!
ThreadId:18 start!
ThreadId:18 stop!
ThreadId:19 start!
ThreadId:19 stop!
ThreadId:20 start!
ThreadId:20 stop!
长度9950

每次的输出结构都不同,偶尔还会抛出越界异常。

1
2
3
4
5
6
// 直接添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e; //应该就是在这里,在多线程的情况下很有可能出现重复添加了元素。
return true;
}

Fail-Fast场景

fail-fast 机制在遍历一个集合时,当集合结构被修改,会抛出 Concurrent Modification Exception。

fail-fast 会在以下两种情况下抛出 Concurrent Modification Exception

(1)单线程环境

  • 集合被创建后,在遍历它的过程中修改了结构。
  • 注意 remove() 方法会让 expectModcount 和 modcount 相等,所以是不会抛出这个异常。

(2)多线程环境

  • 当一个线程在遍历这个集合,而另一个线程对这个集合的结构进行了修改。

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作,或者是调整内部数组的大小,仅仅只是设置元素的值不算结构发生变化。

在进行序列化或者迭代等操作时,需要比较操作前后 modCount 是否改变,如果改变了需要抛出 Concurrent Modification Exception。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();

// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);

// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}

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