前言

Java集合估计是我们开发过程中，用的最多的API了，它位于java.util包下，同时支持多线程的集合类位于java.util.concurrent包下。

我们都知道各种数据结构最底层的组成都是数组或者链表，其实各种集合类也是基于最基本的数据结构进行封装，便于各种场景直接使用。

我们可以把集合想象成一个容器，它可以存储各种对象，扩展和封装了数组和链表，通过算法实现。

有了这些认识，是不是集合也变了没那么抽象了，后续将陆续更新各种常见集合类的底层实现。—慢慢更新

------万变不离其宗，各种集合就像各门各派的招式，但是其本质都是数据结构和算法。

好吧，这是一个不那么合适的比喻。天下武功，唯快不破，透过事物的本质，方能笑傲江湖…扯远了，能不被各路面试官虐惨就心满意足了…

集合框架

Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue，这4个接口又分别衍生出了很多的实现类。

孙猴子毫毛一吹，子孙千千万？

Collection接口的主要子类关系，如下图所示：

Collection相当于容纳了其他对象的引用，而构成了一个集合的对象，整个集合可以有序的，也可以无序的，它本身不能被直接实现，需要去实现它的子接口如：List，Set。

List接口是一个有序的Collection，能够精准的控制列表中每个元素的插入位置，能够通过索引来访问List中的元素（List中的元素位置，类似数组下标，第一个元素位置为0），允许有相同的元素，且允许null。

常见的实现：ArrayList（查询快）、LinkedList（增删快）。传送门：【Java集合】ArrayList源码解析、【Java集合】LinkedList源码解析。

喂喂，不是还有另外一个儿子Vector吗，对不起，他已经被后浪排在沙滩上了…

Queue接口以队列实现了Collection，队列当然满足一定的队列顺序了，除了优先队列外，都是满足FIFO（先进先出）方式排序元素。Queue实现通常不允许插入null元素，因为null经常被poll方法用做识别队列是否包含元素。

常见的实现：PriorityQueue（优先队列），你期待的传送门还没开启…

Set接口具有和Collection完全一样的接口，只是行为上不同，Set不保存重复元素，且对象是唯一的。

常见的实现：HashSet（由Hash表实现）、LinkedHashSet（由链表和Hash表实现）、TreeSet（有序的Set），你期待的传送门还没开启…

看完Collection：列表，我们再来看看Map：图，以key-value键值对映射关系存储元素。

Map接口的主要子类关系，如下图所示：

将key映射到value的对象，不能包含重复元素，每个key最多映射一个value。

Map实现的类较多：HashMap、HashTable、SortedMap、LinkedHashMap、TreeMap等。你期待的传送门还没开启…

看到这里，应该对Java集合有了整体宏观的认识，你肯定会问：后宫三千，我该选哪个好呢？…醒醒，天亮了

List和Set的区别

1. List接口实例存储是有序的，可以重复的元素；Set接口实例存储的是无序的，不重复的数据；
2. List和数组类似，可以动态增长，根据实际存储的数据长度自动增长List的长度。查找元素效率高（直接通过索引），插入删除效率低（因为会引起其他元素位置变动）；
3. Set查询效率低下，删除和插入效率高，插入和删除不会引起元素位置的变化。

常见的集合实现类

1. ArrayList：实现了可变大小的数组，可以随机访问和遍历元素；非同步类；动态增长当前长度的50%；插入删除效率低（会引起其他元素位置变动）。
2. LinkedList：主要用于创建链表数据结构，没有同步方法，需要手动加锁。
3. HashSet：不允许出现重复元素，集合中元素是无序的；允许为null，但最多一个；不同步，需要手动加锁。
4. LinkedHashSet：具有可预知迭代顺序的Set接口的哈希表和链接列表实现。
5. TreeSet：可以实现排序的Set集合。
6. HashMap：散列表，存储的内容是key-value，根据key的HashCode值存储数据，具有快速访问速度；最多允许一个记录的key为null；不支持线程同步。
7. TreeMap：使用了红黑树来实现的Map，不同步。
8. WeakHashMap：使用弱密钥的哈希表，不同步。
9. LinkedHashMap：使用元素的自然顺序对元素进行排序，不同步。
10. IdentityHashMap：比较键（和值）时使用引用相等代替对象相等。

线程安全集合类

前面讲的集合类好像都是非安全的，那么安全的集合类有哪些呢？

1.CopyOnWriteArrayList：

1）线程安全的List，修改方法（add，set，remove等）都通过集合属性一个ReentrantLock进行同步，先获取锁，才能执行变更操作。但是通过ReentrantLock进行同步只是能保证线程的安全，并不能保持时间上的有序和正确，因为先申请锁然后进入休眠等待的线程，并不一定是最先获取锁的线程，所以，会在时间顺序看，对集合的修改是无序的。
2）对象数组用volatile修饰，其他线程对集合元素数组的修改，能够在其他线程的每次访问都是最新值。
3）在对集合元素数组进行修改时，是先拷贝之前的元素数组出一个新元素数组，在新的元素数组上进行修改，修改完毕后在用元素数组替换旧的元素数组，内存消耗大。

2.ConcurrentSkipListSet：

ConcurrentSkipListSet是实现了NavigableSet接口和继承自AbstractSet的Set集合类，它是线程安全的，内部存储实际是存在ConcurrentNavigableMap中。内部元素的存储是有序的，根据创建ConcurrentSkipListSet时提供的Comparator。

3.CopyOnWriteArraySet：

CopyOnWriteArraySet底层实现是CopyOnWriteArrayList,线程安全的，大部分操作和原理是同CopyOnWriteArrayList。

4.ConcurrentHashMap：

ConcurrentHashMap是线程安全的HashMap，实现了ConcurrentMap接口，所以提供了一些原子性和线程安全的集合操作接口。
JDK1.8之后的ConcurrentHashMap的实现和1.7之前已经大不一样了，保证线程安全的机制从原来的给每个数组segment加锁方式变成了无锁的cas操作，特别是扩容方式被重写了，实现了无锁情况下多线程参与复制旧存储元素到新存储集合上。有一个最重要的不同点就是ConcurrentHashMap不允许key或value为null值。

5.HashTable：

HashTable是线程安全的HashMap,其实就在修改方法上添加synchronized关键字进行同步，同步的粒度太大，性能不佳，不建议使用。

6.ConcurrentSkipListMap：

ConcurrentSkipListMap是基于SkipList存储结构实现的线程安全的有序Map集合，不支持Null为value或者为key，线程安全且有序。

迭代器和比较器

迭代器（Iterator接口）提供了一种方法，来对集合、容器进行遍历的方式，使你能够通过循环来得到换删除集合元素。
ListIterator接口继承于Iterator接口，允许双向遍历列表和修改元素。

比较器（Comparator接口），集合实现Comparator接口，就可以按照你定义的排序方式进行排序。

小结

后续会深入各个集合类的源代码进行分析学习，敬请期待…
【Java集合】ArrayList源码解析
【Java集合】LinkedList源码解析