HashMap类简介

1 基本定义

数据结构

数据结构	数组	链表	红黑树
用途	存储键值对。数组下标为键的哈希值	解决哈希冲突	解决哈希冲突

定义参数

参数	initialCapacity	loadFactor
用途	用于定义数组容量，但数组是延迟初始化的。如果不是2的整数幂，会适当扩大。	负载因子，默认0.75。用于定义扩容阈值threshold。

基本特性
HashMap中允许null值和null键。null键对应着哈希值0，即数组的下表0。

HashMap是不保证对象的放入顺序的。

基本操作get和`put的时间性能基本为（如果不考虑哈希冲突的情况下）。

---

2 基本操作

读
判断hash/key，key值是否相等，hash值是否相等
判断是否是TreeNode，如果是从根节点二分查找(**问题TreeNode.find的最后的if else)

写
判断table是否存在
判断节点是否存在
如果是Tree节点，执行RB插入；
如果不是Tree节点，执行链表插入，如果大于TREEIFY_THRESHOLD，则树化。

扩容
计算新容量和新扩容阈值
拷贝

1. 如果是桶中是单个节点，重新hash到新表中。
2. 如果是树节点，遍历树切分为低于和高于旧阈值的两个链表，然后进行分别判断是否进行树化。
3. 如果是链表，遍历树切分为低于和高于旧阈值的两个链表。

树和链表转换
保持节点相对顺序。
使用类和哈希值进行比较。

---

3 哈希算法

在哈希值随机且扩容阈值为默认值0.75的情况下，哈希表每个桶的频率遵循的泊松分布。由于扩容时粒度较大，进而导致泊松分布的方差也很大。如果忽略方差的因素，哈希表桶列表长度为的概率为。第一批值如下：

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

哈希算法

• 直接寻址法（Identity hash function）
• 识字分析法
• 平方取中法
• 折叠法
• 随机数法
• 除留取余法

冲突解决方法

• 开放定址法（线性探测、二次/平方探测、双散列探测）
• 拉链法
• 再哈希
• 公共溢出区

参考资料

1. java-hashmap-tail-traversing
2. Hash function
3. Consistent hashing
4. HashMap的死循环