系统优化专题4——集合

集合作为一种存储数据的容器，是日常开发中使用最频繁的对象类型之一。JDK为开发者提供了一系列的集合类型，这些集合类型使用不同的数据结构来实现。因此，不同的集合类型，使用场景也不同。

List接口

先通过这张图，看一下List集合类的接口和类的实现关系：


image.png

我们可以看到ArrayList、Vector,LinkedList集合类继承了AbstractList抽象类，而AbstractList实现了List接口，同时也继承了AbstractCollection抽象类。ArrayList、VectorsLinkedList又根据自我定位，分别实现了各自的功能。

ArrayList和Vector使用了数组实现，两者的实现原理差不多，LinkedList使用了双向链表实现。

ArrayList是如何实现的？

如下几个问题：

  1. 我们在查看ArrayList的实现类源码时，会发现对象数组elementData使用了transient修饰，我们知道transient关键字修饰该属性，则表示该属性不会被序列化，然而我们并没看到文档中说明ArrayList不詣被序列化，这是为什么？
  2. 使用ArrayList做新删除作会影响效率，那是不是ArrayList在大量新增元素的场景下效率就一定会降低呢？
  3. 使用for循环以及迭代循环遍历一个ArrayList，你会使用哪种方式呢？原因是什么？

ArrayList实现类

ArrayList实现了List口，继承了AbstractList抽象类，底层是数组实现的，并且实现了自增扩容数组大小。

ArrayList还实现了Cloneable接口和Serializable接口，所以他可以实现克隆和序列化。

ArrayList还实现了RandomAccess接口。通过代码我们可以发现，这个接口其实是一个空接口，什么也没实现，那ArrayList为什么要去实现它？

其实RandomAccess接口是一个标志口，他标志着"只要实现该口的List类，都能实现快速随机访问"。

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

ArrayList属性

ArrayList属性主要由数组长size、对象数组elementData、初始化容量default_capacity等组成，其中初始化容量默认大小为10。

//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//对象数组
transient Object[] elementData;
//数组长度
private int size;

从ArrayList属性来看，它没被任何的多线程关键字修饰，但elementData被关键字transient修饰了。这就是上面提到的第一道测试题。其实，这还得从"ArrayList是基于数组实现开始说起，由于ArrayList的数组是基于动态扩增的，所以并不是所有被分配的内存空间都存储了数据。

如果采总外部序列化法实现数组的序列化，会序列化整个数组。ArrayList为了避免这些没有存放数据的内存空间被序列化，内部提供了两个私有方法writeObject以及readObject来自我完成序列化与反序列化，从而在序列化与反序列化数组时节省了空间和时间。

因此使用transient修饰数组，是防止对象数组被其他外部方法序列化。

ArrayList构造函数

ArrayList类实现了三个构造丞数，第一个是创建ArrayList对象时，传入一个初始化值；第二个是默认创建一个空数组对象；第三个是传入一个集合类型进行初始化。

当ArrayList新增元素时，如果所存储的元素已经超过其已有大小，它会计算元素大小后再进行动态扩容，数组的扩容会导致整个数组进行一次内存复制。因此，我们在初始化ArrayList时，可以通过第一个构造函数合理指定数组初始大小，这样有助于减少数组的扩容次数，从而提高系统性能。

public ArrayList(int initialCapacity){
    if(initialCapacity > 0){
//初始化容量不为0时，将根据初始化值创建数组大小
        this.elementData = new Object[initialCapacity];
    }else if(initialCapacity == 0){
//初始化容量为0时，使用默认的空数组
        this.elementData = EMPTY_ELEMENTDATA;
    }else{
        throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);
    }
}

public ArrayList(){
    //初始化默认为空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList新增元素

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);
    System.arraycopy(elementData,index,elementData,index+1,size - index);
    elementData[index] = element;
    size++;
}

两个方法的相同之处是在添加元素前，会先确认容量大小，如果容量够大，就不进行扩容；如果容量不够大，就会按照原来数组的1.5倍大小进行扩容，在扩容后需要将数组复制到新分配的内存地址。

private void ensureExplicitCapacity(int minCapacity){
    modCount++;
    //overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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初始化时指定数组容量大小，并且在添加元素时，只在数组末尾添加元素，那么在大量新增元素的场景下，性能并不会变差，反而比其他List集合性能要好。

ArrayList删除元素

ArrayList的删除方法和添加任意位置元素的方法是有些相同的。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; //chear to let GC do its work
    return oldValue;
}

ArrayList遍历元素

由于ArrayList是基于数组实现的，所以在获取元素的时候是非常快捷的。

public E get(int index){
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index){
    return (E) elementData[index];
}

LinkedList

虽然LinkedList与ArrayList都是List类型的集合，但LinkedList的实现原理却和ArrayList大相径庭，使用场景也不太一样。

LinkedList是基于双向链表数据结构实现的，LinkedList定义了一个Node结构，Node结构中包含了3个部分：元素内容item、前指针prev以及后指针next，代码如下：

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就是由Node结构对象连接而成的一个双向链表。在JDK1.7之前，LinkedList中只包含了一个Entry结构的header属性，并在初始化的时候默认创建了一个空的Entry，用来做header，前后指针指向自己，形成一个循环双向链表。

在JDK1.7之后，LinkedList做了很大的改动，对链表进行了优化。链表的Entry结构换成了Node，内部组成基本没有改变，但LinkedList里面的header属性去掉了，新增了一个Node结构的first属性和一个Node结构的last属性。这样做有以下几点好处：

  1. first/last属性能更清晰地表达链表的表头和表尾概念；
  2. first/last方式可以在初始化LinkedList的时候节省new一个Entry；
  3. first/last方式最重要的性能优化是表头和表尾的插入操作更快捷了。

LinkedList实现类

LinkedList类实现了List接口、Deque接口，同时继承了AbstractSequentialList抽象类，LinkedList既实现了List类型又有Queue类型的特点；

LinkedList也实现了Cloneable和Serializable接口，同ArrayList一样，可以实现克隆和序列化。

由于LinkedList存储数据的内存地址是不连续的，而是通过指针来定位不连续地址，因此，LinkedList不支持随机快速访问，LinkedList也就不能实现RandomAccess接口。

public class LinkedList<E> extends AbstractSequentialList<E> implement List<E>,Deque<E>,Cloneable，java.io.Serializable

LinkedList属性

我们可以看到，LinkedList的first/last/size属性都被transient修饰了，因为我们在序列化的时候不会只对头尾进行序列化，所以LinkedList也是自行实现readObject和writeObject进行序列化与反序列化。

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

LinkedList新增元素

LinkedList添加元素的实现很简洁，添加的方式有很多种。默认的add(E e)方法是将添加的元素加到队尾，首先是将last元素置换到临时变量中，生成一个新的Node节点对象，然后将last引用指向新节点对象，之前的last对象的前指针指向新节点对象

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

LinkedList也有添加元素到任意位置的方法，如果我们是将元素添加到任意两个元素的中间位置，添加元素操作只会改变前后元素的前后指针，指针将会指向添加的新元素，所以相比ArrayList的添加操作来说，LinkedList的性能优势明显。

public void add(int index,E element){
    checkPositionIndex(index);
    if(index == size)
        linkLast(element);
    else
        linkBefore(element,node(index));
}

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;
    last = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

LinkedList删除元素

在LinkedList删除元素的操作中，首先需要通过循环，根据要删除元素所处的位置，从前到后或从后到前找到要删除的元素。无论要删除的元素靠前或靠后都是非常高效的，但如果List拥有大量元素，要移除的元素处于中间位置的话，效率相对来说会很低。

LinkedList遍历元素

LinkedList的获取元素操作实现跟LinkedList的删除元素操作基本类似，通过分前后半段来循环查找到对应的元素。但是通过这种方式来查询元素是非常低效的，特别是在for循环遍历下，每一个循环都会去遍历半个List。

所以，在使用LinkedList循环遍历时，我们可以使用iterator方式迭代循环，直接拿到我们的元素，不需要通过循环查找List。

总结

现在我们看几组测试结果

添加

测试条件 测试结果(耗时)
从集合头部位置新增元素 ArrayList>LinkedList
从集合中间位置新增元素 ArrayList<LinkedList
从集合尾部位置新增元素 ArrayList<LinkedList

由于ArrayList是数组实现的，而数组是一块连续的内存空间，在添加元素到数组头部的时候，需要对头部以后的数据进行复制重排，所以效率很低。而LinkedList是基于链表实现，在添加元素的时候，首先会通过二分法循环查找到添加元素的位置，所以LinkedList添加元素到头部是非常高效的。

同上，ArrayList在添加元素到数组中间时，同样有部分数据需要复制重排，效率也不是很高；LinkedList将元素添加到中间位置，是添加元素中效率最低的，因为靠近中间位置，在添加元素之前的循环是遍历元素最多的操作。

而在添加元素到尾部的操作中，在没有扩容的前提下，ArrayList的效率要高于LinkedList，因为LinkedList中多了new对象以及变换指针的过程，所以效率要低于ArrayList。

删除

测试条件 测试结果(耗时)
从集合头部位置删除元素 ArrayList>LinkedList
从集合中间位置删除元素 ArrayList<LinkedList
从集合尾部位置删除元素 ArrayList<LinkedList

ArrayList和LinkedList删除元素操作的测试结果和添加元素操作测试的结果很接近，原理也相同。

遍历

测试条件 测试结果(耗时)
for( ; ; ) ArrayList<LinkedList
迭代器 ArrayList=LinkedList

我们可以看到，因为LinkedList基于链表实现，在使用for循环的时候，每一次循环都会遍历半个List，严重影响了效率；ArrayList基于数组实现的，并且实现了快速随机访问，所以for循环效率非常高。

注意：
for(:)循环[这里指的不是for( ; ; )]是一个语法糖，这里会被解释为迭代器，在使用迭代器遍历时，ArrayList内部创建了一个内部迭代器iterator，在使用next()方法来取下一个元素时，会使用ArrayList里保存的一个用来记录List修改次数的变量modCount，与iterator保存了一个expectedModCount来表示期望的修改次数进行比较，如果不相等则会抛出异常；

而在在foreach循环中调用list中的remove()方法，会走到fastRemove()方法，该方法不是iterator中的方法，而是ArrayList中的方法，在该方法只做了modCount++，而没有同步到expectedModCount。

当再次遍历时，会先调用内部类iteator中的hasNext(),再调用next(),在调用next()方法时，会对modCount和expectedModCount进行比较，此时两者不一致，就抛出了ConcurrentModificationException异常。

所以关键是用ArrayList的remove还是iterator中的remove。

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