1， java集合框架
2, Iterable and Iterators
3, 主要实现机制
3.1 数组：访问快插入慢
Arrays are used in the Collections Framework as the backing structure for ArrayList, CopyOnWriteArrayList, EnumSet and EnumMap, and for many of the Queue and Deque implementations. They also form an important part of the mechanism for implementing hash tables.
3.2 链表：插入快查找慢
Linked lists are the primary backing structure used for the classes ConcurrentLinkedQueue, LinkedBlockingQueue, and LinkedList, and the new skip list collections ConcurrentSkipListSet and ConcurrentSkipListMap. They are also used in implementing HashSet and LinkedHashSet.
3.3 hash表：基于内容查找比较快
Hash tables are the backing structure for many Set and Map implementations, including HashSet and LinkedHashSet together with the corresponding maps HashMap and LinkedHashMap, as well as WeakHashMap, IdentityHashMap and ConcurrentHashMap.
3.4 树：有序结构，插入没有链表快，查找没有数组快
Trees are the backing structures for TreeSet and TreeMap. Priority heaps, used in the implementation of PriorityQueue and PriorityBlockingQueue, are treerelated structures.
4， 算法效率
5， 并发
util.concurrent包下的集合比遗留的所有方法都加synchronized的集合吞吐量更高，因为锁粒度更小。
并发实现机制：
5.1 copy on write
Classes that use copy-on-write store their values in an internal array, which is effectively immutable; any change to the value of the collection results in a new array being created to represent the new values. Synchronization is used by these
classes, though only briefly, during the creation of a new array; because read operations do not need to be synchronized, copy-on-write collections perform well in the situations for which they are designed—those in which reads greatly predominate over writes. Copy-on-write is used by the collection classes CopyOnWriteArrayList and CopyOnWriteArraySet.
5.2 compare-and-swap (CAS)
An algorithm based on CAS behaves differently: it makes a local copy of the variable and performs the calculation without getting exclusive access. Only when it is ready to update the variable does it call CAS, which in one atomic operation compares the variable’s value with its value at the start and, if they are the same, updates it with the new value. If they are not the same, the variable must have been modified by another thread; in this situation, the CAS thread can try the whole computation again using the new value, or give up, or—in some algorithms— continue, because the interference will have actually done its work for it! Collections using CAS include ConcurrentLinkedQueue and ConcurrentSkipListMap.
5.3 java.util.concurrent.locks.Lock
A Lock has the same basic behavior as classical synchronization, but a thread can also acquire it under special conditions: only if the lock is not currently held, or with a timeout, or if the thread is not interrupted. Unlike synchronized code, in which an
object lock is held while a code block or a method is executed, a Lock is held until its unlock method is called. Some of the collection classes in this group make use of these facilities to divide the collection into parts that can be separately locked, giving improved concurrency. For example, LinkedBlockingQueue has separate locks for the head and tail ends of the queue, so that elements can be added and removed in parallel. Other collections using these locks include ConcurrentHashMap and most of the implementations of BlockingQueue.
基于5.1和5.2实现的集合枚举时不会抛出ConcurrentModificationException。基于5.3实现的集合使用fail-fast快速检测并发修改并抛出ConcurrentModificationException。fail-fast的实现机制类似乐观锁，每次修改版本号+1，如果枚举时检测到版本号变化，可以直接抛异常。
6，Collection
7，Set
7.1 HashSet
实现机制：完全依赖内部的HashMap的keySet实现
线程安全：线程不安全
适用范围：通用
7.2 LinkedHashSet
实现机制：完全依赖内部的LinkedHashMap的keySet实现，accessOrder默认为false，链表维护插入顺序，枚举时按插入顺序返回。
线程安全：线程不安全
适用范围：需要保持插入顺序时
7.3 CopyOnWriteArraySet
实现机制：完全依赖内部的CopyOnWriteArrayList实现
线程安全：线程安全。
适用范围：适用于容量小且读明显比写频繁的情景。修改代价高，所有元素复制一遍。
7.4 EnumSet
实现机制：内部根据枚举类型枚举值数量使用long或long数组存储，bit位的位置对应枚举常量的声明顺序，1表示对应的枚举值存在。
线程安全：线程不安全
适用范围：只能存储枚举类型，且所有值属于同一个枚举类型。
7.5 SortedSet 和 NavigableSet
7.5.1 TreeSet
实现机制：完全依赖内部的TreeMap的keySet实现。
线程安全：线程不安全
适用范围：根据指定的Comparator或元素自然顺序排序。
7.5.2 ConcurrentSkipListSet
实现机制：完全依赖内部的ConcurrentSkipListMap的keySet实现。
线程安全：线程安全
适用范围：元素有序，并发吞吐量高。但是占用空间多，添加删除要维护索引速度稍慢。
7.6 总结
8， Queue
add：加入队列，有界队列满时抛出异常。
offer：加入队列，有界队列满时返回false。
element：取回但不删除head，空队列抛异常
removed：取回并删除head，空队列抛异常
peek：取回但不删除head，空队列返回null
poll：取回并删除head，空队列返回null
8.1 PriorityQueue
实现机制：基于优先级堆(priority heaps)实现，按指定Comparator或自然顺序排序。priority heaps是一颗满足两个条件的二叉树：父节点大于两个子节点；除了叶子层，其他层次应该是满的，如果叶子层不满，全部靠左。
插入算法：先插入叶子层最左边的空节点，如果叶子层满了就插到最左边元素的左节点。然后跟父节点比较，大于父节点就交换，直到root。
删除算法：把被删除节点替换为以其为root的子树的叶子层的最右边元素，然后跟两个子节点比较，如果比子节点小，跟较小子节点交换，然后向下递归。
状态：
所有元素都保存在Object[]中，顺序是从上往下从左往右，所以n的两个子节点是2n+1，2n+2。
扩容：
插入：
删除：
线程安全：线程不安全
适用范围：无界，线程不安全的优先级队列。
8.2 ConcurrentLinkedQueue
实现机制：无界队列，按插入顺序先进先出，通过cas实现线程安全，支持并发修改，所以枚举和size等read操作不能返回精确结果。队列以单链表存储。
插入：
删除：
size：在size过程中，已经数过的节点可能被别的线程删除，结果不精确。
线程安全：线程安全，基于cas
适用范围：高吞吐量，但是读操作不精确。
8.3 BlockingQueue：
offer：添加元素，如果队列满了，等待直到超时。
put：添加元素，如果队列满了，一直等待。
poll：取元素，如果队列为空，等待直到超时
take：取元素，如果队列为空，一直等待。
加上从Queue继承的方法：添加和取回都有4中方法，空/满时：抛异常；返回null/false；阻塞直到超时；一直阻塞。
8.3.1 LinkedBlockingQueue
实现机制：基于单链表的可选有界队列。
状态：
添加：
删除：
线程安全：线程安全，生产和消费使用不同的可重入锁，并发度更好。
8.3.2 ArrayBlockingQueue：有界队列
实现机制：利用可重入锁的环形数组。
插入：
删除：
线程安全：线程安全，基于可重入锁
适用范围：
8.3.3 PriorityBlockingQueue
实现机制：线程安全版本的PriorityQueue，所有操作都使用可重入锁。
线程安全：线程安全，基于可重入锁。
8.3.4 DelayQueue：延迟队列
实现机制：所有元素都实现Delayed接口，附加过期时间，所有元素按过期时间排序，内部依赖一个可重入锁和一个PriorityQueue。
插入：
删除：
线程安全：线程安全，基于可重入锁
8.4 Deque 双向队列
push/pop：插入和删除都在head，就形成了stack结构。
8.4.1 ArrayDeque
实现机制：内部使用环形数组结构，首尾相遇时扩容一倍。
线程安全：线程不安全
8.4.2 LinkedList：即实现Deque又实现List，线程不安全。
8.4.3 ConcurrentLinkedDeque
实现机制：基于双向链表存储
线程安全：线程安全，基于cas
插入：
删除：
8.5 BlockingDeque
8.5.1 LinkedBlockingDeque
实现机制：看名字就知道啦。
线程安全：线程安全，生成和消费各有一个可重入锁。
8.6 算法效率总结
9 List：基于索引读写
subList：只是返回一个视图，返回的内部类所有读写都委托给外部类。
9.1 ArrayList
实现机制：内部基于数组存储，简单的数组操作
线程安全：线程不安全
扩容：每次50%
9.2 LinkedList
实现机制：基于双链表存储，简单的链表操作
线程安全：线程不安全
9.3 CopyOnWriteArrayList
实现机制：基于数组存储，读不加锁，每次修改，加锁，产生新的数组，复制元素。
状态：
添加：
线程安全：线程安全，基于可重入锁。
适用范围：集合元素少，且读的频率明显高于写。
9.4 Vector 和 Stack
实现机制：所有方法都加synchronized的ArrayList。
线程安全：线程安全，基于synchronized，吞吐量不如基于锁的实现。
适用范围：遗留集合，基本不用，Stack可以替换为LinkedBlockingDeque
9.5 性能比较
10 Map：最复杂的结构
10.1 HashMap
状态：
transient Node<K,V>[] table：数组 + 单链表(单桶节点少于8)/红黑树(单桶节点大于8 树中先按hash排序，hash相同的再按key排序)，每个元素根据 hash(key) % size(table)分散到不同的hash桶。
transient int modCount：修改版本号，枚举时快速检测并发修改抛出异常。
threshold：size>size(table) * loadFactor时，threshold和loadFactor都扩大一倍。
loadFactor：hash表的hash桶使用率
红黑树的元素TreeNode一共有7个指针(！！！)：
parent：树形结构父节点
left：左子树
right：右子树
parent，left，right一起构成红黑树结构
next：指向双链表的下一个节点
prev：指向双链表的上一个节点
next，prev构成双链表，存储红黑树的节点，链表头为红黑树的root节点
before：前一个
after：后一个
before，after构成另一个双链表，用于维护插入顺序(默认)或访问顺序。
添加元素：
删除元素：
查找：
扩容：
10.2 LinkedHashMap
实现机制：继承HashMap，元素继承HashMap的Node，额外添加before，after两个指针，在HashMap单链表数组的基础上额外维护一个所有元素的双链表。
双链表根据构造参数用于维护元素访问顺序或插入顺序(默认)
当维护元素访问顺序时，非常适合用于实现LRU缓存过期策略。
10.3 WeakHashMap
实现机制：HashMap的简化版，单桶元素过多时不会转成红黑树，所有的key都继承WeakReference，key在WeakHashMap外部无强引用时，会被gc回收，在key被gc回收后进入内部的ReferenceQueue队列。每次读操作都会先清理key被gc回收的元素：
10.4 IdentityHashMap
实现机制：以数组存储，数组长度永远都是2的指数，偶数存储key，+1为对应值。key比较引用相等。
计算hash：内存地址的低位
添加：key比较引用相等
10.5 EnumMap
实现机制：key必须是枚举值，内部使用两个数组存储，一个存储所有key的枚举值，一个存储对应的value。
10.6 SortedMap 和 NavigableMap
10.6.1 TreeMap
实现机制：基于红黑树实现，key按指定Comparator或自身排序。
先从简单的2-3树开始：
2-3树：每个节点可以有1或2个元素，2个元素的节点可以有3个子节点。
搜索：
单元素节点变双元素节点：
插入双元素节点，中间元素向上提升，两端元素拆成独立节点。
节点拆分：
红黑树：基于2-3树，2元素节点之间用红线连接，所有红线左倾，把所有红线拉平，所有叶子节点高度相同。插入单元素节点时，变成2元素节点，如果插入右子树，红线右倾，需要左旋。插入2元素节点变成3元素节点时，根据插入位置，进行合适的左右旋转之后转为两条红线的人字行，然后提升中间元素跟父节点合并，拆分其余元素为独立节点。
旋转：
单元素节点变双元素节点，如果是插入右子树需要左旋
双元素节点变三元素节点，一共分插入中间和插入两端三种情况，最后结果都是提升中间节点跟父节点合并，拆分另外两个节点：
三元素节点提升中间节点到父节点，然后递归处理：
10.7 ConcurrentMap：添加remove和replace等原子操作
10.7.1 ConcurrentHashMap
实现机制：跟HashMap一样的存储结构，通过cas实现线程安全，每次修改hash桶时锁定桶的第一个节点。读操作不加锁。resize时不像HashMap那样直接迁移整个hash表，而是多个线程通过cas锁定transferIndex每次迁移一个hash桶。
添加：
删除：
resize：
查找：不加锁
10.8 ConcurrentNavigableMap
10.8.1 ConcurrentSkipListMap
实现机制：基于性能类似红黑树但更易实现的跳表。
存储结构：底层数据节点采用普通的单链表。上层索引节点包含down和right两个指针以及被索引的节点，每层索引的第一个节点记录当前层次。
查找索引：
删除：
查找：
10.9 性能
java集合框架几乎所有重要集合及其实现机制分析完毕！！！
