| title | date | order | categories | tags | permalink | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Java 容器之 List |
2018-06-27 16:12:18 -0700 |
2 |
|
|
/pages/c7adc138/ |
List是Collection的子接口，其中可以保存各个重复的内容。
List 是一个接口，它继承于 Collection 的接口。它代表着有序的队列。
AbstractList 是一个抽象类，它继承于 AbstractCollection。AbstractList 实现了 List 接口中除 size()、get(int location) 之外的函数。
AbstractSequentialList 是一个抽象类，它继承于 AbstractList。AbstractSequentialList 实现了“链表中，根据 index 索引值操作链表的全部函数”。
ArrayList、LinkedList 是 List 最常用的实现。
ArrayList基于动态数组实现，存在容量限制，当元素数超过最大容量时，会自动扩容；LinkedList基于双向链表实现，不存在容量限制。ArrayList随机访问速度较快，随机插入、删除速度较慢；LinkedList随机插入、删除速度较快，随机访问速度较慢。ArrayList和LinkedList都不是线程安全的。
Vector 和 Stack 的设计目标是作为线程安全的 List 实现，替代 ArrayList。
Vector-Vector和ArrayList类似，也实现了List接口。但是，Vector中的主要方法都是synchronized方法，即通过互斥同步方式保证操作的线程安全。Stack-Stack也是一个同步容器，它的方法也用synchronized进行了同步，它实际上是继承于Vector类。
ArrayList 是一个数组队列，相当于动态数组。ArrayList 默认初始容量大小为 10 ，添加元素时，如果发现容量已满，会自动扩容为原始大小的 1.5 倍。因此，应该尽量在初始化 ArrayList 时，为其指定合适的初始化容量大小，减少扩容操作产生的性能开销。
ArrayList 定义：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable从 ArrayList 的定义，不难看出 ArrayList 的一些基本特性：
ArrayList实现了List接口，并继承了AbstractList，它支持所有List的操作。ArrayList实现了RandomAccess接口，支持随机访问。RandomAccess是一个标志接口，它意味着“只要实现该接口的List类，都支持快速随机访问”。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。ArrayList实现了Cloneable接口，默认为浅拷贝。ArrayList实现了Serializable接口，支持序列化，能通过序列化方式传输。ArrayList是非线程安全的。
ArrayList 包含了两个重要的元素：elementData 和 size。
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 对象数组
transient Object[] elementData;
// 数组长度
private int size;size- 是动态数组的实际大小，默认初始容量大小为 10。elementData- 是一个Object数组，用于保存添加到ArrayList中的元素。正是由于实际存储元素的是Object数组，所以其天然支持随机访问。
ArrayList 类实现了三个构造函数：
- 第一个是默认构造方法，ArrayList 会创建一个空数组；
- 第二个是创建 ArrayList 对象时，传入一个初始化值；
- 第三个是传入一个集合类型进行初始化。
当 ArrayList 新增元素时，如果所存储的元素已经超过其当前容量，它会计算容量后再进行动态扩容。数组的动态扩容会导致整个数组进行一次内存复制。因此，初始化 ArrayList 时，指定数组初始大小，有助于减少数组的扩容次数，从而提高系统性能。
public ArrayList() {
// 创建一个空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 根据初始化值创建数组大小
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 初始化值为 0 时，创建一个空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}ArrayList 具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。为此，ArrayList 定制了其序列化方式。具体做法是：
- 存储元素的
Object数组（即elementData）使用transient修饰，使得它可以被 Java 序列化所忽略。 ArrayList重写了writeObject()和readObject()来控制序列化数组中有元素填充那部分内容。
💡 不了解 Java 序列化方式，可以参考：Java 序列化
ArrayList 访问元素的实现主要基于以下关键性源码：
// 获取第 index 个元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}实现非常简单，其实就是通过数组下标访问数组元素，其时间复杂度为 O(1)，所以很快。
ArrayList 添加元素有两种方法：一种是添加元素到数组末尾，另外一种是添加元素到任意位置。
// 添加元素到数组末尾
public boolean add(E e) {
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++;
}两种添加元素方法的不同点是：
- 添加元素到任意位置，会导致在该位置后的所有元素都需要重新排列；
- 而添加元素到数组末尾，在没有发生扩容的前提下，是不会有元素复制排序过程的。
两种添加元素方法的共同点是：添加元素时，会先检查容量大小，如果发现容量不足，会自动扩容为原始大小的 1.5 倍。
ArrayList 添加元素的实现主要基于以下关键性源码：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
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 执行添加元素动作（add 方法）时，调用 ensureCapacityInternal 方法来保证容量足够。
- 如果容量足够时，将数据作为数组中
size+1位置上的元素写入，并将size自增 1。 - 如果容量不够时，需要使用
grow方法进行扩容数组，新容量的大小为oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。扩容操作实际上是调用Arrays.copyOf()把原数组拷贝为一个新数组，因此最好在创建ArrayList对象时就指定大概的容量大小，减少扩容操作的次数。
ArrayList 的删除方法和添加元素到任意位置方法有些相似。
ArrayList 在每一次有效的删除操作后，都要进行数组的重组，并且删除的元素位置越靠前，数组重组的开销就越大。具体来说，ArrayList 会**调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上。
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;
}ArrayList 使用 modCount 来记录结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。
在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果发生改变，ArrayList 会抛出 ConcurrentModificationException。
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();
}
}LinkedList 基于双链表结构实现。由于是双链表，所以顺序访问会非常高效，而随机访问效率比较低。
LinkedList 定义：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable从 LinkedList 的定义，可以得出 LinkedList 的一些基本特性：
LinkedList实现了List接口，并继承了AbstractSequentialList，它支持所有List的操作。LinkedList实现了Deque接口，也可以被当作队列（Queue）或双端队列（Deque）进行操作，此外，也可以用来实现栈。LinkedList实现了Cloneable接口，默认为浅拷贝。LinkedList实现了Serializable接口，支持序列化。LinkedList是非线程安全的。
LinkedList 内部维护了一个双链表。
LinkedList 通过 Node 类型的头尾指针（first 和 last）来访问数据。
// 链表长度
transient int size = 0;
// 链表头节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;size- 表示双链表中节点的个数，初始为 0。first和last- 分别是双链表的头节点和尾节点。
Node 是 LinkedList 的内部类，它表示链表中的元素实例。Node 中包含三个元素：
prev是该节点的上一个节点；next是该节点的下一个节点；item是该节点所包含的值。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
...
}LinkedList 与 ArrayList 一样也定制了自身的序列化方式。具体做法是：
- 将
size（双链表容量大小）、first和last（双链表的头尾节点）修饰为transient，使得它们可以被 Java 序列化所忽略。 - 重写了
writeObject()和readObject()来控制序列化时，只处理双链表中能被头节点链式引用的节点元素。
LinkedList 访问元素的实现主要基于以下关键性源码：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}获取 LinkedList 第 index 个元素的算法是：
- 判断 index 在链表前半部分，还是后半部分。
- 如果是前半部分，从头节点开始查找；如果是后半部分，从尾结点开始查找。
LinkedList 这种访问元素的性能是 O(N) 级别的（极端情况下，扫描 N/2 个元素）；相比于 ArrayList 的 O(1)，显然要慢不少。
推荐使用迭代器遍历 LinkedList ，不要使用传统的 for 循环。注：foreach 语法会被编译器转换成迭代器遍历，但是它的遍历过程中不允许修改 List 长度，即不能进行增删操作。
LinkedList 有多种添加元素方法：
add(E e)：默认添加元素方法（插入尾部）add(int index, E element)：添加元素到任意位置addFirst(E e)：在头部添加元素addLast(E e)：在尾部添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}LinkedList 添加元素的实现主要基于以下关键性源码：
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}算法如下：
- 将新添加的数据包装为
Node； - 如果往头部添加元素，将头指针
first指向新的Node，之前的first对象的prev指向新的Node。 - 如果是向尾部添加元素，则将尾指针
last指向新的Node，之前的last对象的next指向新的Node。
LinkedList 删除元素的实现主要基于以下关键性源码：
public boolean remove(Object o) {
if (o == null) {
// 遍历找到要删除的元素节点
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 遍历找到要删除的元素节点
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}算法说明：
- 遍历找到要删除的元素节点，然后调用
unlink方法删除节点； unlink删除节点的方法：- 如果当前节点有前驱节点，则让前驱节点指向当前节点的下一个节点；否则，让双链表头指针指向下一个节点。
- 如果当前节点有后继节点，则让后继节点指向当前节点的前一个节点；否则，让双链表尾指针指向上一个节点。
- 是否保证线程安全：
ArrayList和LinkedList都是不同步的，也就是不保证线程安全； - 底层数据结构：
ArrayList底层使用的是Object数组；LinkedList底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！） - 插入和删除是否受元素位置的影响：
ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候，ArrayList会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。LinkedList采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、removeLast()），时间复杂度为 O(1)，如果是要在指定位置i插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
- 是否支持快速随机访问：
LinkedList不支持高效的随机元素访问，而ArrayList（实现了RandomAccess接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。 - 内存空间占用：
ArrayList的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。
在业务开发中，我们常常会把原始的数组转换为 List 类数据结构，来继续展开各种 Stream 操作。通常，我们会使用 Arrays.asList 方法可以把数组一键转换为 List。
【示例】Arrays.asList 转换基本类型数组
int[] arr = { 1, 2, 3 };
List list = Arrays.asList(arr);
log.info("list:{} size:{} class:{}", list, list.size(), list.get(0).getClass());【输出】
11:26:33.214 [main] INFO io.github.dunwu.javacore.container.list.AsList示例 - list:[[I@ae45eb6] size:1 class:class [I
数组元素个数为 3，但转换后的列表个数为 1。
由此可知， Arrays.asList 第一个问题点：不能直接使用 Arrays.asList 来转换基本类型数组。
其原因是：Arrays.asList 方法传入的是一个泛型 T 类型可变参数，最终 int 数组整体作为了一个对象成为了泛型类型 T：
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}直接遍历这样的 List 必然会出现 Bug，修复方式有两种，如果使用 Java8 以上版本可以使用 Arrays.stream 方法来转换，否则可以把 int 数组声明为包装类型 Integer 数组：
【示例】转换整型数组为 List 的正确方式
int[] arr1 = { 1, 2, 3 };
List list1 = Arrays.stream(arr1).boxed().collect(Collectors.toList());
log.info("list:{} size:{} class:{}", list1, list1.size(), list1.get(0).getClass());
Integer[] arr2 = { 1, 2, 3 };
List list2 = Arrays.asList(arr2);
log.info("list:{} size:{} class:{}", list2, list2.size(), list2.get(0).getClass());【示例】Arrays.asList 转换引用类型数组
String[] arr = { "1", "2", "3" };
List list = Arrays.asList(arr);
arr[1] = "4";
try {
list.add("5");
} catch (Exception ex) {
ex.printStackTrace();
}
log.info("arr:{} list:{}", Arrays.toString(arr), list);抛出 java.lang.UnsupportedOperationException。
抛出异常的原因在于 Arrays.asList 第二个问题点：Arrays.asList 返回的 List 不支持增删操作。Arrays.asList 返回的 List 并不是我们期望的 java.util.ArrayList，而是 Arrays 的内部类 ArrayList。
查看源码，我们可以发现 Arrays.asList 返回的 ArrayList 继承了 AbstractList，但是并没有覆写 add 和 remove 方法。
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable
{
private static final long serialVersionUID = -2764017481108945198L;
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
// ...
@Override
public E set(int index, E element) {
E oldValue = a[index];
a[index] = element;
return oldValue;
}
}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
}Arrays.asList 第三个问题点：对原始数组的修改会影响到我们获得的那个 List。ArrayList 其实是直接使用了原始的数组。
解决方法很简单，重新 new 一个 ArrayList 初始化 Arrays.asList 返回的 List 即可：
String[] arr = { "1", "2", "3" };
List list = new ArrayList(Arrays.asList(arr));
arr[1] = "4";
try {
list.add("5");
} catch (Exception ex) {
ex.printStackTrace();
}
log.info("arr:{} list:{}", Arrays.toString(arr), list);List.subList 直接引用了原始的 List，也可以认为是共享“存储”，而且对原始 List 直接进行结构性修改会导致 SubList 出现异常。
private static List<List<Integer>> data = new ArrayList<>();
private static void oom() {
for (int i = 0; i < 1000; i++) {
List<Integer> rawList = IntStream.rangeClosed(1, 100000).boxed().collect(Collectors.toList());
data.add(rawList.subList(0, 1));
}
}出现 OOM 的原因是，循环中的 1000 个具有 10 万个元素的 List 始终得不到回收，因为它始终被 subList 方法返回的 List 强引用。
解决方法是：
private static void oomfix() {
for (int i = 0; i < 1000; i++) {
List<Integer> rawList = IntStream.rangeClosed(1, 100000).boxed().collect(Collectors.toList());
data.add(new ArrayList<>(rawList.subList(0, 1)));
}
}【示例】子 List 强引用原始的 List
private static void wrong() {
List<Integer> list = IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toList());
List<Integer> subList = list.subList(1, 4);
System.out.println(subList);
subList.remove(1);
System.out.println(list);
list.add(0);
try {
subList.forEach(System.out::println);
} catch (Exception ex) {
ex.printStackTrace();
}
}抛出 java.util.ConcurrentModificationException。
解决方法：
一种是，不直接使用 subList 方法返回的 SubList，而是重新使用 new ArrayList，在构造方法传入 SubList，来构建一个独立的 ArrayList；
另一种是，对于 Java 8 使用 Stream 的 skip 和 limit API 来跳过流中的元素，以及限制流中元素的个数，同样可以达到 SubList 切片的目的。
//方式一：
List<Integer> subList = new ArrayList<>(list.subList(1, 4));
//方式二：
List<Integer> subList = list.stream().skip(1).limit(3).collect(Collectors.toList());