5. 哈希表（Hash Table）

问题：需要通过键快速查找值，不想遍历整个集合。

核心：用哈希函数把键映射到数组下标，直接定位元素。冲突时用链表或开放寻址解决。

特点

键值对存储，键唯一
哈希函数将键映射到数组索引
平均 O(1) 的查找、插入、删除

优点

平均 O(1) 查找/插入/删除，极快
键可以是多种类型（字符串、数字等）
灵活，适合缓存、计数、去重

缺点

哈希冲突不可避免，最坏 O(n)
无序（大多数实现不保证顺序）
内存开销大（需要预留空间降低冲突率）
哈希函数质量影响性能

// 简易哈希表实现（链地址法）
class HashTable {
  #size = 53;
  #buckets = Array.from({ length: this.#size }, () => []);

  #hash(key) {
    let h = 0;
    for (const ch of String(key)) {
      h = (h * 31 + ch.charCodeAt(0)) % this.#size;
    }
    return h;
  }

  set(key, val) {
    const i = this.#hash(key);
    const pair = this.#buckets[i].find(p => p[0] === key);
    if (pair) pair[1] = val;
    else this.#buckets[i].push([key, val]);
  }

  get(key) {
    const pair = this.#buckets[this.#hash(key)].find(p => p[0] === key);
    return pair?.[1];
  }

  has(key) {
    return this.get(key) !== undefined;
  }
}

const table = new HashTable();
table.set('name', '小明');
table.set('age', 25);
console.log(table.get('name')); // 小明
console.log(table.has('age'));  // true

// 实际开发直接用 Map
const m = new Map();
m.set('key', 'value');
console.log(m.get('key')); // value

package hashtable

// 实际开发直接用 map
func Example() map[string]int {
    m := map[string]int{
        "apple":  3,
        "banana": 5,
    }

    // O(1) 平均查找
    v, ok := m["apple"]
    _ = v  // 3
    _ = ok // true

    // O(1) 平均插入
    m["cherry"] = 2

    // O(1) 平均删除
    delete(m, "banana")

    return m
}

// 判断键是否存在
func Contains(m map[string]int, key string) bool {
    _, ok := m[key]
    return ok
}

JS 的 Object 和 Map、Go 的 map、Python 的 dict、Java 的 HashMap 都是哈希表。