目录
集合
List
有序
可重复
有索引
ArrayList
数组
线程不安全
初始容量：10
扩容：1.5倍
结尾会预留空间
修改和查询快
Vector
线程安全，synchronized
扩容：2倍
性能不高
LinkedList
双向循环链表（1.7-）
双向链表（1.7+）
增删快
实现了Deque接口，可当作队列使用
CopyOnWriteArrayList
线程安全的ArrayList
ConcurrentLinkedQueue
线程安全的LinkedList
Set
无序
不可重复
无索引
HashSet
底层是HashMap
添加时，首先判断hashCode，不存在则添加；存在则调equals，false则添加，true则不添加
补充：说说 == 与 equals
Object：两者均比较地址
String：==比较地址，重写了equals，比较内容
TreeSet
默认升序
底层是TreeMap
存自定义对象切记实现Comparator接口，并重写compare方法规定排序方式
CopyOnWriteArraySet
线程安全的HashSet
Map
key -> value
Key无序 + 不可重复
value无序 + 可重复
HashMap
无序
若无初值，容量16
扩容因子：0.75，扩为2n
若给定初值，且达到阈值，扩到初值的2的幂次方
线程不安全
key可为null（只能一个），value可为null
jdk版本对比
1.8-
数组 + 链表
头插（并发环境扩容造成循环依赖）
4次扰动5次异或
拉链法
1.8+
数组 + 链表/红黑树
注：当数组<64时，不转红黑树，而是先扩容
节点>8，链表 -> 红黑树
节点<=6，红黑树 -> 链表
尾插
1次扰动1次异或
时间复杂度
定位数组下标，hash，时间O(1)
若遍历链表（1.8-），总时间O(n)
若遍历红黑树（1.8+），总时间O(logn)
存储过程
key -> hashcode -> hash -> index
闲话：多想想put和get的完整流程
散列表解决hash冲突
1.开放地址法
a.线性探测：冲突了一步一步找最近的位置插入
b.二次探测：类似a，区别在步长为当前位置的2次方
c.双重散列：冲突后hash，直到不冲突
2.拉链法
HashTable
数组 + 链表
若无初值，容量11
扩容因子：0.75，扩为2n+1
线程安全，synchronized
key和value均不为null
性能不高
TreeMap
底层是红黑树
默认按 key 升序
自定义排序见TreeSet
ConcurrentHashMap
线程安全的HashMap
1.7
分段（segment）数组 + HashEntry数组 + 链表
分段锁
1.8
组成同1.8 HashMap
volatile + synchronized + CAS
锁节点
Queue
PriorityQueue
底层是堆，默认小根堆
可解决top k问题
Iterator迭代器
遍历集合 + 不暴露细节 + 能抛并发修改异常
String
1.8底层用 char[]
1.9底层用 byte[]
final 不可变性
