哈希表深入
理解哈希函数、冲突解决、装载因子和重哈希策略。
你将学到
- 哈希函数性质:均匀分布、速度
- 冲突解决:链地址法与开放寻址法
- 装载因子和何时重哈希
- 加密哈希与非加密哈希
概念讲解
哈希表深入
哈希表使用哈希函数将键映射到值,给出 O(1) 平均查找、插入和删除。它是现代编程的主力——JavaScript 对象、Python 字典、Java HashMap 底层都是哈希表。
哈希函数
好的哈希函数有两个性质:均匀分布(键均匀散布到桶中)和速度(计算快)。对字符串,常用多项式滚动哈希:hash(s) = (s[0]*p^0 + s[1]*p^1 + ...) mod m。
冲突解决
当两个键哈希到同一桶时,发生冲突。链地址法:每个桶持有条目的链表。简单,容忍高装载因子,但不缓存友好。开放寻址法:冲突时探测下一个桶。缓存友好但对聚集敏感。
装载因子
装载因子 alpha = n/m(条目数/桶数)。随 alpha 增长,冲突增加。大多数实现在 alpha 超过阈值(通常 0.75)时重哈希。重哈希为 O(n) 但罕见,因此摊还成本为 O(1)。
加密与非加密哈希
非加密哈希(FNV、MurmurHash、xxHash)快但不抗冲突。加密哈希(SHA-256)抗此攻击但更慢。哈希表用非加密;完整性和安全用加密。
示例代码
class HashTable {
constructor(size = 16) { this.size = size; this.buckets = Array.from({length: size}, () => []); this.count = 0; }
_hash(key) { let h = 0; const s = String(key); for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0; return h % this.size; }
set(key, value) {
const idx = this._hash(key); const bucket = this.buckets[idx];
for (const e of bucket) { if (e[0] === key) { e[1] = value; return; } }
bucket.push([key, value]); this.count++;
if (this.count / this.size > 0.75) this._rehash();
}
get(key) { const idx = this._hash(key); for (const e of this.buckets[idx]) { if (e[0] === key) return e[1]; } return undefined; }
_rehash() { const old = this.buckets; this.size *= 2; this.buckets = Array.from({length: this.size}, () => []); this.count = 0; for (const b of old) for (const [k, v] of b) this.set(k, v); }
}
const ht = new HashTable();
ht.set('name', 'Ada'); ht.set('age', 36); ht.set('role', 'admin');
console.log(ht.get('name'), ht.get('age'), ht.get('role'));
哈希函数使用基 31 的多项式滚动。链地址法将冲突存储在桶数组中。当装载因子超过 0.75 时,_rehash 将桶数翻倍。
动手试一试
- Hash Generator
观察哈希函数如何分布输入——哈希表性能的基础。
常见错误
错误写法
使用非均匀哈希函数,导致所有键聚集在一个桶中。
正确做法
坏的哈希函数破坏 O(1) 性能。测试分布:哈希多个键并检查桶占用大致均匀。
错误写法
装载因子增长时不重哈希。
正确做法
不重哈希,冲突链变长,性能退化为 O(n)。设置装载因子阈值并在超过时扩容。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。