Fork me on GitHub

2019-7-18 jdk源码分析(2)-ArrayList

jdk源码分析(2)-ArrayList

1.ArrayList简介

ArrayList是基于Object[] 数组的,也就是我们常说的动态数组。它能很方便的实现数组的增加删除等操作。

1
2
3
4
5
6
7
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable</span>

1. ArrayList支持泛型,它继承自AbstractList,实现了ListRandomAccessCloneablejava.io.Serializable接口。
2. List接口定义了列表必须实现的方法。
3. RandomAccess是一个标记接口,接口内没有定义任何内容。
4. 实现了Cloneable接口的类,可以调用Object.clone方法返回该对象的浅拷贝。
5. 通过实现 java.io.Serializable 接口以实现序列化功能

2.ArrayList成员变量

1
2
3
4
5
private static final int DEFAULT_CAPACITY = 10;                        // 默认容量
private static final Object[] EMPTY_ELEMENTDATA = {}; // 空实例的空数组对象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 也是空数组对象,用于计算添加第一个元素时要膨胀多少
transient Object[] elementData; // 存储内容的数组
private int size; // 存储的数量

Java关键字 transient:是为了在序列化时保护对象的某些域不被序列化

其中elementData被声明为了transient,那么ArrayList是如何实现序列化的呢?
查看writeObjectreadObject的源码如下:

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

private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;

// Read in size, and any hidden stuff
s.defaultReadObject();

// Read in capacity
s.readInt(); // ignored

if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;

// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}

可以看到在序列化的时候是把elementData里面的元素逐个取出来放到ObjectOutputStream里面的;而在反序列化的时候也是把元素逐个拿出来放回到elementData里面的;

这样繁琐的操作,其中最重要的一个好处就是节省空间,因为elementData的大小是大于ArrayList中实际元素个数的。所以没必要将elementData整个序列化。

3.ArrayList构造函数

ArrayList的构造函数主要就是要初始化elementDatasize,但是其中有一个注意点

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

可以看到在Collection.toArray()之后又判断了他的Class类型是不是Object[].class,这个也注释了是一个bug!

4.常用方法

由于ArrayList是基于数组的,所以他的api基本都是基于System.arraycopy()实现的;

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

可以看到这是一个native方法,并且JVM有对这个方法做特殊的优化处理

1、void trimToSize()

1
2
3
4
5
6
7
8
9
public void trimToSize() {//节约内存
modCount++;//此变量记录ArrayList被改变的次数 !!!超级注意!!!
int oldCapacity = elementData.length;
if (size < oldCapacity) {//!!size往往不等于elementData.length;elementData.length是数组的初始长度,size是实际内容的长度!!
elementData = Arrays.copyOf(elementData, size);
}
}

modCount变量是记录ArrayList被改变的次数

ArrayList不是线程安全(异步)的

ArrayList不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对ArrayList 结构的修改(长度的变化,增加,删除;赋值不是结构变化)都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了ArrayList。
ArrayList中的mouCount是在他的父类Abstract中申明的。

protected transient int modCount = 0;

2、void ensureCapacity(int minCapacity)

1
2
3
4
5
6
7
8
9
10
11
12
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;//若传入参数大于原容量,先扩为 1.5*原容量+1
if (newCapacity < minCapacity)
newCapacity = minCapacity;//若扩为 1.5*原容量+1 后还是小于传入的参数,则把传入的参数作为新容量
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}

ArrayList需要扩容时至少都是扩为 1.5*原容量+1 ,若1.5*原容量+1 还是小于传入的参数,才把传入的参数作为新容量

3、boolean contains(Object o)

1
2
3
public boolean contains(Object o) {
return indexOf(o) >= 0;
}

4、int indexOf(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
public int indexOf(Object o) {
if (o == null) {//定位是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;
}

5、Object[] toArray() / T[] toArray(T[] a)

调用的是Arrays.copyOf()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Object[] toArray() {

return Arrays.copyOf(elementData, size);
}

public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());//若传入的数组长度小于size(ArrayList实际长度),则返回一个长度为size新的数组
System.arraycopy(elementData, 0, a, 0, size);//若传入数组长度相等,则把elementData复制进传入数组
if (a.length > size)//若传入的a的长度大于原本数组,则后面补null
a[size] = null;
return a;
}

6、E set(int index, E element)

set是直接替换掉该位置元素;而add是插入该位置,其余元素后移。

1
2
3
4
5
6
7
public E set(int index, E element) {
RangeCheck(index);//参数检查的方法~~一定要时刻注意参数检查哦~~
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;

}

7、boolean add(E e) / void add(int index, E element)

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean add(E e) {
ensureCapacity(size + 1); // add()时先扩容!
elementData[size++] = e;//!!写的很好,size++的同时还完成了在最后位置的赋值。之所以size++不会报边界溢出的错误是因为上面已经扩容了。
return true;
}

public void add(int index, E element) {
if (index > size || index < 0)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);//!!把elementData的数据从index->末尾全部复制到从index+1开始,复制长度无size-index
elementData[index] = element;//相当于把传入的element插入到空出的位置,即原index
size++;
}

8、E remove(int index) / boolean remove(Object o) / void fastRemove(int index)

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
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];//得到需要返回的被remove掉的元素
int numMoved = size - index - 1;//复制时复制的长度,
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);//把原数组从index+1-->末尾的数据复制到 index的位置,即相当于把原本index上的数据覆盖掉了,这样最后就空出了一个位置。
elementData[--size] = null; // 先把size减一,在把最后一赋值为null
return oldValue;
}


public boolean remove(Object o) {
if (o == null) {//!!判断是否为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; // Let gc do its work
}

5.迭代方式

  • 1. 随机访问

    由于ArrayList实现了RandomAccess接口,它支持通过索引值去随机访问元素。

    1
    2
    3
    for (int i=0, len = list.size(); i < len; i++) {
    String s = list.get(i);
    }
  • 2. 迭代器遍历

    这其实就是迭代器模式

    1
    2
    3
    4
    Iterator iter = list.iterator();
    while (iter.hasNext()) {
    String s = (String)iter.next();
    }
  • 3. 增强for循环遍历

    这其实是一个语法糖

    1
    2
    3
    for (String s : list) {
    ...
    }
  • 4.增强for循环遍历的实现

    1
    2
    3
    4
    5
    6
    7
    8
    public void test_List() {
    List<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    for (String s : list) {
    System.out.println(s);
    }
    }

6.fail-fast机制

fail-fast是说当并发的对容器内容进行操作时,快速的抛出ConcurrentModificationException;但是这种快速失败操作无法得到保证,它不能保证一定会出现该错误,但是快速失败操作会尽最大努力抛出ConcurrentModificationException异常。所以我们程序的正确性不能完全依赖这个异常,只应用于bug检测。

1
2
3
4
5
protected transient int modCount = 0;
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}

ArrayListIteratorSubList中,每当进行内存操作时,都会先使用checkForComodification来检测内容是否已修改。

7.总结

a.ArrayList动态数组!

b.ArrayList 非线程安全,即 是异步的。 单线程才用ArrayList。

c.ArrayList整体来看就是一个更加安全和方便的数组,但是他的插入和删除操作也实在是蛋疼,对于这一点其实可以通过树或者跳表来解决

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!