Question

HashMap类简介

Answer 1

数据结构

定义参数

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

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

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

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

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

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

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

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

哈希算法

冲突解决方法