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，则树化。
扩容
计算新容量和新扩容阈值
拷贝
- 如果是桶中是单个节点，重新hash到新表中。
- 如果是树节点，遍历树切分为低于和高于旧阈值的两个链表，然后进行分别判断是否进行树化。
- 如果是链表，遍历树切分为低于和高于旧阈值的两个链表。
树和链表转换
保持节点相对顺序。
使用类和哈希值进行比较。
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）
- 识字分析法
- 平方取中法
- 折叠法
- 随机数法
- 除留取余法
冲突解决方法
- 开放定址法（线性探测、二次/平方探测、双散列探测）
- 拉链法
- 再哈希
- 公共溢出区
