- HashSet和TreeSet 实质上是对Map的封装
- HashMap
- 数据结构是数组table+链表(Node<K,V>)\红黑树(TreeNode<K,V>)，初始容量为16，加载因子为0.75，每次扩容为原来的二倍
- put()方法放入键值对时，根据key的hash值确定index = table.length-1 & hash，然后按照链表或者红黑树的逻辑插入Node。table中的元素存储的是头结点
- Node<K,V> 是静态内部类，对Map.Entry内部接口的实现，有四个成员变量，hash是key和value的hash值的异或，key默认，value默认，还有一个Node next，说明是单向链表
- TreeNode<K,V> 是静态内部类，对LinkedHashMap.Entry静态内部类的实现，TreeNode有5个成员：parent，left，right，prev，是否是red，LinkedHashMap.Entry 有 before和after
- 扩容在当前键值对插入后判断的，当table大小超过 容量*装载因子 时，扩容
- 线程不安全的原因：
-- jdk1.7中扩容使用头部插入，是可能发生循环死锁，CPU可以达到100%；jdk1.8在扩容时使用尾部插入，不会发生死锁
-- put 方法可能会发生覆盖问题 - Entry<K,V> 主要方法有 getKey() getValue() 等
- ConcurrectHashMap
- key和value不可以是null值
- 线程安全的原因是在put、remove、resize等操作时会对当前 Node f加同步锁 synchronized(f)
- TreeMap
- 基于红黑树的对NavigableMap接口的实现
- 构造方法： TreeMap(Comparator<? super K> comparator)
- 挖坑：红黑树
- 挖坑：LinkedHashMap