数值哈希函数构造与 冲突处理入门

// 写法一：布尔桶 —— 判断某个数是否出现过
const int MAXV = 10000005;
bool exist[MAXV];
exist[x] = true;                  // O(1) 标记
if (exist[y]) { /* ... */ }          // O(1) 查询

// 写法二：计数桶 —— 统计每个值出现次数
int cnt[MAXV];
cnt[x]++;                          // O(1) 累加
cout << cnt[y] << endl;              // O(1) 取值

// 值域含负数时加偏移
const int OFF = 1000000;
int cnt2[MAXV];
cnt2[x + OFF]++;

const int M = 100003;   // 表长取质数
const int EMPTY = -1;
long long key[M];

// 插入：找第一个空位（线性探测）
void insert(long long k) {
    int h = (k % M + M) % M;      // 处理负数取模
    while (key[h] != EMPTY && key[h] != k)
        h = (h + 1) % M;               // 往后找一格
    key[h] = k;
}

// 查询：沿同样的探测路径找
bool find(long long k) {
    int h = (k % M + M) % M;
    while (key[h] != EMPTY) {
        if (key[h] == k) return true;
        h = (h + 1) % M;
    }
    return false;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000001;
bool exist[MAXV];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        exist[x] = true;             // O(1) 标记，重复自动忽略
    }
    int cnt = 0;
    for (int v = 0; v < MAXV; v++)
        if (exist[v]) cnt++;
    cout << cnt << "\n";
    for (int v = 0; v < MAXV; v++) {
        if (!exist[v]) continue;
        cout << v;
        if (--cnt) cout << ' ';              // 最后不输出尾空格
    }
    cout << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int M = 100003;            // 质数表长
vector<long long> bucket[M];      // 每个桶挂一条链

int hashi(long long x) {
    return (int)((x % M + M) % M);   // 负数取模归一
}

void insertVal(long long x) {
    int h = hashi(x);
    for (long long v : bucket[h])
        if (v == x) return;             // 已存在则不重复插入
    bucket[h].push_back(x);
}

bool findVal(long long x) {
    int h = hashi(x);
    for (long long v : bucket[h])
        if (v == x) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m; cin >> m;
    while (m--) {
        int op; long long x;
        cin >> op >> x;
        if (op == 1) insertVal(x);
        else cout << (findVal(x) ? "Yes" : "No") << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int HMOD = 1000003;      // 哈希表长（质数）
int head[MAXN], nxt[MAXN], cntNode;
long long val[MAXN];
int num[MAXN];                     // 该键出现的次数

int hashi(long long x) { return (int)((x % HMOD + HMOD) % HMOD); }

int getCnt(long long x) {            // 查询 x 的出现次数
    int h = hashi(x);
    for (int i = head[h]; i; i = nxt[i])
        if (val[i] == x) return num[i];
    return 0;
}

void addCnt(long long x) {            // 把 x 的计数 +1
    int h = hashi(x);
    for (int i = head[h]; i; i = nxt[i])
        if (val[i] == x) { num[i]++; return; }
    val[++cntNode] = x; num[cntNode] = 1;
    nxt[cntNode] = head[h]; head[h] = cntNode;   // 头插法挂链
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; long long C;
    cin >> n >> C;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        ans += getCnt(x - C);       // 先查：x 前面有多少个 x - C
        addCnt(x);                  // 后加：把自己计入
    }
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int cnt[101];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        cnt[x]++;                       // O(1) 落桶
    }
    int kinds = 0;
    for (int v = 0; v <= 100; v++) if (cnt[v]) kinds++;
    cout << kinds << "\n";
    for (int v = 0; v <= 100; v++)
        if (cnt[v]) cout << v << " " << cnt[v] << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int M = 100003;
vector<long long> bucket[M];

int hashi(long long x) { return (int)((x % M + M) % M); }

bool has(long long x) {
    for (long long v : bucket[hashi(x)]) if (v == x) return true;
    return false;
}
void put(long long x) { bucket[hashi(x)].push_back(x); }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; long long T; cin >> n >> T;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        long long need = T - x;
        if (has(need)) {
            cout << min(x, need) << " " << max(x, need) << endl;
            return 0;
        }
        put(x);
    }
    cout << "No" << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int M = 2000003;              // 表长 ≈ 2 倍 n
int head[M], nxt[M], cntNode;
long long val[M];
int num[M];

int hashi(long long x) { return (int)((x % M + M) % M); }

int addAndGet(long long x) {
    int h = hashi(x);
    for (int i = head[h]; i; i = nxt[i])
        if (val[i] == x) return ++num[i];
    val[++cntNode] = x; num[cntNode] = 1;
    nxt[cntNode] = head[h]; head[h] = cntNode;
    return 1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    long long bestVal = 0; int bestCnt = 0;
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        int c = addAndGet(x);
        if (c > bestCnt || (c == bestCnt && x < bestVal)) {
            bestCnt = c; bestVal = x;       // 在线更新，并列取小
        }
    }
    cout << bestVal << " " << bestCnt << endl;
    return 0;
}

const int M = 2000003;              // 质数，约为元素数的 2 倍
int head[M], nxt[M], cntNode;
long long val[M];
int num[M];

int hashi(long long x) { return (int)((x % M + M) % M); }

int* findNode(long long x) {          // 找到返回指针，找不到返回 nullptr
    int h = hashi(x);
    for (int i = head[h]; i; i = nxt[i])
        if (val[i] == x) return &num[i];
    return nullptr;
}

void add(long long x) {               // 计数 +1（不存在则新建）
    int* p = findNode(x);
    if (p) { (*p)++; return; }
    int h = hashi(x);
    val[++cntNode] = x; num[cntNode] = 1;
    nxt[cntNode] = head[h]; head[h] = cntNode;
}

int query(long long x) {
    int* p = findNode(x);
    return p ? *p : 0;
}

unordered_map<long long, int> id;
int tot = 0;
auto getId = [&](long long x) {
    auto it = id.find(x);
    if (it != id.end()) return it->second;
    return id[x] = ++tot;              // 新值分配新编号
};

int probeSquare(long long k) {
    int h0 = hashi(k);
    for (int i = 0; i < M; i++) {
        int h = (h0 + i * i) % M;      // 只向一个方向平方
        if (key[h] == EMPTY || key[h] == k) return h;
    }
    return -1;                        // 表满
}

sort(a + 1, a + n + 1);
long long ans = 0;
int l = 1, r = 1;
for (int l = 1; l <= n; l++) {
    while (r <= n && a[r] - a[l] < C) r++;
    while (r <= n && a[r] - a[l] == C) { ans++; r++; }
    // 注意：这里只统计了「值对」，不区分原始下标，视题目定义调整
}