Skip to content

哈希表

中等 约 40 分钟

你将构建什么

一个 HashTable 类,含 set、get、delete 和 keys 方法,使用简单哈希函数并通过分离链处理冲突。

学习目标

  • 实现将字符串键映射到桶索引的哈希函数
  • 通过分离链(每桶一个数组)处理冲突
  • 提供 get/set/delete/keys 操作
  • 理解哈希表为何能实现 O(1) 平均查找

前置要求

  • 对象与属性访问
  • 数组与数组方法
  • 字符串方法(charCodeAt)

步骤

  1. 1

    设计桶数组

    哈希表是一个桶数组。每个桶是 [key, value] 对的数组。选定固定容量(如 53),将所有桶初始化为空数组。

    代码
    class HashTable {
      constructor(capacity = 53) {
        this.capacity = capacity;
        this.buckets = Array.from({ length: capacity }, () => []);
      }
    }

    预期结果

    一个含 53 个空桶的 HashTable。

  2. 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. 3

    实现带冲突处理的 set

    set 时先哈希键找到桶,再检查桶中是否已存在该键。若存在则更新值,否则压入新的 [key, value] 对。

  4. 4

    实现 get 和 delete

    get 哈希键、遍历桶并返回匹配值(或 undefined)。delete 找到并移除匹配对。两者都依赖相同的桶遍历逻辑。

  5. 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。

自己动手试试

你学到了什么

你构建了支撑 JavaScript 对象和 Map 的数据结构——并看到哈希函数加冲突处理如何实现近似 O(1) 查找。

相关资源

相关课程

  • 对象

    对象底层就是哈希表。

  • 数组

    桶是键值对数组。

相关术语

相关术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

解读错误信息

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

查看错误

← 返回主题