起因

好像Java面试必不可少的一个问题就是，Java中集合有哪些？分别有什么特点。照搬各种《XXX从入门到放弃》，集合有2种类型，一个是有序可重复的List，一个是无序不可重复的Set，可是真的用起来的时候好像就不是简单的这样了。

先来看一下集合的整体关系图(并发包中的集合没有考虑进来，仅看java.util包)

第一眼看上去我也懵，本来以为自己天天用的那些集合类已经差不多了，然后发现一坨坨的没见过没用过的。

那就啃吧。。

Collection

Collection应该是老大哥级别的了，算是集合类的鼻祖（迭代器忽略），定义了一个集合应该有的基本方法，包括增删迭代等，这个就不多说了。
1.8版本开始，增加了流式操作的几个default方法(先不关注了)

List

List应该是集合中用的最多最多的了，平时搬砖，基本上几行代码就要加上一个List存储各种元素。忽略抽象方法，整理一下对应的实现类

ArrayList

ArrayList应该是日常搬砖使用最多的的实现了，特点如下:

底层实现是数组，对应代码:
1
transient Object[] elementData;

实现了动态扩容方法，简单说就是容量不够了，我就新建一个数组，然后将原来的数据拷贝到新数组中。从代码int newCapacity = oldCapacity + (oldCapacity >> 1);中也可以看出来，每次扩容变为原本的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);
}

线程不安全，所有方法没有加锁，多线程存在并发问题
因为底层实现是数组，所以随机读取速度很快，并不是说不适合插入数据，而是不适合在中间或者头部插入数据。因为插入数据之后，当前位置后面的元素都要往后移动，成本相对来说比较大了。代码如下:
1
2
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
删除操作也是同理，在末尾操作其实影响不大，但是在中间和数组起始位置操作成本就有点高了。
更新操作影响很小，直接找到对应数组下标，然后替换就可以了。
indexOf和contains以及lastIndexOf方法都是直接进行遍历，因为数组是无序的，也没办法采用二分法之类的进行快速查找。所以尽可能不要直接使用List的查找方法。
size方法成本不高，并不是每次都进行统计，而是内部存储了一个size变量，每次增删操作回进行更新。
暂时想到的就这么多，以后想起来再补充。

Vector

这个可是个老古董了，从JDK1.0开始就存在了（别问我怎么知道的，那会我也没用过Java，是文档自己写的。。。。），正因为是老古董，所以现在已经不是很推荐使用了，原因就是效率很低下，因为很多方法都暴力的增加了synchronized关键字，性能很低下。做个简单总结吧：

因为很多方法都加上了synchronized关键词，导致整体性能较差，不推荐使用
底层实现也是数组，特性和ArrayList差不多。
注意：Vector没有实现Serializable接口

关于扩容：ArrayList每次扩容是1.5倍，Vector是2倍。代码如下：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);//扩充一倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

capacityIncrement是构造方法传进来的，如果不指定，则传0。

Stack

这个类已经快被遗忘了，简单概述一下。

1.0时代的远古产物，继承了Vector，所以也是各种synchronized关键字，性能低下
官方注释已经不推荐使用了，同样的功能可以使用Deque实现
1
Deque<Integer> stack = new ArrayDeque<Integer>();

LinkedList

你以为LinkedList仅仅是一个链表实现的List的么？？那你就是图样图森破了，来看看强大的LinkedList吧。

看一下接口层面：List、deque和Queue，也就是说LinkedList不仅仅是一个list集合，同时也是一个双向队列，当然也可以作为单向队列来使用。所以根据场景，上面的Stack也可以使用LinkedList进行替换

底层的实现是基于链表，基本存储数据的元素是Node，代码如下：

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

正是因为基于链表实现，所以理论上在任意位置进行增删操作都是O(1)的时间复杂度，但是为什么我说是理论上呢？因为实际进行增删的时候，必须要先找到对应的位置吧？这个查找的过程时间复杂度可就是O(n)了。
LinkedList同样没有加任何同步措施，因此也是线程不安全的。
说一个坑点：千万不要在for循环中通过索引的方式去获取元素（之前实习生干了这个事。。。），因为链表的通过索引方式进行随机读取的时间复杂度是O(n)!

简单汇总一下

列	ArrayList	LinkedList	Vector	Stack
实现方式	数组	链表	数组	数组
线程安全	否	否	是	是
优势	适合随机读，末尾写	适合随机写，顺序读	线程安全	线程安全
劣势	不适合随机写入	不适合随机读取	性能差	性能差
扩容	1.5	-	2	-

Set

上面简单总结了一下List相关实现，接下来看看狐假虎威的Set。为啥说Set是狐假虎威呢？看看对应的实现类就明白了，基本上都是Map套了个壳（Map稍后总结）

HashSet

基于Hash实现的Set，内层实现是HashMap，所有的操作都是HashMap的Key的操作，而Map的实际Value则是一个Object对象。总结一下特点：

判断是否存在速度很快，基于Hash实现如果不出现冲突，基本都是O(1)的操作。
线程不安全，需要自己实现线程同步方式
元素唯一（前提重写HashCode和equals方法,只有两者都相同才被认为是同一个元素）
不保证顺序，因为基于Hash实现，无法保证读取时候的顺序(也就是通过迭代器方式读取无法保证顺序，不过貌似重写HashCode之后，可以在一定程度上控制顺序，但是最好不要这么用。。)
因为底层实现是HashSet，所以也存在初始容量和负载因子，因此使用的时候如果事先知道存储大小，最好指定一下大小和负载因子，减少扩容消耗。
因为HashSet支持null作为key，所以HashSet也可以存储null元素

LinkedHashSet

LinkedHashSet也是一个壳，继承了HashSet，注意一下HashSet内部还有一个带有boolean的构造方法，调用这种构造方法，则内部实现不再是HashMap，而是LinkedHashMap。

LinkedHashSet和HashSet最大的区别就是能保证元素插入的顺序和通过迭代器读取的顺序是一致的(但是不是经过排序的，是保留插入的顺序)。
除了有序这个之外，其他特点和HashSet一样，因为继承了嘛(写这个类的人，真的是懒到极致的。。向他学习！)

TreeSet

看到TreeSet是不是立即想到了TreeMap？对的，TreeSet内部就是一个NavigableMap，NavigableMap又是什么？java.util包下原生的实现且暴露出来的好像只有。。。。TreeMap。。。

内部实现是TreeMap，也就是基于红黑树（啥是红黑树？。。。自行百度。。）,所以整体操作复杂度事O(log(n)),表面上看不如HashSet的O(1)速度快，但是一旦出现大量Hash冲突的时候，HashSet性能将急剧下降，因为冲突导致查询变为链表遍历(好像1.8还是1.7开始，冲突元素个数增加到8就会进行树化，防止链表过长)，而TreeSet不会存在这个问题。
TreeSet实现了NavigableSet接口和SortedSet接口，也就是说TreeSet中的元素是有序的，同时是支持范围查询,查找大于或者小于某个元素的元素或者集合(具体看NavigableSet接口)，这些都是HashSet无法提供的。
线程不安全，补充：因为红黑树实现复杂，并发粒度控制困难(应该是这个原因)，官方没有提供TreeSet对应的并发类，而是提供了基于跳表实现的并发类(后面再说)
其他想到了再补充。。

EnumSet

EnumSet是一个抽象类，有两个实现：

RegularEnumSet
JumboEnumSet

注意一下，这两个类都是不对外暴露的，对外统一暴露的是EnumSet。这两个类有啥区别呢？RegularEnumSet存储的是元素个数小于等于64个，JumboEnumSet则是超过64个。
为啥要单独出来一个EnumSet呢？HashSet，TreeSet也是可以存储枚举的啊，查了一堆资料(实际上我也没用过这玩意。。)，总结如下：

EnumSet的速度很快，原因是底层用了elements进行位运算，也就是说EnumSet并不直接存放枚举对象，而是存储一个对应类和elements，通过位运算来判断Set中有哪些元素，速度自然要快得多。
一旦元素的枚举类型确定那么集合就确定了（因为要通过枚举类型进行位判断，如果更换了枚举类型，会导致结果出错，所以不允许修改）
EnumSet只能存放一种枚举类型的元素(原因同上)

Queue

一个先入先出的数据结构，util包下实现好像只有下面3个，这个主要在juc包下实现类较多(各种阻塞队列)

LinkedList

前面已经说过，不再多说了。

ArrayDeque

和LinkedList相比，最大不同就是底层实现是依赖于一个数组,简单汇总一下其特点:

实现依赖于一个循环数组
扩容: 扩容直接将容量翻倍，然后执行数组拷贝
容量：要求必须是2的幂次方(方便进行位移运算)
优势：和LinkedList相比，无需用Node对数据进行包裹，而且数组通过下标访问速度很快
应用场景:额。。。其实我也没怎么用过，感觉常用栈和队列都可以用这个实现(好吧，以前我都是用LinkedList实现栈的操作。。。)

PriorityQueue

这个感觉平时用的也很少，是一个带有优先级的队列(并发包中的优先队列貌似使用场景更多一些。。)，这个研究不多，直接当个搬运工吧(参考:https://www.cnblogs.com/mfrank/p/9614520.html)

内部是根据小顶堆的结构进行存储的
构造方法需要传入一个比较器，用于判断优先级
内部实际上也是使用一个数组进行数据存储，同时有一个heapify()方法，用于将数组进行堆化(具体过程就不描述了。。。)
应用场景，基本上就是堆的应用场景，比如寻找topN之类的

顺便肯一下另外一组容器

Map

Map我的理解就是存储键值对的容器，基本上每一种开发语言都有这种容器，比如Python,C#的字典，golang的map，应该说Map是和数组一个级别的重要容器了。最常用的应该是基于Hash实现的HashMap，当然还有基于红黑树的TreeMap。先看一下Map相关的类图：

简单总结一下：

HashMap

最常用的Map，没有之一(至少我工作这两年看到的Map，九成以上都是HashMap)，应该也是面试必问容器，后面估计要专门整理一篇HashMap的总结了(网上各种总结已经一大把了。。)，简单总结一下特点：

基于hash的方法，能够快速通过key找到对应的value
内部存储数据是基于数组，Node<K,V>[] table;
线程不安全(几乎面试都会问到，然后就自然转到了juc的并发包了)
Key建议使用字符串，当然用自定义对象也可以，但是要重写hashcode和equals方法，否则不保证正确性了。
hash冲突的解决是通过链表方式，链表长度超过8以后，转为红黑树，当长度减少到6一下，再次转换为链表。(原因是怕链表长度过长，导致查询速度过慢，而冲突变少之后使用链表和树速度差别小，但是复杂度来看，链表要简单。。好吧，也是强行解释)
迭代遍历不保证顺序
允许null作为key和value

Hashtable

远古产物，并且类命名还不对，正确命名应该是HashTable，估计是当时开发人员粗心，写成了Hashtable，然后为了兼容性，那就错着把。。。功能上和HashMap基本一样，简单总结一下:

线程安全，但是性能低下，全部基于synchronized关键词实现。
不允许null作为key和value

LinkedHashMap

与HashMap相比，保留的key的插入顺序性，遍历的时候和插入的顺序一致
原理是内部维护了一条双向链表，记录插入的顺序
额外增加了空间和时间上的开销
应用场景
- 保留插入顺序的遍历场景
- LRU缓存的实现(可以看一下MyBatis的缓存实现，其中就有基于LinkedHashMap的LRU缓存)

TreeMap

这个因为红黑树实现，有点复杂(面试在单独复习红黑树吧。。)，所以就不管内部具体实现了，总结一下特点

线程不安全，即使是在并发包中也没有TreeMap的并发类
实现了SortedMap接口，说明Key是有序的
遍历的时候根据Key的自然顺序进行，或者指定Comparator比较器
实现了NavigableMap接口，也就是说支持区间范围或者比大小操作(基于Key的)
整体操作复杂度均为O(log(n))

EnumMap

针对枚举类作为Key的情形进行优化的Map，内部通过数组存储，查找的时候直接通过枚举的ordinal作为index快速查询。

只能支持单一类型枚举

IdentityHashMap

陌生么？陌生。。。陌生就对了，因为日常开发中，压根就不会用到这玩意。。这玩意干嘛用的，它实际上是严格版本的HashMap，有多严格？引用必须相等！

HashMap中判断key相等的依据是key.equals(otherKey),而IdentityHashMap判断key相等的依据是key==otherKey，这种严格的限制，恕我无知。。我实在是找不到应用场景。。关键这个类还是大神Doug Lea写的。。。大神的思维。。不懂。。不懂。。

WeakHashMap

这个容器使用之前最好先了解一下Java中的引用(强软弱虚)，WeakHashMap是一种弱key实现的容器，使用场景主要还是缓存吧(反正我没用过。。。)，说一下特点

当key被GC回收后，对应Map中的KeyValue対也会被回收，附代码示例:

public static void main(String[] args) throws InterruptedException {
    WeakHashMap<String, Object> map = new WeakHashMap<>();
    String k1 = new String("k1"); //注意一定要使用new String("xxx")，形式
    String k2 = new String("k2");
    String k3 = new String("k3");
    map.put(k1,new Object());
    map.put(k2,new Object());
    map.put(k3,new Object());
    System.out.println(map);
    System.gc();
    Thread.sleep(500);
    System.out.println(map);
    k1 = null;
    k2 = null;
    k3 = null;
    System.out.println("Key=null -> " +map);
    System.gc();
    Thread.sleep(500);
    System.out.println("After GC -> " +map);
}

Properties

以前我还真不知道Properties竟然也是Map的实现类，内部主要是各种读取配置文件相关逻辑，存储方面由于继承了Hashtable，所以也是线程安全的，关于这个就不分析啥了。。

总结

糊里糊涂整理了一下java.util包下面的集合相关类(容器类也行。。)，发现了几个平时开发中没用过的容器，但是其实是都可以用的。。。比如ArrayDeque，比如Enum相关Set和Map(恕我无知，之前真的都是通过HashSet和HashMap实现的。。。)。等后续有时间了，整理一下并发包下面的容器（好像已经烂大街了。。。）

Eviltuzki

Java 集合类整理

起因

那就啃吧。。

Collection

List

ArrayList

Vector

Stack

LinkedList

简单汇总一下

Set

HashSet

LinkedHashSet

TreeSet

EnumSet

Queue

LinkedList

ArrayDeque

PriorityQueue

顺便肯一下另外一组容器

Map

HashMap

Hashtable

LinkedHashMap

TreeMap

EnumMap

IdentityHashMap

WeakHashMap

Properties

总结