哈希表 -- 刷题（查找算法）

目录

💻哈希 -- 知识点

🐍刷题?

🌼1，雪花

AC? --? vector?

AC? --? 链式前向星

🌼2，公式

---

💻哈希 -- 知识点

线性表 和 树表，通过比较关键字进行查找

而 散列表，基于 哈希函数 实现，根据关键字直接访问

它通过 散列（哈希）函数，将 关键字 映射 到 存储地址，建立关键字和存储地址的映射

常见 散列(哈希) 函数👇

直接定址，除留取余，随机数，数字分析，平方取中....

常见 处理冲突 的方法👇

（1）开放地址法

a. 线性探测：蹲坑时，发现坑被占了，就找后面一个...（缺点：容易堆积）

di = 1, ..., m - 1（逐个向后找）

hash'(key) = (hash(key) + di) % m?

m 表长，di 增量序列，hash'(key) 探测函数

b. 二次探测：前后跳跃式探测，冲突时，后 1 位，前 1 位，后 2^2 位，前 2^2 位...

c. 随机探测

d. 再散列

（2）链地址法

又称 拉链法

冲突的同义词，存储在一个线性链表中

适用于 -- 经常插入 / 删除的情况

🐍刷题?

🌼1，雪花

3349 -- Snowflake Snow Snowflakes (poj.org)

思路

?采用 哈希表 + vector? 或? 哈希表 + 链式前向星

（1）每个雪花 6 个花瓣求和，然后 mod P（大的质数）

（2）哈希表 Hash[key] 中（key 相同的链），查询是否有相同顺序的雪花

（3）比较时，顺时针，逆时针，分别比较一次

（4）哈希表，处理冲突，采用链地址法

AC? --? vector?

较慢

#include<iostream>
#include<cstdio> // scanf()
#include<vector>
using namespace std;

// snow[i] 存储 i 号雪花
// Hash[i] 存储哈希值为 i 的所有雪花
const int maxn = 100010, P = 100007; // P 大的质数
vector<int> Hash[P]; // 散列表
int snow[maxn][6]; // 存储雪花 （6 个边长）
int n;

// 比较雪花 a b 是否一样
bool cmp(int a, int b) 
{
    int i, j;
    for (i = 0; i < 6; ++i) {
        if (snow[a][0] == snow[b][i]) {
            // 顺时针
            for (j = 1; j < 6; ++j) 
                if (snow[a][j] != snow[b][(i + j) % 6]) // a 逐个向后
                    break;
            if (j == 6) return 1; // 一样
            // 逆时针
            for (j = 1; j < 6; ++j)
                if (snow[a][6 - j] != snow[b][(i + j) % 6]) // a 逐个向前
                    break;
            if (j == 6) return 1; 
        }
    }
    return 0;
}

// 散列表中，查找 雪花 i
bool find(int i)
{
    int key = 0;
    for (int j = 0; j < 6; ++j)
        key += snow[i][j];
    key %= P; // 边长和 取余 P 得到 哈希值
    for (int j = 0; j < Hash[key].size(); ++j)
        if (cmp(i, Hash[key][j])) // 比较每一个同义词
            return 1; // 找到相同雪花, 直接返回
    Hash[key].push_back(i); // 没找到, 先 push_back 再返回
    return 0;
}

int main()
{
    int flag = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) { // n 个雪花
        for (int j = 0; j < 6; ++j) // 6 个边长
            scanf("%d", &snow[i][j]);
        if (find(i)) // 每次输入雪花都要加入 散列表 并判断
            flag = 1;
    }

    if (flag)
        printf("Twin snowflakes found.");
    else 
        printf("No two snowflakes are alike.");
    return 0;
}

AC? --? 链式前向星

较 vector 快，这里不自己写了，按书里给的部分代码，没AC

贴 一个 网上过了的代码

#include <iostream>
#include <cstdio> // scanf()
#include <cstring> // memset()
using namespace std;

const int MAXN = 100050;
const int mod = 99991;

struct node {
    int a[6], next;  // 存储雪花的六个边长和下一个同义词雪花的位置
} e[MAXN];

int head[mod], num[6], cnt = 0;  // 哈希表、辅助变量

// 计算哈希值
int Hash() {
    int sum = 0, mul = 1;
    for (int i = 0; i < 6; ++i) {
        sum = (sum + num[i]) % mod;
        mul = (1LL * mul * num[i]) % mod;
    }
    return (sum + mul) % mod;
}

// 添加同义词雪花
void add(int val) {
    ++cnt;
    for (int i = 0; i < 6; ++i) {
        e[cnt].a[i] = num[i];
    }
    e[cnt].next = head[val];
    head[val] = cnt;
}

// 判断两个雪花是否相同
bool equal(int pos) {
    bool flag = false;
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            flag = false;
            for (int k = 0; k < 6; ++k) {
                if (e[pos].a[(i+k)%6] != num[(j+k)%6]) {
                    flag = true;
                    break;
                }
            }
            if (!flag) return true;
            flag = false;
            for (int k = 0; k < 6; ++k) {
                if (e[pos].a[(i+k)%6] != num[(6+j-k)%6]) {
                    flag = true;
                    break;
                }
            }
            if (!flag) return true;
        }
    }
    return false;
}

// 处理同义词雪花
bool solve() {
    int val = Hash();
    for (int i = head[val]; i != -1; i = e[i].next) {
        if (equal(i)) return true;
    }
    add(val);
    return false;
}

int main() {
    memset(head, -1, sizeof(head));  // 初始化哈希表

    int n;
    scanf("%d", &n);  // 输入雪花的数量

    for (int i = 1; i <= n; ++i) {  // 循环读入每个雪花的边长
        for (int j = 0; j < 6; ++j)
            scanf("%d", &num[j]);
        if (solve()) {
            printf("Twin snowflakes found.");  // 存在同义词雪花
            return 0;
        }
    }

    printf("No two snowflakes are alike.");  // 不存在同义词雪花
    return 0;
}

🌼2，公式

1840 -- Eqs (poj.org)

解释?

将方程 变形

变形成 a3 * ^3 + a4 * ^3 + a5 * ^3 = - (a1 * ^3 + a2 * ^3)

（1）定义哈希数组 Hash[]，Hash[i] 表示哈希值为 i 的数量

（2）暴力枚举 x1, x2??[-50, 50] ，x1, x2 != 0，计算等式右边的值为 temp

temp < 0，则 temp += maxn

maxn 设置成 2500万，因为等式右边取值范围为 -1250 ~ 1250 万，考虑到 哈希值 i 不能为负数

当 temp为正数，范围 0 ~ 1250万

当 temp是负数，范围 -1250万 ~ 0，此时 + 2500万，变成 1250万 ~ 2500万

然后 Hash[temp]++，表示等式右边和为 temp 的情况 +1

（3）暴力枚举 x3, x4, x5....计算等式左边的 temp 值

如果此时的 Hash[temp] == 1，等式成立，ans += Hash[temp];

（4）注意：x1, x2, x3, x4, x5 != 0，出现 == 0 时要 continue 跳出 for()

又 ∵ 数组较大，2500万，用 short 防止超内存

AC? 代码?

#include<iostream>

const int maxn = 25000000;
short Hash[maxn];

int main()
{
    int ans = 0;
    int a1, a2, a3, a4, a5;
    std::cin >> a1 >> a2 >> a3 >> a4 >> a5;
    // 暴力枚举 x1, x2
    for (int i = -50; i <= 50; ++i) // x1
        for (int j = -50; j <= 50; ++j) { // x2
            if (i == 0 || j == 0) 
                continue;
            int temp = (-1) * (a1*i*i*i + a2*j*j*j);
            if (temp < 0) temp += maxn; // 防止负数
            Hash[temp]++; // 哈希值为 temp 的情况 +1
        }
    // 暴力枚举 x3, x4, x5
    for (int i = -50; i <= 50; ++i) // x3
        for (int j = -50; j <= 50; ++j) // x4
            for (int k = -50; k <= 50; ++k) { // x5
                if (i == 0 || j == 0 || k == 0) 
                    continue;
                int temp = a3*i*i*i + a4*j*j*j + a5*k*k*k;
                if (temp < 0) temp += maxn;
                if (Hash[temp]) 
                    ans += Hash[temp];
            }
    std::cout << ans;
    return 0;
}