哈希表

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

// ========== 1. 开放寻址法 ==========
const int null_val = 0x3f3f3f3f;
int h[N];  // 哈希表

void hash_init() {
    memset(h, 0x3f, sizeof(h));  // 初始化为"空"
}

int hash_find(int x) {
    int k = (x % N + N) % N;  // 哈希函数，处理负数
    while (h[k] != null_val && h[k] != x) {
        k++;
        if (k == N) k = 0;  // 循环
    }
    return k;  // 如果 h[k]==null_val 说明不存在，否则是 x 的位置
}

void hash_insert(int x) {
    int k = hash_find(x);
    if (h[k] == null_val) h[k] = x;
}

bool hash_contains(int x) {
    int k = hash_find(x);
    return h[k] != null_val;
}

// ========== 2. 拉链法（链地址法）==========
int h2[N], e[N], ne[N], idx = 0;

void chain_init() {
    memset(h2, -1, sizeof(h2));
}

void chain_insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h2[k];
    h2[k] = idx++;
}

bool chain_find(int x) {
    int k = (x % N + N) % N;
    for (int i = h2[k]; i != -1; i = ne[i]) {
        if (e[i] == x) return true;
    }
    return false;
}

// ========== 3. STL unordered_map / unordered_set ==========
void stl_hash_demo() {
    // 哈希映射（键值对）
    unordered_map<string, int> score;
    score["Alice"] = 95;
    score["Bob"] = 87;

    cout << score["Alice"] << endl;  // 95

    // 判断键是否存在
    if (score.count("Charlie")) {
        cout << score["Charlie"] << endl;
    }

    // 遍历
    for (auto &[name, s] : score) {
        cout << name << ": " << s << endl;
    }

    // 哈希集合（去重）
    unordered_set<int> seen;
    seen.insert(42);
    seen.insert(42);  // 重复插入无效
    cout << seen.count(42) << endl;  // 1
    cout << seen.size() << endl;     // 1

    // 统计每个数出现次数
    unordered_map<int, int> cnt;
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    for (int x : arr) cnt[x]++;
    for (auto &[val, c] : cnt) {
        cout << val << " 出现 " << c << " 次" << endl;
    }
}

// ========== 4. 字符串哈希 ==========
// 用于快速比较两个子串是否相同
typedef unsigned long long ULL;
const int BASE = 131;  // 哈希基数
ULL p[N], h_str[N];    // p[i] = BASE^i, h_str[i] = 前缀哈希

void str_hash_init(string &s) {
    int n = s.size();
    p[0] = 1;
    h_str[0] = 0;
    for (int i = 1; i <= n; i++) {
        h_str[i] = h_str[i-1] * BASE + s[i-1];
        p[i] = p[i-1] * BASE;
    }
}

// 获取子串 s[l..r] 的哈希值（1-indexed）
ULL get_hash(int l, int r) {
    return h_str[r] - h_str[l-1] * p[r-l+1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 数组哈希：判断元素是否存在
    hash_init();
    hash_insert(42);
    hash_insert(17);
    cout << hash_contains(42) << endl;  // 1
    cout << hash_contains(99) << endl;  // 0

    // 字符串哈希
    string s = "hello world";
    str_hash_init(s);
    // 比较子串是否相同
    cout << (get_hash(1, 3) == get_hash(7, 9) ? "相同" : "不同") << endl;

    return 0;
}

📖 要点说明

哈希表核心

• 哈希函数：将键映射到数组下标 h(x) = x % N
• 冲突：不同键映射到同一位置，必须处理
• 查找 O(1)：理想情况下常数时间

两种冲突处理

字符串哈希

• 将字符串映射为一个数字，快速比较子串是否相同
• 公式：hash(s[l..r]) = h[r] - h[l-1] * BASE^(r-l+1)
• 自然溢出取模（用 unsigned long long）

STL 选择

• unordered_map：需要键值对时使用
• unordered_set：只需要判断存在性时使用
• map/set：需要有序时使用（红黑树，O(log n)）

⚠️ 常见错误

• 哈希函数处理负数：(x % N + N) % N
• 开放寻址法数组要开到数据量的 2~3 倍
• 字符串哈希的 BASE 和 MOD 选择影响冲突率