记录哈希表的底层原理探索

关于 HashMap

HashMap 是什么？

HashMap 是基于哈希表的数据结构，用于存储键值对（key-value）

特点：键唯一，值可以重复，允许一个 null 键，多个 null 值

核心点：将键的哈希值映射到数组索引位置，利用数组+链表（Java1.8 之后为数组+链表+红黑树）来处理哈希冲突

哈希冲突是什么？怎么解决？

哈希冲突：当两个不同的数经过哈希函数计算后得到了同一个结果，即他们会被映射到哈希表的同一个位置时，即称为发生了哈希冲突。

常用的解决方法

拉链法

使用链表或者其他数据结构来存储哈希冲突的键值对，将它们链接在同一个哈希桶中。

把所有同义词存储在一个链表中

假设现在有一个哈希函数为H(key)=key%13

当发生哈希冲突的时候，会将新的键值对添加到链表中，当需要查找该值的时候，会先通过哈希函数找到桶，然后遍历链表找到该值

开放定址法

在哈希表中寻找另一个位置（哈希桶）存放哈希键值对，而不是存放在链表中

常见的策略有：线性探测、平方探测、双重三列、伪随机序列

公式：

参数介绍：

• H_i：发生第 i 次冲突的散列地址
• H(key)：初始散列地址
• d_i：偏移量
• m：散列表的长度

线性探测：

• 逐一检查下一个哈希桶（H(key)++），直到找到一个空桶为止
• 在线性探测d_i相当于一个等差数列，d_i= 0,1,2,3,4….,m-1

平方探测：

利用平方探测公式逐渐增加偏移量检查下一个哈希桶，直到找到一个空桶为止，公式为：

例如

双散列表：

公式：

• 当第一个哈希函数发生冲突的时候，就会使用第二个哈希函数来寻找空的哈希桶，如此反复，直到找到空的哈希桶
• 偏移量

哈希扩容

HashMap中的扩容是基于负载因子（load factor）决定的，散列表的平均查找长度依赖于负载因子a，而不是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…

参考文章： 说说Java中HashMap的原理？ 一篇博客让你认识哈希冲突和解决方法