哈希表
中等 约 40 分钟
你将构建什么
一个 HashTable 类,含 set、get、delete 和 keys 方法,使用简单哈希函数并通过分离链处理冲突。
学习目标
- 实现将字符串键映射到桶索引的哈希函数
- 通过分离链(每桶一个数组)处理冲突
- 提供 get/set/delete/keys 操作
- 理解哈希表为何能实现 O(1) 平均查找
前置要求
- 对象与属性访问
- 数组与数组方法
- 字符串方法(charCodeAt)
步骤
- 1
设计桶数组
哈希表是一个桶数组。每个桶是 [key, value] 对的数组。选定固定容量(如 53),将所有桶初始化为空数组。
代码class HashTable { constructor(capacity = 53) { this.capacity = capacity; this.buckets = Array.from({ length: capacity }, () => []); } }预期结果
一个含 53 个空桶的 HashTable。
- 2
编写哈希函数
实现将字符串键转换为桶索引的哈希函数。常见做法:累加字符码,乘以一个质数,再对容量取模。
代码_hash(key) { const PRIME = 31; let total = 0; for (let i = 0; i < Math.min(key.length, 100); i++) { total = (total * PRIME + key.charCodeAt(i)) % this.capacity; } return total; }预期结果
_hash('name') 返回 [0, capacity) 范围内的数字。
提示
使用质数乘数可分散键,减少冲突。
- 3
实现带冲突处理的 set
set 时先哈希键找到桶,再检查桶中是否已存在该键。若存在则更新值,否则压入新的 [key, value] 对。
提示
遍历桶数组,比较每个 pair 的第一个元素与键。
- 4
实现 get 和 delete
get 哈希键、遍历桶并返回匹配值(或 undefined)。delete 找到并移除匹配对。两者都依赖相同的桶遍历逻辑。
提示
对桶使用 array.findIndex,比较 pair[0] 与键。
- 5
测试冲突场景
插入若干键值对,检索它们,删除一个,确认其余完好。验证哈希到同一桶的键仍能正常工作(冲突处理)。
代码const ht = new HashTable(); ht.set('name', 'Alice'); ht.set('age', 30); ht.set('city', 'Beijing'); console.log(ht.get('name')); // Alice console.log(ht.get('age')); // 30 ht.delete('age'); console.log(ht.get('age')); // undefined预期结果
get 依次返回 Alice、30,删除后返回 undefined。
自己动手试试
起始代码
class HashTable {
constructor(capacity = 53) { /* TODO */ }
_hash(key) { /* TODO */ }
set(key, value) { /* TODO */ }
get(key) { /* TODO */ }
delete(key) { /* TODO */ }
}解决方案代码
class HashTable {
constructor(c = 53) { this.capacity = c; this.buckets = Array.from({length:c}, () => []); }
_hash(k) { let t = 0; for (let i = 0; i < Math.min(k.length,100); i++) t = (t*31 + k.charCodeAt(i)) % this.capacity; return t; }
set(k, v) { const i = this._hash(k); const b = this.buckets[i]; const ex = b.find(p => p[0] === k); if (ex) ex[1] = v; else b.push([k, v]); }
get(k) { const b = this.buckets[this._hash(k)]; const p = b.find(x => x[0] === k); return p ? p[1] : undefined; }
delete(k) { const b = this.buckets[this._hash(k)]; const i = b.findIndex(p => p[0] === k); if (i !== -1) b.splice(i, 1); }
}你学到了什么
你构建了支撑 JavaScript 对象和 Map 的数据结构——并看到哈希函数加冲突处理如何实现近似 O(1) 查找。
相关资源
相关术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
- 哈希表
O(1) 平均查找的键值存储。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。