哈希表原理与实现

核心思想

key ──→ [hash function] ──→ index ──→ O(1) 存取

关键设计：
1. 哈希函数：把 key 均匀映射到 [0, capacity)
2. 冲突解决：两个不同 key 映射到同一 index 怎么办

哈希函数

// 字符串哈希 — DJB2（经典简单高效）
size_t hash(const string &s) {
    size_t h = 5381;
    for (char c : s) h = ((h << 5) + h) + c;  // h * 33 + c
    return h;
}

// 整数哈希 — 避免简单取模的低位冲突
size_t hash(int key, size_t capacity) {
    // 乘法哈希：用无理数打散
    const double A = 0.6180339887;  // (√5-1)/2
    return size_t(capacity * fmod(key * A, 1.0));
}

冲突解决

链地址法（std::unordered_map 采用）

template <typename K, typename V>
class ChainedHashMap {
    vector<list<pair<K, V>>> buckets;
    size_t size_ = 0;
    const double MAX_LOAD = 0.75;

    size_t index(const K &key) const {
        return hash<K>{}(key) % buckets.size();
    }

public:
    ChainedHashMap(size_t cap = 16) : buckets(cap) {}

    void put(const K &key, const V &val) {
        auto &chain = buckets[index(key)];
        for (auto &[k, v] : chain) {
            if (k == key) { v = val; return; }
        }
        chain.emplace_back(key, val);
        if (++size_ > buckets.size() * MAX_LOAD) rehash();
    }

    V *get(const K &key) {
        for (auto &[k, v] : buckets[index(key)])
            if (k == key) return &v;
        return nullptr;
    }
};

开放寻址法

// 线性探测: index, index+1, index+2 ...
// 问题：主聚类（primary clustering）

// 二次探测: index + 1², index + 2², ...
// 问题：次聚类（secondary clustering）

// 双重哈希: h1(key) + i * h2(key)
// 优点：无聚类，但需要两个哈希函数

负载因子与 rehash

void rehash() {
    auto oldBuckets = move(buckets);
    buckets.resize(oldBuckets.size() * 2);
    size_ = 0;
    for (auto &chain : oldBuckets)
        for (auto &[k, v] : chain)
            put(k, v);
}

负载因子	含义	行为
<0.5	稀疏	查找快，但浪费空间
0.75	平衡点	std::unordered_map 默认扩容阈值
>1.0	链地址可容忍	链表变长，退化为 O(n)

复杂度分析

操作	平均	最坏
插入	O(1)	O(n)
查找	O(1)	O(n)
删除	O(1)	O(n)

最坏情况：所有 key 冲突到同一个桶 → 退化成链表。防止方法：好的哈希函数 + 低负载因子。

std::unordered_map 使用

unordered_map<string, int> m;

// 插入
m["alice"] = 25;
m.insert({"bob", 30});
m.try_emplace("carol", 28);  // C++17，已存在不覆盖

// 查找
if (m.count("alice")) { /* 存在 */ }
auto it = m.find("alice");
if (it != m.end()) cout << it->second;

// 删除
m.erase("alice");

// 预留空间（避免 rehash）
m.reserve(1000);  // 至少 1000 个桶

// 遍历（无序！）
for (auto &[k, v] : m) cout << k << ": " << v;

自定义哈希

struct Point { int x, y; };

struct PointHash {
    size_t operator()(const Point &p) const {
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};
struct PointEq {
    bool operator()(const Point &a, const Point &b) const {
        return a.x == b.x && a.y == b.y;
    }
};

unordered_map<Point, string, PointHash, PointEq> grid;