Java中集合主要分为以下几类：
1: List
2: Set
3: Map
4：Queue
它们的总体关系如下：
从上图可以看出， List, Set, Queue 三类集合框架都继承自Collection接口，而Map接口是独立的。
各种类型的框架都有那些特点？
(1) List: 有序、可重复。
首先解释有序的概念，有序指的是类似数组的存放方式，比如有三个元素，1, 2, 3 依次存放到List中
用户取出来的时候，取List的下标为0, 那肯定是元素1， 取下标为1，那元素肯定是2，
取下标为2，则取出来的元素肯定是3。
而Set集合是无序的， 这个其实就是链表和哈希表的区别， List是链表或数组的存放方式， 是有序的。
而Set是哈希表的存放方式，哈希表的内部存储是固定的，但并不能保证是按照用户存入的顺序来保存的。
再说一下可重复的概念： List是链表， 它可以存放两个一样的数据，只要知道它的下标，就很容易区分两个对象， 而Set属于集合，是无序的， 也就是放两个一样的数据，根本没办法分出那个是那个。
(2) Set: 无序，不可重复
Set是如何判断两个元素是否重复呢？
是通过对象的HashCode()方法和equals()方法，来共同判断对象是否重复的。
(3) Queue: Java中的队列分为两种： Queue 和 Deque
Queue: 表示正常的队列，队头取数据，队尾存数据。
Deque: 表示双端队列，支持在头部、尾部进行存、取元素。
(4) Map: 适用于键值映射的情况。
接下来详细介绍每种集合的子类及其特点
(一) List
首先看下List的的整体架构
从以下架构图可以看到，List的子类分布有：
ArrayList：
LinkedList
Vector
Stack：
首先看ArrayList的实现，通过名字可以发现，它的内部实现是通过数组来实现的。是通过一个动态数组来实现的，既然 是通过数组实现的，那一定有一个默认的初始值大小，这个值可以由用户指定,也可以使用默认的值
List aList = new ArrayList(4) ;// 那么初始值大小是4
如果使用默认的如： List bList = new ArrayList(); // 默认的大小为10
那么，如果超出这个范围后，List长度的扩充方案是什么样的的，看下面的公式：
int newSize = ((currentSize * 3) / 2) + 1; // 也就是当前List的大小乘以3 再除以2 , 最后加1。得出新的容量。
int newSize = (currentSize * 3) / 2 // JDK 1.7后就不会加1了，直接乘以1.5倍。
它的实现方式决定了他的特点如下：
1： 数组存储方式
2：插入数据比较慢， 但检索数据比较快。
数组的插入慢，主要用在耗费在移动元素上面， 检索就是直接使用数组下标，所以非常快。
3：线程不安全。
如果多线程操作，必须在上层保持同步。 或者使用替代方案。
使用Collections.synchronizedList 或 CopyOnWriteArrayList 来实现线程安全的列表。
(在ArrayList源码分析时，会分析以下两者怎么保证线程安全，以及它们的性能如何)
4： 适合于大量随机访问的情况，但不适合频繁的插入和删除操作。
LinkedList
LinkedList它的实现方式是类似主于C语言中的指针来实现的，学过C语言的同学一定知道，自己写个链表也不是什么难事，
链表的特点：
1： 链表的数据保存，在内存中并不像数组一样，是连续存放的，链表的数据是分散存放的，数组的存放方式为，知道数组的第0个元素，就可以推断出剩下的所有的元素的位置，而链表也需要同样的操作，就需要获取关键的一个点，那就是链表的Head，这个就相当于数组的首元素，必须要知道，要不然链表是没法操作的。
2： 链表适合插入和删除操作，不适合查找频繁的操作，因为插入和删除操作对于链表来说，就是个指针的修改，比ArrayList要高效的多。
Vector
是线程安全版的ArrayList， 底层使用数组实现，可以让用户指定扩容的大小，默认为扩容2倍大小，
与ArrayList的区别：
1: Vector是线程安全的，而ArrayList是线程不安全的， vector的线程安全是通过synchronized来实现的。
2： Vector默认扩容是2倍，ArrayList默认扩容为1.5倍。
3: 如果没有线程安全的需求，最好使用ArrayList, Vector的每个方法都加了synchronized，开销太大了。
Stack
是Vector的子类，实现栈的后进先出操作。
（二）Set
首先看Set的特点，
1： 不能重复：
2: 无序： 指两方面的概念：
1: 是插入的顺序(添加顺序)，
2： 经过排序后的顺序 (自然顺序)
Set类的子类有那些？
1: HashSet
2: LinkHashSet
3: SortedSet
4: TreeSet
HashMap,
1: 不能保证插入顺序，也不能保证自然顺序。
2: 数组初始大小为16，加载因子为0.75
3:线程不安全。
LinkHashMap
1: 内部使用LinkList保证插入顺序，但不能保证自然顺序。
2: 初始大小为16，加载因子0.75
3:线程不安全。
3:identityHashMap
1: key值 只有是一个对象的情况下才认为是重复，key == newKey
2: hashmap是只要key的内容一样就认为重复，key.equals(newkey)
TreeMap
0: 使用红黑树算法实现的，需要了解的概念为：二叉树的性质，平衡二叉树、红黑树等概念。
1、TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口，也因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，而HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key。
2、TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才使用TreeMap。
3、TreeMap的key不能为null，而HashMap的key可以为null。
WeakHashMap
1: 与HashMap一样，是一个散列表，存储方式也是key-value， 而且key与value都可以为null。
2: WeakHashMap中有一个ReferenceQueue, 用于保存Key值的引用, 而且每个Entry实体都是一个WeakReference, 看如下代码：
private static final class Entry<K, V>
extends WeakReference<K>
implements Map.Entry<K, V> {
}
既然每个Entry都是WeakReference， 那么当对象被回收的时候，此Entry也会被回收。
我们先看插入一个新的数据的代码实现
public V put(K key, V value) {
poll();
int index = 0;
Entry<K, V> entry;
if (key != null) {
index = (Collections.secondaryHash(key) & 0x7FFFFFFF) % elementData.length;
entry = elementData[index];
while (entry != null && !key.equals(entry.get())) {
entry = entry.next;
}
} else {
entry = elementData[0];
while (entry != null && !entry.isNull) {
entry = entry.next;
}
}
if (entry == null) {
modCount++;
if (++elementCount > threshold) {
rehash();
index = key == null ? 0 : (Collections.secondaryHash(key) & 0x7FFFFFFF)
% elementData.length;
}
entry = new Entry<K, V>(key, value, referenceQueue);
entry.next = elementData[index];
elementData[index] = entry;
return null;
}
V result = entry.value;
entry.value = value;
return result;
}
首先看，插入元素前，先执行poll()方法，此方法就是为了把RefreneceQueue中的元素全部移除掉，因为“弱引用”的关系，加入RefrenceQueue中的元素，肯定是被系统回收掉的，所以先清理一下。
接下来，如果key != null ， 则计算新值在数组中的位置
index = (Collections.secondaryHash(key) & 0x7FFFFFFF) % elementData.length;
则使用Collections.secondaryHash来计算Key的Hash值，然后再与0x7FFFFFFF来计算最终的值，与数组长度进行最后确定在数组中的位置。
TODO : Collections.secondaryHash(key) 这个方法需要再研究一下。
ConcurrentSkipListMap
要了解这个类，首先要了解一个SkipList跳跃表。
特点：
1: 由并联的链表实现，其查找效率可以比拟二叉查找树。
2: 采用“空间换时间”的思想，除了原始链表以外，还保存一些“跳跃”的链表，用于辅助加速查找的效果。
3: 链表要保证有序。
SkipList产生的过程：
以上由于二分查找法，特点列表有序，可以快速查找，而链表的特点是：
查找比较慢，但插入和删除比较快， 有没有一种即查找快，又插入删除快的呢？
那就是二叉查找树了。
又因为二叉查找树最坏的情况下会变成一个链表，所以出现了平衡二叉树，
根据平衡二叉树的算法不同，又分为AVL树，B-Tree, B+Tree, 红黑树。
又因为AVL树实现起来比较复杂，平衡操作更难理解。这个时候就出现了SkipList跳跃表结构。
目前常用的key-value数据结构有三种：
Hash表、
红黑树、
SkipList，它们各自有着不同的优缺点（不考虑删除操作）：
Hash表：插入、查找最快，为O(1)；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。
红黑树：插入、查找为O(logn)，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。
SkipList：插入、查找为O(logn)，但常数项比红黑树要大；底层结构为链表，可无锁实现；数据天然有序。
如果要实现一个key-value结构，需求的功能有插入、查找、迭代、修改，那么首先Hash表就不是很适合了，因为迭代的时间复杂度比较高；而红黑树的插入很可能会涉及多个结点的旋转、变色操作，因此需要在外层加锁，这无形中降低了它可能的并发度。而SkipList底层是用链表实现的，可以实现为lock free，同时它还有着不错的性能（单线程下只比红黑树略慢），非常适合用来实现我们需求的那种key-value结构。
LevelDB、Reddis的底层存储结构就是用的SkipList。
基于锁的并发
优点：
1、编程模型简单，如果小心控制上锁顺序，一般来说不会有死锁的问题；
2、可以通过调节锁的粒度来调节性能。
缺点：
1、所有基于锁的算法都有死锁的可能；
2、上锁和解锁时进程要从用户态切换到内核态，并可能伴随有线程的调度、上下文切换等，开销比较重；
3、对共享数据的读与写之间会有互斥。
无锁编程（lock free）
常见的lock free编程一般是基于CAS(Compare And Swap)操作：CAS(void ptr, Any oldValue, Any newValue);
即查看内存地址ptr处的值，如果为oldValue则将其改为newValue，并返回true，否则返回false。X86平台上的CAS操作一般是通过CPU的CMPXCHG指令来完成的。CPU在执行此指令时会首先锁住CPU总线，禁止其它核心对内存的访问，然后再查看或修改ptr的值。简单的说CAS利用了CPU的硬件锁来实现对共享资源的串行使用。
优点：
1、开销较小：不需要进入内核，不需要切换线程；
2、没有死锁：总线锁最长持续为一次read+write的时间；
3、只有写操作需要使用CAS，读操作与串行代码完全相同，可实现读写不互斥。
缺点：
1、编程非常复杂，两行代码之间可能发生任何事，很多常识性的假设都不成立。
2、CAS模型覆盖的情况非常少，无法用CAS实现原子的复数操作。
