Java集合框架详解(一) ArrayList

相关文章

从今天开始开始进行jdk的集合框架的学习,会对java集合框架中ArrayList,LinkedList,HashMap, LinkedHashMa..等多个集合类进行学习总结,今天对ArrayList和LinkedList总结(jdk 1.8)。

ArrayList

ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了ICollection和IList接口,灵活的设置数组的大小等好处

类属性

1
2
3
4
5
6
7
8
9
10
11
private static final long serialVersionUID = 8683452581122892189L; //序列化ID

private static final int DEFAULT_CAPACITY = 10;//数组初始容量

private static final Object[] EMPTY_ELEMENTDATA = {}://被用于空实例的共享空数组实例

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//被用于默认大小的空实例的共享数组实例。其与EMPTY_ELEMENTDATA的区别是:当我们向数组中添加第一个元素时,知道数组该扩充多少。

transient Object[] elementData; //存储ArrayList的元素

private int size; //元素的数量

关于transient

在类属性中我们看到了transient关键字,下面说说transient,往上看代码,可以看到类声明的时候有

1
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

我们知道Serializable接口能使对象进行序列化,只要类实现了Serializable接口 它则可以序列化,只要这个类实现了Serilizable接口,这个类的所有属性和方法都会自动序列化。
但是在实际中,敏感信息(比如密码,重要数据等)我们不想它进行序列化,则可以用transient关键字进行取消序列化。
总之,java 的transient关键字为我们提供了便利,你只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。

但是!在ArrayList的 elementData 中被 transient 关键字修饰了,但是又实现了 Serializable 接口,这里并不矛盾,ArrayList通过writeObject和readObject方法以自定义的方式将其序列化并反序列化(ArrayList本身实现了writeObject和readObject方法)。在序列化的过程中,如果被序列化的类定义了writeObject和readObject方法,虚拟机会试图调用这两个方法进行用户自定义的序列化和反序列化,如果没有这两个方法,则默认调用是ObjectOutputStream的defaultWriteObject方法以及ObjectInputStream的defaultReadObject方法。

之所以这样的一个原因是ArrayList的值数组elementData的大小并不一定等于数组的size的大小。size是ArrayList中add进的个数。由于ArrayList有动态扩容的机制,所以elementData的大小总是大于size.所以通过对elementData中有效的元素进行逐个的序列化可以明显的提高效率。

构造方法

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
/**
* Constructs an empty list with the specified initial capacity.
* 构造指定容量的空列表
* @param initialCapacity the initial capacity of the list ArrayList的初始容量
* @throws IllegalArgumentException if the specified initial capacity 如果给定的初始容量为负值
* is negative
*/
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);
}
}

// 构造一个默认初始容量为10的空列表
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* 构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回的顺序排列的
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
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;
}
}

注意,ArrayList在创建默认初始容量为10的空列表中

1
2
3
4
// 构造一个默认初始容量为10的空列表
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

在查找资料的过程中,我了解到在JDK1.6 它的构造函数是

1
2
3
4
// 构造一个默认初始容量为10的空列表
public ArrayList() {
this(10); //public ArrayList(int initialCapacity)中this.elementData = new Object[initialCapacity];
}

构造方法相对还是比较简单的,下面来看看ArrayList的常用方法

常用方法

add()

1
2
3
4
5
6
7
8
9
10
11
/**
* Appends the specified element to the end of this list.
*
* @param e 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;
return true;
}

add方法只有简单三行代码,操作就是在list的结尾添加element,究竟内部如何操作,顺藤摸瓜,看看ensureCapacityInternal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void ensureCapacityInternal(int minCapacity) {
//调用无参构造方法时调用
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

//如果minCapacity小于数组长度,调用grow方法
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

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

下面看看grow方法,看看究竟是如何扩容的,ArrayList的1.5倍扩容为核心

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //当前数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量为就容量的1.5倍
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);
}

为什么选择1.5倍,网上搜索是这样说的

这种算法构造出来的新的数组长度的增量都会比上一次大( 而且是越来越大) ,即认为客户需要增加的数据很多,而避免频繁newInstance 的情况。

总结一下add方法主要是先判断是否需要扩容,将需要容量与当前容量进行比较,如果不够则进行扩容,其次进行溢出判断,之后将旧数组复制到新容量的数组中,最后将添加的数组元素添加至数组最后。

值得注意的地方是在 hugeCapacity 方法溢出判断中,

1
2
3
4
5
6
7
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

该方法最开始会判断 (minCapacity > MAX_ARRAY_SIZE),顺藤摸瓜,可以找到 MAX_ARRAY_SIZE 的定义

1
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

为什么 MAX_ARRAY_SIZE 要定义成 Integer.MAX_VALUE - 8 呢?

首先我们要知道数组无法创建过大,如果数组长度过大,会出现 OutOfMemoryError: Java heap spaceOutOfMemoryError: Requested array size exceeds VM limit ,第一个是Java堆空间不足而第二个是超过了JVM虚拟机的最大限制,回到问题:为什么要定义成 Integer.MAX_VALUE - 8呢?数组作为一个对象,需要一定的内存存储对象头信息(例如标志、锁指针、数组长度),而数组需要占用8字节来存储这些信息,所以要定义成 Integer.MAX_VALUE - 8,如果数组长度来到了Integer.MAX_VALUE - 7,则没有内存来存储这些信息。

java - Why the maximum array size of ArrayList is Integer.MAX_VALUE

下面看重载方法

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
rangeCheckForAdd(index);//判断参数index是否IndexOutOfBoundsException

ensureCapacityInternal(size + 1); // Increments modCount!! 判断扩容
System.arraycopy(elementData, index, elementData, index + 1,
size - index); //将源数组中从index位置开始后的size-index个元素统一后移一位
elementData[index] = element;
size++;
}

addAll()

1
2
3
4
5
6
7
8
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); //将集合c数组化
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount 判断扩容
System.arraycopy(a, 0, elementData, size, numNew); //将添加的数组化后的集合c中的元素批量导入 将a数组从0开始从elementData的size位置开始导入numNew个元素
size += numNew;//更新长度
return numNew != 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//指定的位置开始,将指定collection中的所有元素插入到此列表中,新元素的顺序为指定collection的迭代器所返回的元素顺序
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);//判断溢出

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);//将源数组中从index位置开始的后numMoved个元素统一后移numNew位

System.arraycopy(a, 0, elementData, index, numNew);////再将数组a[0,...,numNew-1]复制到数组elementData[index,...,index+numNew-1]
size += numNew;
return numNew != 0;
}

get()

1
2
3
4
5
6
7
8
9
10
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}

private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

这个方法很简单,先判断越界,如果不越界则返回数组索引对应的元素

remove()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);//将后面的数组元素向前移动1位
elementData[--size] = null; // clear to let GC do its work 将最后一位进行垃圾回收并且更新容量

return oldValue;
}

接下来看看重载方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

主要是遍历数组,如果存在要删除的对象0则调用fastRemove方法,看看fastRemove方法

1
2
3
4
5
6
7
8
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
}

和前一个方法差不多,将索引后面的数组元素向前移动1位,将最后一位进行垃圾回收并且更新容量

clear()

1
2
3
4
5
6
7
8
9
public void clear() {
modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;

size = 0;
}

clear方法很简单,就是所有元素都回收。

removeRange()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//删除数组中从fromIndex到toIndex区间的所有元素,注意区间是左闭右开区间
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);

// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}

set()

1
2
3
4
5
6
7
8
//将指定索引上的值替换为新值,并返回旧值
public E set(int index, E element) {
rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;//新值替换
return oldValue;//返回旧值
}

indexOf() 和 lastIndexOf()

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 int indexOf(Object o) {
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;
}

public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

indexOf方法是从头开始遍历,找到数组中第一次出现目标对象的索引
lastIndexOf方法是从尾开始遍历,找到数组中最后一次出现目标对象的索引

ArrayList总结

  • ArrayList底层使用的是数组,通过数组的特点能通过索引直接访问元素,访问效率高,但是在添加删除不如链表,会对大量元素进行移动,效率低
  • ArrayList的扩容是1.5倍扩容,先判断需要的容量和当前容量进行比较,如果大于,则进行1.5倍扩容,如果依然不够,则直接将数组容量设置为最小需求容量
  • ArrayList不是同步的(不是线程安全的),详细会在后面解释
  • 关于modCount,在每次数组操作的时候都会有modCount++;,依然是关于多线程问题 可以详细看知乎问题参考