这里的内容只是从下边来源的系列文章摘抄的一些关键内容，方便复习
来源：《深入理解Java集合框架》系列文章
ArrayList
- 顺序容器，底层通过数组实现
- 每个ArrayList都有一个容量（capacity,底层数组的实际大小）,添加元素时容量不足，容器会自动增加底层数组的大小（原来的1.5倍）
- size(), isEmpty(), get(), set()方法均能在常数时间内完成（O(1)复杂度）
- add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比，其余方法大都是线性时间
- 没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代
LinkedList
- 同时实现了List接口和 Deque接口，既可以看作顺序容器，也可以用作队列或者栈，底层实现是一个双向链表
- 成员变量first和last分别指向链表的头和尾
- 所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间
- 没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装
ArrayDeque
- 实现了Deque接口，Deque的含义是“double ended queue”，即双端队列，既可以当作栈使用，也可以当作队列使用
- 当需要使用栈时，Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque
- 底层通过循环数组实现，也就是说数组的任何一点都可能被看作起点或者终点，跟ArrayList一样，当容量不够的时候会自动增加数组的大小
- 成员变量head和tail分别指向第一个元素在数组中的位置和最后一个元素在数组中的位置的下一个位置，head不一定为0，tail也不一定比head大
- 非线程安全（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。
TreeMap
- 实现了SortedMap接口，会按照key的大小顺序对Map中的元素进行排序
- 底层通过红黑树实现，因此containsKey(), get(), put(), remove()都有着log(n)的时间复杂度
- 非同步（not synchronized），如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将TreeMap包装成（wrapped）同步的：SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…));
TreeSet
- 是对TeeMap的简单包装（TreeSet里面有一个TreeMap，适配器模式），对TreeSet的函数调用都会转换成合适的TeeMap方法
红黑树
- 一种近似平衡的二叉查找树，能够确保任何一个节点的左右子树的高度不会超过二者中较低那个的一倍
- 要满足以下条件：
- 1.每个节点要么是红色，要么是黑色
- 2.根节点必须是黑色
- 3.红色节点不能连续（也就是红色节点的孩子和父亲都不能是红色）
- 4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
- 在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。
- 插入节点时，一般插入红色节点，即可能会破坏条件2和3。
- 调整可以分为两类：一类是颜色调整，即改变某个节点的颜色；另一类是结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作：左旋（RotateLeft），右旋（RotateRight）。
HashMap
- 实现了Map接口，允许放入null元素
- 哈希表采用冲突链表方式
- 不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同
- **hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()**方法决定了这些对象是否是“同一个对象”
- 进行迭代时，需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将HashMap的初始大小设的过大。
- 初始容量（inital capacity）和负载系数（load factor）影响HashMap的性能，初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。
- hashmap的容量（table.length）必须是2的指数，这时hash(k)&(table.length-1)等价于hash(k)%table.length，因为table.length-1就是二进制低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了
- 除未实现同步外，该类其余跟Hashtable大致相同
HashSet
- 是对HashMap的简单包装（HashSet里面有一个HashMap,适配器模式），对HashSet的函数调用都会转换成合适的HashMap方法
LinkedHashMap
- 是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。
- LinkedHashMap维护双向链表时，实际维护的是一个循环双向链表，不像LinkedList那样，用两个指针first和last分别指向链表的头和尾，而是只用一个header指针指向双向链表的头，链表头的before指针指向链表的尾
LinkedHashSet
- 是对LinkedHashMap的简单包装（LinkedHashSet里面有一个LinkedHashMap,适配器模式），对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法
PriorityQueue
- 优先队列，实现了Queue接口，不允许放入null元素
- 能保证每次取出的元素都是队列中权值最小的，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）
- 底层是通过数组实现的最小值堆（完全二叉树）
- 取出堆顶数据但不删除时间复杂度O(1),其他插入、删除等操作时间复杂度O(logN)
WeakHashMap
存放的是对象的弱引用，因此WeakHashMap里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法。
适用于需要缓存的场景：对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误
将一对key, value放入到 WeakHashMap 里并不能避免该key值被GC回收，除非在 WeakHashMap 之外还有对该key的强引用。
没有WeekHashSet，不过Java Collections工具类给出了解决方案，Collections.newSetFromMap(Map<E,Boolean> map)方法可以将任何 Map包装成一个Set：
1
2
3// 将WeakHashMap包装成一个Set
Set<Object> weakHashSet = Collections.newSetFromMap(
new WeakHashMap<Object, Boolean>());