Skip to content

哈希表深入

理解哈希函数、冲突解决、装载因子和重哈希策略。

你将学到

  • 哈希函数性质:均匀分布、速度
  • 冲突解决:链地址法与开放寻址法
  • 装载因子和何时重哈希
  • 加密哈希与非加密哈希

概念讲解

哈希表深入

哈希表使用哈希函数将键映射到值,给出 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 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误