集合总结（List、Map、Set）

集合要掌握的是ArrayList、LinkedList、Hashtable、HashMap、ConcurrentHashMap、HashSet的实现原理，当然能掌握CopyOnWrite容器和Queue是再好不过的了。

ArrayList实现原理

ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长。  对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。
ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。ArrayList中允许元素为null。
           

LinkedList实现原理

LinkedList是基于双向链表的，是List接口的双向链表非同步实现，并允许包括null在内的所有元素。
对于顺序访问集合中的元素进行了优化。特别是插入，删除元素的速度特比快。LinkedList即实现了List接口，也实现了Deque接口。因此可以作为栈来使用。当向LinkedList添加对象，实际上则是内部生成一个Entry对象。
           

Hashtable实现原理

Hashtable 是一个散列表，它存储的内容是键值对(key-value)映射。它的key、value都不可以为null。此外，Hashtable中的映射不是有序的。
           

HashMap实现原理

HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。底层使用数组实现，数组中每一项是个链表，即数组和链表的结合体。
           

ConcurrentHashMap实现原理

ConcurrentHashMap 是一个并发散列映射表的实现，它允许完全并发的读取，并且支持给定数量的并发更新。ConcurrentHashMap是一个线程安全的支持高并发的HashMap集合类。
![转载自博客http://www.cnblogs.com/ITtangtang/p/3948786.html](https://img-blog.csdn.net/20170301170049177?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemhhbmdmZW5nemhhbmcxMjM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
           

HashSet实现原理

HashSet采用哈希算法，底层用数组存储数据。HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。

CopyOnWrite实现原理

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

CopyOnWriteArrayList就是ArrayList的并发实现。CopyOnWriteArrayList适合用于读操作远远大于写操作的情景中。

Queue实现原理

Queue用于模拟队列数据结构，采用“先进先出”的方式。包括PriorityQueue实现类（保存队列元素的顺序、按照队列元素的大小进行重新排序）、Deque接口（代表一个双端队列。同时Deque不仅可以作为双端队列使用，而且可以被当成栈来使用，所以可以使用出栈，入栈的方法）、LinkedList实现类（LinkedList既可以当做双端队列来使用，也可以当做栈来使用）。