HashMap、HashSet、HashTable

HashMap

• 特点：使用了数组＋链表＋红黑树实现，Node数组为table，使用（table.length - 1) & hashcode（key）得到Node数组下标
• 初始容量：new出来后为空（空参），在添加了第一个元素后，自动扩容到16
• 最大容量：2^30
• 默认负载因子：0.75
• 链表转化树的默认阈值：链表长度大于8（至少为8），且表当前的容量不少于64
• 树转化链表的默认阈值：6（最多为6）
• 转化为树时，一个哈希桶的最小容量：4*链表转化树的默认阈值 容量默认为64
• 自动扩容机制（桶数量）：当当前实际容量大于（负载因子*当前最大容量时）进行自动扩容，扩容到原来的2倍
• 哈希桶的特殊转化机制：当桶中的数量大于链表转化树的阈值，则桶中的链表转化红黑树，当桶中的数量小于树转化链表的阈值则从树退化成链表

---

HashSet

• 特点：背后依赖于HashMap进行实现，参数除了序列化ID，有HashMap和PRESENT（private static final Object）
• 去重方式：依赖hashmap中key唯一的特点，进行去重，通过map.put(e, PRESENT)的方式进行添加（PRESENT的hash值在同一个HashSet是唯一的）

---

HashTable

• 特点：

  1. 使用数组＋链表的实现方式，解决哈希冲突的方法为链地址法，且不会转化为红黑树，性能较hashmap来说比较差；

  2. 各种对元素进行操作或者查询方法使用了synchronized同步锁，保证了线程安全，但是导致性能较差；

  3. 下标直接通过hashcode % tab.length 进行计算，可能会导致分布不够均匀，进一步影响性能。

• 初始容量：11

• 最大容量：Integer.MAX_VALUE - 8

• 默认负载因子：0.75

• 自动扩容机制：当当前实际容量大于（负载因子*当前最大容量时）进行自动扩容，扩容到原来的2倍