List
ArrayList
以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时，创建大小为10的数组。
基本优势
按数组下标访问元素get(i) set(i, e)的性能很高。
直接在数组末尾加入元素add(e)的性能也高。
基本劣势
如果按下表插入、删除元素add(i, e) remove(i) remove(e)，则要用System.arraycopy()来移动部分受影响的元素，性能就变差了。
LinkedList
以双向链表实现。链表无容量限制，但本身使用了更多空间，也需要额外的链表指针操作。
基本优势
不需扩容，调整容量
在链表两头的操作add() addFirst() removeLast()能省掉指针的移动
基本劣势
按下标访问元素get(i) set(i, e)要遍历链表，将指针移动到位。如果i>数组大小的一半，会从末尾移起。
CopyOnWriteArrayList
并发优化的ArrayList。用CopyOnWrite策略，在修改时，先复制一个快照来修改，改完再让内部指针指向新数组。
因为对快照的修改对读操作不可见，所以只有写锁没有读锁，加上复制的昂贵成本，典型的适合读多写少的场景。如果更新频率较高，或者数组较大时，还是Collections.synchronizedList(list)，对所有操作用同一把锁来保证线程安全更好。
Map
HashMap
用key的哈希值%桶数组的大小可得到数组下标。
插入元素时，如果两条key落在同一个桶，Entry用一个next属性实现多个Entry以单向链表存放，后入桶的Entry将next指向桶当前的Entry
当Entry数量达到桶数量的75%时，会成倍扩容桶数组，并重新分配所有原来的Entry，所以这两也最好有个预估值。
取模用位运算(hash & (arrayLength-1))会比较快，所以数组的大小永远是2的N次方。默认第一次放入元素时的初始值是16。
在JDK8里，新增默认为8的閥值，当一个桶里的Entry超过閥值，就不以单向链表而以红黑树来存放以加快Key的查找速度。
LinkedHashMap
扩展HashMap，增加了双向链表的实现，号称是最占内存的数据结构。
TreeMap
以红黑树实现。
ConcurrentHashMap
并发优化的HashMap，默认16把写锁（可以设置更多），有效地分散了阻塞的概率，而且没有读锁。
数据结构为Segment[]，Segment里面才是哈希桶数组，每个Segment一把锁。Key先算出它在哪个Segment里，再算出它在哪个哈希桶里。
Set
Set几乎都是内部用一个Map来实现的。
将Map里的KeySet当做一个Set，而Value是假值，全部使用同一个Object。Set的特征也继承了那些内部Map实现的特征。
HashSet：内部就是HashMapLinkedHashSet：内部就是LinkedHashMapTreeSet：内部就是TreeMap的SortedSetConcurrentSkipListSet：内部就是ConcurrentSkipListMap的并发优化SortedSet
Queue
Queue是在两端出入的List，所以也可以用数组或链表来实现。
LinkedList
即是List，也是Queue。它是唯一一个允许放入null值的Queue。
ArrayDeque
以循环数组实现的双向Queue。大小是2的倍数，默认是16。
It represens a queue where you can insert and remove elements from both ends of the queue.
Adding and Accessing Elements
The order in which the elements added to the ArrayDeque are stored internally. ArrayDeque stores the elements in the order in which they are inserted.
You can peek at the element at the head of the queue without taking the element out of the queue.
PriorityQueue
用二叉堆实现的优先级队列，不再是FIFO，而是按元素实现的Comparable接口或传入Comparator的比较结果来出队，数值越小，优先级越高，越先出队。