集合 Collection
List有序可重复 Set无序不重复 Map为key-value
List
ArrayList
底层数据结构
基于动态数组实现支持随机访问
自动扩容
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容以满足添加数据的需求，每次进行扩容时会将老数组中的元素重新拷贝一份到新的数组中。每次数组容量的增长大约为其容量的1.5倍，这种代价是很高的，因此我们在实际使用时应尽量避免数组容量的扩张。
Fail-Fast机制：
ArrayList采用了快速失败的机制，通过记录modCount参数来实现。
说说什么是Fail-Fast机制：
Fail-Fast 机制是 Java 集合（Collection）中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件。
例如：当某一个线程 A 通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变了，那么线程 A 访问集合时，就会抛ConcurrentModificationException 异常，产生 fail-fast 事件。这里的操作主要是指 add、remove 和 clear，对集合元素个数进行修改。
解决办法：建议使用“java.util.concurrent 包下的类”去取代“java.util 包下的类”。
可以这么理解：在遍历之前，把 modCount 记下来 expectModCount，后面 expectModCount 去和 modCount 进行比较，如果不相等了，证明已并发了，被修改了，于是抛出 ConcurrentModificationException 异常。
Vector
和ArrayList类似但它是线程安全的
LinkedList
基于双向链表实现只能顺序访问但可以在列表中快速的插入和删除元素
底层数据结构
LinkedList底层通过双向链表实现
说说ArrayList和LinkedList的区别：
ArrayList
- 优点：实现了基于动态数组的数据结构。存储地址物理连续，查询效率比较高，随机读取速率比较高。
- 缺点：因为地址连续，要移动数据的时候比如插入删除的操作效率就会比较低。
LinkedList
- 优点：基于链表的数据结构存储地址逻辑上是连续的，但物理上并不是连续，所以开辟内存空间时不需要一个连续的内存地址。新增和删除操作效率比较高。LinkedList比较适用于头尾操作需要插入指定位置的场景。
- 缺点：因为LinkedList需要移动指针，查询效率比较低。
Stack & Queue
Queue 队列
Deque 双向队列
PriorityQueue 优先队列
Map
TreeMap
基于红黑树实现
HashMap
基于哈希表实现
底层数据结构
jdk1.7 底层: 数组+链表
jdk1.8 底层: 数组+链表+红黑树
初始为一个默认大小为16的数组，put操作的时候hash运算之后取模(位运算，直接面向二进制位)，存一个Object对象，存储为单链表，当单链表中的对象过多的时候(链表长度8个，数组长度64个)，时间复杂度为O(N)，查询较慢，将链表升级为红黑树，时间复杂度为O(log N)
红黑树的特征：
每个节点是黑色或者红色
根节点是黑色
每个叶子节点都是黑色
如果一个叶子节点是红色，那么其子节点必须都是黑色的
从一个节点到该节点的子孙节点上所有路径包含相同数目的黑节点
扩容
数组长度<64,链表长度>8
通过扩容将数组重新分配，从而提高查询性能
jdk1.7 :rehash
jdk1.8 :hash & 老数组长度
低位:保留原位
高位:原下标+扩容大小
HashMap的长度为什么是2的N次方呢？
为了能使HashMap存取数据的效率尽可能高，尽可能减少哈希值的碰撞，也就是说尽量将数据均匀分配，每个链表或者红黑树的长度尽量相等。
我们可能首先会取到想到%取模操作来实现。
取余操作中如果除数是2的幂次，则等价于与其除数减一的与(&)操作(也就是说hash % length == hash &(length - 1) 的前提是 length是2的n次方)。采用二进制位操作&相对于取余能够提高运算效率。
ConcurrentHashMap
ConcurrentHashMap支持线程安全并且效率更高，因为ConcurrentHashMap引入了分段锁。
ConcurrentHashMap 在 JDK 1.8 之前是采用分段锁来现实的 Segment + HashEntry，
Segment 数组大小默认是 16，2 的 n 次方；
JDK 1.8 之后，采用 Node + CAS + Synchronized
来保证并发安全进行实现。
LinkedHashMap
使用双向链表来维护元素的顺序顺序为插入的顺序或者最近最少使用(LRU)顺序
经典用法
可以轻松实现一个采取FIFO替换策略的缓存，具体说来，LinkedHashMap有一个子类方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest)，该方法的作用是告诉Map是否要删除“最老”的Entry，所谓最老就是当前Map中最早插入的Entry，如果该方法返回true，最老的那个元素就会被删除。在每次插入新元素之后LinkedHashMap会自动询问removeEldestEntry()是否要删除最老的元素。这样只需要在子类中重载该方法，当元素个数超过一定数量时让removeEldestEntry()返回true，就能够实现一个固定大小的FIFO策略的缓存。
底层数据结构
在HashMap的基础上，使用双向链表的形式将所有的NT连接起来为了保证元素的迭代顺序和插入的顺序相同
Set
TreeSet
基于红黑树实现，支持有序性操作但查找效率不如HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 由于呃link list需要移动指针所以查询的效率比较低则为 O(logN)。
HashSet
基于哈希表实现，支持快速查找，但不支持有序性操作。并且会导致元素插入顺序失序，也就是说遍历HashSet得到的结果是不确定的。
LinkedHashSet
具有HashSet的查找效率且内部使用双向链表来维护元素的插入顺序。
说说List,Set,Map三者的区别？
List： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
Set: 不允许重复的集合。不会有多个元素引用相同的对象。
Map: 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。
