Skip to content

哈希表

一句话解释

哈希表存储键值对,并用哈希函数计算索引,从而实现 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"

哈希函数对字符码求和再对桶数取模。冲突用链地址法处理——每个桶存放一组键值对。

相关术语

相关资源

相关课程

解读错误信息

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

查看错误

← 返回术语表