关于 HashMap
HashMap 是什么？
HashMap 是基于哈希表的数据结构，用于存储键值对（key-value）
特点：键唯一，值可以重复，允许一个 null 键，多个 null 值
核心点：将键的哈希值映射到数组索引位置，利用数组+链表（Java1.8 之后为数组+链表+红黑树）来处理哈希冲突
哈希冲突是什么？怎么解决？
哈希冲突：当两个不同的数经过哈希函数计算后得到了同一个结果，即他们会被映射到哈希表的同一个位置时，即称为发生了哈希冲突。
常用的解决方法
拉链法
使用链表或者其他数据结构来存储哈希冲突的键值对，将它们链接在同一个哈希桶中。
把所有同义词存储在一个链表中
假设现在有一个哈希函数为H(key)=key%13
当发生哈希冲突的时候，会将新的键值对添加到链表中，当需要查找该值的时候，会先通过哈希函数找到桶，然后遍历链表找到该值
开放定址法
在哈希表中寻找另一个位置（哈希桶）存放哈希键值对，而不是存放在链表中
常见的策略有：线性探测、平方探测、双重三列、伪随机序列
公式：
$$ H_i=(H(key)+d_i) \% m $$
参数介绍：
- H_i：发生第 i 次冲突的散列地址
- H(key)：初始散列地址
- d_i：偏移量
- m：散列表的长度
线性探测：
- 逐一检查下一个哈希桶（H(key)++），直到找到一个空桶为止
- 在线性探测
d_i相当于一个等差数列，d_i= 0,1,2,3,4….,m-1
平方探测：
利用平方探测公式逐渐增加偏移量检查下一个哈希桶，直到找到一个空桶为止，公式为：
$$ d_i=i^2,-(i^2) $$
例如
$$ d_i= 0^2, 1^2, -1^2, 2^2, -2^2,….,k^2, -k^2; k <= m/2 $$
双散列表：
公式：
$$ H_i=(hash1(key) + i*hash2(key)) \% m $$
$$ hash1(key)=key\% m $$
$$ hash2(Key)=PRIME - (key\%PRIME) $$
当第一个哈希函数发生冲突的时候，就会使用第二个哈希函数来寻找空的哈希桶，如此反复，直到找到空的哈希桶
偏移量
$$ d_i=i*hash2(key) $$
哈希扩容
HashMap中的扩容是基于负载因子（load factor）决定的，散列表的平均查找长度依赖于负载因子a，而不是n或者m
$$ 负载因子 a = \frac{表中记录数n}{散列长度m} $$
负载因子a默认是0.75，也就是当表中记录n（已存储元素数量）超过散列长度的 75%，散列表就会发生扩容
当发生扩容的时候，HashMap的容量会扩大为当前的 2 倍。扩容时，HashMap需要将所有元素重新分配到新的哈希桶，这个过程为rehashing
HashMap 的红黑树优化
首先看hashmap中的一个常量值：
TREEIFY_THRESHOLD
使用树而不是列表来表示一个桶的桶计数阈值。当向一个至少包含此数量节点的桶中添加元素时，这些桶会被转换为树。该值必须大于2，且至少应为8，以便与树删除操作中的假设相一致，即收缩后应重新转换为普通桶。
UNTREEIFY_THRESHOLD
在调整大小操作期间将（拆分）桶标记为非树状化的桶计数阈值。该值应小于TREEIFY_THRESHOLD，且最多为6，以便与移除操作下的收缩检测相协调。
MIN_TREEIFY_CAPACITY
可以实施树化操作的最低表容量。否则，如果桶中节点过多，则会对表进行重新调整大小。应至少设置为4 * TREEIFY_THRESHOLD，以避免在重新调整大小和树化阈值之间产生冲突。
源码：
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
转换为红黑树的时机
当HashMap的链表长度 >= 8 且数组的长度>=64的时候会树化，即链表转换成红黑树
在源码的putVal(...)函数中的树化判定条件
TREEIFY_THRESHOLD的默认阈值，因为负载因子是0.75，而 8 * 0.75 = 6，也就是当表中记录数超过6并且散列表的长度为 8 的时候就会发生树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
转换为链表的时机
当哈希表的长度为 6 的时候，就会退化为链表
在源码中的split(...)函数中的红黑树退化为链表的判定条件
untreeify()为转链表化函数
end…
参考文章：
