当前位置：首页 > news >正文

哈希表的底层原理

news 2025/10/28 2:16:21

关于 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,-(i2)
$$
例如
$$
d_i= 0^2, 1^2, -1^2, 2^2, -2^2,….,k2, -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);}
}