题解：P11615 【模板】哈希表

stripe_python · 2025-01-30 21:52:15 · 题解

第一次写【模板】开头的题解。

本文的代码基于这个板子写：

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

namespace FastIO {
#ifndef SPN_LOCAL
    const int SZ = 1 << 18; char *p1, *p2, buf[SZ];
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SZ, stdin), p1 == p2) ? EOF : *p1++)
#endif
    inline void skip() {for (char ch = getchar(); ch == ' ' || ch == '\n' || ch == '\t'; ch = getchar());}

    int t; char ch;
    template <typename T> inline void read(T& x) {x = 0, t = 1, ch = getchar(); for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') t = -1; for (; '0' <= ch && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); x *= t;}
    inline void read(char& x) {skip(), x = getchar();}
    template <typename T, typename... Args> inline void read(T& t, Args&... args) {read(t); read(args...);}
    template <typename It> inline void read(const It& begin, const It& end) {for (It it = begin; it != end; it++) read(*it);}
} using namespace FastIO;

using uint64 = unsigned long long;

uint64 x, y;
const int M = 5000011;

struct Hash {
    map<uint64, uint64> a[M];

    int h(uint64 x) {return x % M;}

    uint64 get(uint64 x);
    void set(uint64 x, uint64 y);
} mp;

signed main() {
    int q; read(q);
    uint64 res = 0;
    for (int i = 1; i <= q; i++) {
        read(x, y);
        res += i * mp.get(x);
        mp.set(x, y);
    }
    cout << res;
    return 0;
}

思路

构造一个特征函数 h(x)，把 x 映射到 h(x) 上。OI 内，通常采用 h(x) = x \bmod M 的方法，其中 M 通常取质数。

但是总会出现 a \ne b 而 h(a) = h(b) 的情况，这种情况称作哈希冲突。下面的方法就是处理哈希冲突的方法。

拉链法

用一个链表把冲突的键值对拉在一起。写过链式前向星应该很好理解代码。

struct Hash {
    struct node {
        int next;
        uint64 x, y;
    } edge[M];
    int tot = 0, head[M];

    int h(uint64 x) {return x % M;}

    uint64 get(uint64 x) {
        for (int j = head[h(x)]; j != 0; j = edge[j].next) {
            if (edge[j].x == x) return edge[j].y;
        }
        return 0;
    }
    void set(uint64 x, uint64 y) {
        for (int j = head[h(x)]; j != 0; j = edge[j].next) {
            if (edge[j].x == x) return edge[j].y = y, void();
        }
        edge[++tot].next = head[h(x)], edge[tot].x = x, edge[tot].y = y, head[h(x)] = tot;
    }
} mp;

拉链法 + 平衡树

使用 std::map 实现的红黑树替代链表，代码较短，但是常数较大。

struct Hash {
    map<uint64, uint64> a[M];

    int h(uint64 x) {return x % M;}

    uint64 get(uint64 x) {
        return a[h(x)][x];
    }
    void set(uint64 x, uint64 y) {
        a[h(x)][x] = y;
    }
} mp;

拉链法 + vector

使用 vector 替代链表。当然用 list 也可以。

用 deque？MLE 警告！

struct Hash {
    vector<pair<uint64, uint64>> a[M];

    int h(uint64 x) {return x % M;}

    uint64 get(uint64 x) {
        for (const auto& i : a[h(x)]) {
            if (i.first == x) return i.second;
        }
        return 0;
    }
    void set(uint64 x, uint64 y) {
        for (auto& i : a[h(x)]) {
            if (i.first == x) return i.second = y, void();
        }
        a[h(x)].emplace_back(x, y);
    }
} mp;

闭散列法

直接把所有记录存下来，如果冲突就接着找。

struct Hash {
    pair<uint64, uint64> a[M];

    int h(uint64 x) {return x % M;}

    uint64 get(uint64 x) {
        int i = h(x), j = 1; 
        for (; a[i].first != x && a[i].second != 0; j++) i = (i + j) % M;   
        a[i].first = x;
        return a[i].second;
    }
    void set(uint64 x, uint64 y) {
        int i = h(x), j = 1; 
        for (; a[i].first != x && a[i].second != 0; j++) i = (i + j) % M;   
        a[i].first = x, a[i].second = y;
    }
} mp;

二次探测法

一个一个向后找稍有些慢，我们可以一次跳过 j^2 个位置。

struct Hash {
    pair<uint64, uint64> a[M];

    int h(uint64 x) {return x % M;}

    uint64 get(uint64 x) {
        int i = h(x), j = 1; 
        for (; a[i].first != x && a[i].second != 0; j++) i = (i + j * j) % M;   
        a[i].first = x;
        return a[i].second;
    }
    void set(uint64 x, uint64 y) {
        int i = h(x), j = 1; 
        for (; a[i].first != x && a[i].second != 0; j++) i = (i + j * j) % M;   
        a[i].first = x, a[i].second = y;
    }
} mp;

性能测试

最后附上本文所有方法在本题的用时。没有任何刻意卡常。

拉链法比较？存图方法比较！

总结：数据规模较大时，闭散列法通常比拉链法快一些。如果需要手写哈希表卡常，可以使用闭散列法 + 二次探测。