Java中常见数据结构List之ArrayList

时间:2022-06-09 06:34:08

这里主要包含ArrayList和LinkedList.

关于Java中的集合内容, 感觉都已经被写烂了, 我这里主要是做个复习, 再从扒下源代码, 尽量用最直白的语言把里面的核心内容记录下来。仅此而已。

首先放一个Collection下的UML图:(此图是idea通过diagram功能生成的, 基于JDK7)

Java中常见数据结构List之ArrayList

一、ArrayList

1, for-each原理:

0、 在编译的时候编译器会自动将对for这个关键字的使用转化为对目标的迭代器的使用,这就是foreach循环的原理

1、ArrayList之所以能使用foreach循环遍历,是因为ArrayList所有的List都是Collection的子接口,而Collection是Iterable的子接口,ArrayList的父类AbstractList正确地实现了Iterable接口的iterator方法。之前我自己写的ArrayList用foreach循环直接报空指针异常是因为我自己写的ArrayList并没有实现Iterable接口

2、任何一个集合,无论是JDK提供的还是自己写的,只要想使用foreach循环遍历,就必须正确地实现Iterable接口。

2, 集合中的 fail-fast iterator:

Iterator 是工作在一个独立的线程中,并且拥有一个 mutex 锁。 Iterator 被创建之后会建立一个指向原来对象的单链索引表,当原来的对象数量发生变化时,这个索引表的内容不会同步改变,所以当索引指针往后移动的时候就找不到要迭代的对象,所以按照 fail-fast 原则 Iterator 会马上抛出 java.util.ConcurrentModificationException 异常。

当使用foreach遍历一个list元素时, 因为foreach底层实现是使用iteator中的hasNext, next等, 源码中next执行时会checkForComdification:

Java中常见数据结构List之ArrayList

3, ArrayList初始值大小是10, 每次扩容是增加2倍。优缺点是:

//默认的构造函数, 当然还有构造函数是可以指定大小的
public ArrayList() {
this(10);
} //jdk7中的扩容代码, 我看了jdk6中是扩容1.5倍的, 这里有点差别
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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:
elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList的优点:

1、ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快

2、ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已

ArrayList的缺点:

1、删除元素的时候,涉及到一次元素复制,如果要复制的元素很多,那么就会比较耗费性能

2、插入元素的时候,涉及到一次元素复制,如果要复制的元素很多,那么就会比较耗费性能

因此,ArrayList比较适合顺序添加、随机访问的场景。

4,细节: 为什么ArrayList的elementData是用transient修饰的?

ArrayList实现了Serializable接口,这意味着ArrayList是可以被序列化的,用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么?因为序列化ArrayList的时候,ArrayList里面的elementData未必是满的,比方说elementData有10的大小,但是我只用了其中的3个,那么是否有必要序列化整个elementData呢?显然没有这个必要,因此ArrayList中重写了writeObject方法:

private transient Object[] elementData;
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 array length
s.writeInt(elementData.length); // 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();
} }

每次序列化的时候调用这个方法,先调用defaultWriteObject()方法序列化ArrayList中的非transient元素,elementData不去序列化它,然后遍历elementData,只序列化那些有的元素,这样:

1、加快了序列化的速度

2、减小了序列化之后的文件大小