剖析Java 集合框架(二)-List

序

    周末早上又被深圳特色修路的嘟嘟嘟声轰醒，打开手机，习惯性的点开了Boss直聘，想到工作，想到简历，瞬间清醒，深深感受到这世界的恶意。不过就像我自己要求的，不能怨天尤人，不能自怨自艾，调整心态继续热爱生活。
    感谢小平给我做的爱心早餐，煮的牛奶木瓜(好像发现了盲点~)，煎鸡蛋。小平开始就在是要煎鸡蛋还是煎糍粑还是手抓饼纠结，发现比我这天秤座还能纠结，但是我正抑郁于个人简历中，掩饰自己烦躁的心情和语气，选了个鸡蛋。话说鸡蛋煎的针不戳，外脆内舒，口感十足。奈何cc没文化，一句nb走天下。我想说的是工作跟生活还是要分开，放宽心态，对身边的人要好。与君共勉！

1. ArrayList

1.1 概述

List 接口的可伸缩数组实现。支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。在添加大量元素之前，使用 ensureCapacity 操作，可以减少增量重新分配的数量。
size、isEmpty、get、set。iterator 和 listIterator 操作以常量运行。add 操作以分摊常量时间运行，即添加n个元素需要O(n)。其他所有的操作近似于线性时间运行。

List 接口的可伸缩数组实现。支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。在添加大量元素之前，使用 ensureCapacity 操作，可以减少增量重新分配的数量。
size、isEmpty、get、set。iterator 和 listIterator 操作以常量运行。add 操作以分摊常量时间运行，即添加n个元素需要O(n)。其他所有的操作近似于线性时间运行。

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

1.2 构造函数

ArrayList 有三种方式来初始化，构造方法如下：
删除了中间的其他逻辑代码

 // 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;

 // 默认无参构造函数，构造一个初始容量为十的空列表。 
 // 当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
     // 构造具有指定初始容量的空列表。
public ArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity]; 
    //...
}

// 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。 
 public ArrayList(Collection<? extends E> c) {//...}

1.3 扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。
扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

public boolean add(E e) {
    //先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //添加元素就是为数组赋值
    elementData[size++] = e;
    return true;
}
//保证容量足够
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      // 最小也得为10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
 // 最大数组大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 扩容为原始容量 * 1.5;
    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); 
}

1.4 删除元素

需要调用 System.arraycopy() 将随后的元素向左移动( index+1 的元素都复制到 index 位置上)，该操作的时间复杂度为 O(N)，可以看到 ArrayList 删除元素的代价是非常高的。

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

1.5 System.arraycopy()和Arrays.copyOf()方法

先看看 System.arraycopy()的声明，该方法用了native关键字，说明调用的是其他语言写的底层函数。

// src - 源数组。srcPos - 源数组中的起始位置。 
// dest - 目标数组。destPos - 目标数据中的起始位置。
// length - 要复制的数组元素的数量。
public static native void arraycopy(Object src,int srcPos, Object dest, int destPos,int length);

再看Arrays.copyOf(), 仔细观察发现，copyOf()内部调用了System.arraycopy()方法

//该方法对应不同的数据类型都有各自的重载方法
//original:要复制的数组;newLength:要返回的副本的长度;newType:要返回的副本的类型
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

总结：

  1. copyOf()内部调用了System.arraycopy()方法;
  2. arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
  3. copyOf()是系统自动在内部新建一个数组，调用arraycopy()将原数组拷贝到一个长度为newLength的新数组中，并返回该数组。

1.6 ensureCapacity方法

ArrayList 源码头部的注释里面有提到，在添加大量元素之前，使用 ensureCapacity 操作，可以减少增量重新分配的数量。这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，我们来看看这个方法有什么作用？

//如果需要，增加此 ArrayList实例的容量，以确保它至少可以容纳最小容量参数指定的元素数。
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        ? 0
        : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

最好在 add 大量元素之前用 ensureCapacity 方法，直接一次扩容到位，防止频繁触发扩容，影响性能。

1.7 序列化

所谓的 JAVA 序列化与反序列化，序列化就是将 JAVA 对象以一种的形式保持，比如存放到硬盘，或是用于传输。反序列化是序列化的一个逆过程。
JAVA 规定被序列化的对象必须实现java.io.Serializable 这个接口，而我们分析的目标 ArrayList 同样实现了该接口。
如果一个类不仅实现了 Serializable 接口，而且定义了 readObject（ObjectInputStream in）和 writeObject(ObjectOutputStream out)方法，那么将按照如下的方式进行序列化和反序列化：

ObjectOutputStream 会调用这个类的writeObject方法进行序列化。
ObjectInputStream 会调用相应的readObject方法进行反序列化。

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

transient Object[] elementData; // non-private to simplify nested class access

ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

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
        ensureCapacityInternal(size);
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}
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();
    }
}

序列化时使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

1.8 Fail-Fast

fail-fast 机制是 Java 集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationExceptio。

LinkedList

LinkedList 是以双向链表实现的，插入、删除时只需要改变前后两个节点指针指向即可，无需移动其他元素。
LinkedList 继承自 AbstractSequentialList 接口，同时了还实现了 Deque, Queue 接口。LinkedList 底层的链表结构使它支持高效的插入和删除操作, 也具有队列的特性。

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;     // size：集合的长度
    transient Node<E> first;   // first：双向链表头部节点
    transient Node<E> last;    // last：双向链表尾部节点

针对 first 变量和 last 变量，我们看到是 Node 类的实体，这是一个静态内部类，类中通过 item 变量保存了当前节点的值，通过 next 变量指向下一个节点，通过 prev变量指向上一个节点。

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;
    }
}
LinkedList结构图

添加元素

add(E e) 和 add(int index, E element) 没有本质区别，都是通过新建一个 Node 实体，同时指定其 prev 和 next 来实现，不同点在于需要调用 node(int index)通过传入的index来定位到要插入的位置，这个也是比较耗时的。

public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * 设置元素e为最后一个元素
*/
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++;
}


// 在指定位置添加元素
public void add(int index, E element) {
    checkPositionIndex(index); //检查索引是否处于[0-size]之间

    if (index == size)//添加在链表尾部
        linkLast(element);
    else//添加在链表中间
        linkBefore(element, node(index));
}

LinkedList 插入效率高是相对的，因为它省去了 ArrayList 插入数据可能的数组扩容和数据元素移动时所造成的开销，但数据扩容和数据元素移动却并不是时时刻刻都在发生的。

LinkedList插入元素

删除操作原理同插入相反，基本逻辑可参照上图从插入后到插入前的变化。

get

我们知道随机读取元素不是 LinkedList 所擅长的，读取效率比起 ArrayList 也低得多，那么我们一起来看一下为什么。

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

从上述代码中我们可以看到 get(int index)方法的实现机制是:往后或往前遍历查找。也就是说越靠近中间的元素，遍历的次数越多，效率也就越低。因此在使用 LinkedList 的时候，我们不建议使用这种方式读取数据，可以使用 getFirst()，getLast()方法，将直接用到类中的first和last变量。

Arraylist 与 LinkedList 区别?

  1. 是否保证线程安全：都是不同步的，也就是不保证线程安全；
  2. 底层数据结构：Arraylist 底层使用的是动态数组；LinkedList 底层使用的是 双向链表
  3. 时间复杂度：ArrayList 访问时O(1)，但是删除(移动后面的元素)/添加(扩容时复制元素)O(n)。LinkedList 访问平均为o(n)，删除/添加需要先访问到对应位置近视O(n)。
  4. 内存空间占用：ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

Vector

同步

Vector 的实现与 ArrayList 类似，但是基本每个方法都用 synchronized 进行同步。保证了相对安全。

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E remove(int index) {
      modCount++;
      if (index >= elementCount)
          throw new ArrayIndexOutOfBoundsException(index);
      E oldValue = elementData(index);
      int numMoved = elementCount - index - 1;
      if (numMoved > 0)
          System.arraycopy(elementData, index+1, elementData, index,
                           numMoved);
      elementData[--elementCount] = null; // Let gc do its work
      return oldValue;
}

public synchronized E get(int index) {//...}

扩容

Vector 的构造函数可以传入 capacityIncrement 参数，它的作用是在扩容时使容量 capacity 增长 capacityIncrement。如果这个参数的值小于等于 0，扩容时每次都令 capacity 为原来的两倍。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 调用没有 capacityIncrement 的构造函数时，capacityIncrement 值默认为 0，
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
  //...
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
public Vector() {
    this(10);
}

Vector 与 ArrayList 的比较

  • Vector 是同步的，因此性能会受到影响，访问速度更慢。
  • Vector 每次扩容请求其大小的 2 倍（也可以通过构造函数设置增长的容量），而 ArrayList 是 1.5 倍。

CopyOnWriteArrayList

概述

写入时复制（CopyOnWrite，简称COW）思想是计算机程序设计领域中的一种优化策略。其核心思想是，如果有多个调用者（Callers）同时要求相同的资源（如内存或者是磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者视图修改资源内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此做法主要的优点是如果调用者没有修改资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。
CopyOnWriteArrayList 的读写分离：

  • 写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。
  • 写操作需要加锁，防止并发写入时导致写入数据丢失。
  • 写操作结束之后需要把原始数组指向新的复制数组。
    内部持有一个 ReentrantLock;底层是用 volatile transient 声明的数组 array 
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
final void setArray(Object[] a) {
    array = a;
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。比如白名单，黑名单，商品类目的访问和更新场景等等。
CopyOnWrite 的缺点

  1. 内存占用：写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右。
  2. 数据不一致：只能保证数据的最终一致性，不能保证数据的实时一致性。因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

后记

感谢各位观众姥爷看到最后。很不容易，磕磕碰碰，铿锵铿锵挤出来了，可能对于很多大佬都是基本知识，不过还是希望能帮助到人，和加深自己的理解。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
禁止转载，如需转载请通过简信或评论联系作者。
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,658评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,482评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,213评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,395评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,487评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,523评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,525评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,300评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,753评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,048评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,223评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,905评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,541评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,168评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,417评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,094评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,088评论 2赞 352

推荐阅读更多精彩内容