哈希表
一句话解释
哈希表存储键值对,并用哈希函数计算索引,从而实现 O(1) 平均查找。
用大白话说
哈希表(哈希映射)存储键值对,并用哈希函数把每个键转换成内部数组中的数值索引。这使你能在 O(1) 平均时间内按键存、找、删值——远快于在数组中逐元素搜索。哈希函数接收一个键(如字符串 "name")并返回一个整数索引。两个不同键可能哈希到同一索引——即冲突。哈希表用链地址法(每个索引处存一条目链表)或开放寻址法(探测下一个空位)处理冲突。好的哈希函数会均匀分布键以减少冲突。哈希表是 JavaScript 对象与 Map、Python dict、Java HashMap 以及数据库索引的基石。凡需按键快速查找、去重或计数频率时,它都是首选结构。
示例
javascript
// 简易哈希表,使用链地址法
class HashTable {
#buckets = Array.from({ length: 5 }, () => []);
#hash(key) {
let h = 0;
for (const ch of key) h += ch.charCodeAt(0);
return h % this.#buckets.length;
}
set(key, val) {
const i = this.#hash(key);
const bucket = this.#buckets[i];
const entry = bucket.find(e => e[0] === key);
if (entry) entry[1] = val; else bucket.push([key, val]);
}
get(key) {
const bucket = this.#buckets[this.#hash(key)];
return bucket.find(e => e[0] === key)?.[1];
}
}
const ht = new HashTable();
ht.set("name", "Ada"); ht.set("age", 36);
console.log(ht.get("name")); // "Ada"哈希函数对字符码求和再对桶数取模。冲突用链地址法处理——每个桶存放一组键值对。
相关术语
相关资源
相关课程
- 数据结构
学习哈希表与映射。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。