哈希表（Hash Table）结构

核心特性

基于哈希函数实现键值映射，查询 / 增删 O (1)（理想情况）

核心概念：哈希函数（将键映射到数组索引）、冲突解决（拉链法 / 开放地址法）

前端关联：Object、Map 的底层实现本质是哈希表（Object 用拉链法解决冲突，Map 用平衡二叉搜索树优化有序性）

代码实现（拉链法解决冲突）

class HashTable {
  constructor(capacity = 16) {
    this.capacity = capacity; // 数组容量（2的幂次，便于哈希计算）
    this.buckets = new Array(capacity).fill(null).map(() => []); // 每个桶是一个链表（存储冲突的键值对）
    this.size = 0;
  }

  // 哈希函数（简单版：将键转为字符串，计算ASCII码之和，取模容量）
  _hash(key) {
    const strKey = String(key);
    let hash = 0;
    for (let i = 0; i < strKey.length; i++) {
      hash += strKey.charCodeAt(i);
    }
    return hash % this.capacity;
  }

  // 新增/修改
  set(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    // 查找是否已存在该键，存在则更新值
    for (let i = 0; i < bucket.length; i++) {
      const [k, v] = bucket[i];
      if (k === key) {
        bucket[i] = [key, value];
        return;
      }
    }

    // 不存在则添加到桶中
    bucket.push([key, value]);
    this.size++;

    // 扩容（负载因子>0.7时，避免冲突过多）
    if (this.size / this.capacity > 0.7) {
      this._resize();
    }
  }

  // 查找
  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    for (const [k, v] of bucket) {
      if (k === key) return v;
    }

    return undefined; // 未找到
  }

  // 删除
  delete(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    for (let i = 0; i < bucket.length; i++) {
      const [k] = bucket[i];
      if (k === key) {
        bucket.splice(i, 1);
        this.size--;
        return true;
      }
    }

    return false; // 未找到
  }

  // 扩容（容量翻倍，重新计算所有键的哈希值）
  _resize() {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
    this.size = 0;

    // 重新插入所有键值对
    for (const bucket of oldBuckets) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }
}

适用场景

常见数据查询：如缓存池（存储接口返回数据，键为请求 URL，值为响应数据）

字典映射：如中英文翻译（键为英文单词，值为中文释义）

计数统计：如统计字符串中字符出现次数（键为字符，值为次数）

注意

哈希函数的选择影响冲突率（好的哈希函数能均匀分布键）

负载因子（size/capacity）过大时需扩容（否则冲突增多，查询效率下降）