从零到Offer -- List的那些事

阳光穿透心脏的1/2处 2023-09-25 18:02 58阅读 0赞

![format_png][]

### ArrayList ###

--------------------

作为日常最常见的collection对象，相信大家对于ArrayList都不陌生。但是ArrayList的实现你是否又了解呢？开门见山，ArrayList的最底层实现其实就是一个数组：

transient Object[] elementData;
     
     public ArrayList() {
         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
     }
    复制代码

然而我们都知道，java下，一个数组的长度是固定的，是无法变化的。但是实际我们应用ArrayList的时候不难发现，无论你怎么往这个集合中添加元素，他都不会显示越界。相反，数组就像有了魔法一样，会随着你的添加而不断变长。要了解这个原因，就不得不提到add方法。

publicbooleanadd(E e){
         ensureCapacityInternal(size + 1);  // Increments modCount!!
         elementData[size++] = e;
         returntrue;
     }
    复制代码

乍一看，add方法本身平平无奇。但是实际上在ensureCapacityInternal方法中，它悄悄为你做了好多事。

privatevoidensureCapacityInternal(int minCapacity) {
         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
     }
     
     //计算长度
     privatestatic int calculateCapacity(Object[] elementData, int minCapacity) {
         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
             //如果数组为空的，那么此时返回默认最小长度间 - 10
             returnMath.max(DEFAULT_CAPACITY, minCapacity);
         }
         return minCapacity;
     }
     
     privatevoidensureExplicitCapacity(int minCapacity) {
         //记录修改的次数
         modCount++;
     
         // overflow-conscious code
         if (minCapacity - elementData.length > 0)
             grow(minCapacity);
     }
    复制代码

#### 越界处理 ####

首先看到modCount++这个代码，相信我们在使用中不免有过这样的操作，在for循环中尝试删除/移除一个元素对象：

for (String s : arrayList) {
         arrayList.remove(s);
     }
    复制代码

然后此时可能就会抛出这样的报错：

![format_png 1][]

其实本质原因是，for循环的代码依赖每个对象的iterator实现的。而iterator又依赖是数组的长度和下标。其是否可以往下循环会通过hasNext进行判断。如果我们随意删除元素，那么此时就可能出现越界。

publicbooleanhasNext(){
         return cursor != size;
     }
    复制代码

为了尽早的避免这种情况发生（FailFast原则），ArrayList在设计上就采用一个modCount的变量来记录数组变更的次数，并通过判断迭代器生成时的modCount同循环进行时的modCount进行比较，从而达到目的。

#### 容量变化 ####

除了modCount以外，我们还关注到ArrayList里有grow(minCapacity);这样一句代码，这个其实就是ArrayList能够不断添加元素的关键：

private void grow(int minCapacity) {
         int oldCapacity = elementData.length;
         // 扩容
         int newCapacity = oldCapacity + (oldCapacity >> 1);
         // 设置最小长度
         if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
         // 计算溢出
         if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
         elementData = Arrays.copyOf(elementData, newCapacity);
     }
    复制代码

grow中主要做了以下三件事：**数组扩容、设置最小长度、判断溢出**

##### 数组扩容 #####

在数组扩容上，新的容量长度是通过旧容量\*1.5倍（左右）得到的，这里为什么要采用1.5倍而不是2倍也不是1.2倍呢？原因个人理解有两个：

1、添加引发的扩充是很频繁的，因此需要更快的运算速度。而我们都知道位运算运算速度是最快的，自然就不优先考虑1.2、1.4这些用运算较难得到的数字。那么只剩下1.5、2（只需要一次移位）、1.25、4（需要两次移位）的选择了。

2、从上述描述中，我们优先会考虑1.5和2，采用2倍空间进行扩容自然也是可以的，但是实际中2倍扩充会浪费比较多的空间，且数组的空间是无法被GC回收的。因此，为了更少的浪费空间，于是采用了1.5倍这个关键值。

##### 设置最小长度 #####

在设置最小长度的点上，这个相对简单，需要注意的是，虽然初始ArrayList创建时是一个空数组，但是实际ArrayList会保存一个

默认长度，其值为10.

privatestaticfinalint DEFAULT_CAPACITY = 10;
    复制代码

##### 判断溢出 #####

ArrayList能扩容不假，但也不能无限创建空间。因此ArraysList为数组的长度划定了一个上限：Integer.MAX\_VALUE-8。这里之所以要减8，是为了适配不同VM虚拟机，因为不同的VM虚拟机会保存一部分header头信息。

如果当前长度超过了Integer的最大值，毫无疑问会变成负数。此时系统就会判定为超出了ArraysList的存储大小了。若是当前最小长度介于Integer.MAX\_VALUE和Integer.MAX\_VALUE-8之间，会默认转换成最大值。

privatestaticfinalint MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
     
     //判断是否溢出
     privatestaticinthugeCapacity(int minCapacity){
         if (minCapacity < 0) // overflow
             thrownewOutOfMemoryError();
         return (minCapacity > MAX_ARRAY_SIZE) ?
             Integer.MAX_VALUE :
             MAX_ARRAY_SIZE;
     }
    复制代码

### LinkedList ###

--------------------

介绍完了ArrayList，我们自然还需要介绍他的亲戚LinkedList。与ArrayList明显不同的是，LinkedList底层的实现是基于链表实现的。其中有first、last两个节点，用于保存链表的首节点和尾节点。对于每个node来说，其都会保存其前一个节点的指针及后一个节点的指针。

transient Node<E> first; // 首节点
     
     transient Node<E> last; // 尾节点
     
     private static class Node<E> {
         E item;
         Node<E> next; // 前一个对象
         Node<E> prev; // 后一个对象
         Node(Node<E> prev, E element, Node<E> next) {
             this.item = element;
             this.next = next;
             this.prev = prev;
         }
     }
    复制代码

同arrayList类似，要介绍LinkedList就也得介绍他的add方法：

public boolean add(E e) {
         linkLast(e);
         return true;
     }
     
     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++;
     }
    复制代码

从上可以看到，linkLast()方法其实组成了add方法的全部。相信如果各位学过数据结构与算法的话，一定会对上述代码不陌生。就是一个简单的带尾部节点的链表尾插算法。（不了解的同学就百度一下吧，限于篇幅这里就不展开了。）

同时可以看到LinkedList也会保存一个size变量用于保存数组的长度，避免链表在获取长度时所需要消耗的耗时。与ArrayList类似的是，linkedList也会保存一个modCount变量用于保存数据变更的次数，作用是类似的，这里就不再赘述了。

### Vector ###

--------------------

上文介绍到的ArrayList和linkedList是我们日常最常使用到的数组结构。但是他们都存在一个缺陷，就是没法应对多并发。LinkedList在多并发下指针可能会紊乱，而ArrayList则可能出现数组越界、数据污染等问题。

为此，Collection包下还有一个数组结构，那就是Vector。那么vector又是如何支持多并发的呢？其实很简单粗暴，vector本身也是采用数组实现的，与ArrayList不同的是，其所有数据变更的方法都采用**同步关键字synchronized**进行修饰。从而达到同步互斥的逻辑。

publicsynchronizedbooleanadd(E e){
         modCount++;
         ensureCapacityHelper(elementCount + 1);
         elementData[elementCount++] = e;
         returntrue;
     }
    复制代码

尽管Vector是支持高并发的，但是由于其实现的方式太过"粗暴"。因此，建议少用，可以选择CopyOnWriteArrayList等其他轻量级的实现。

[format_png]: https://img-blog.csdnimg.cn/img_convert/abd47528392ca5eb7f3d7398ab273a22.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/cd9aa7d5e3bcc782f66fc137598eff75.webp?x-oss-process=image/format,png