Just for Life.

明月更几时

0%

算法系列：哈希

发表于 更新于
本文字数： 6.4k 阅读时长 ≈ 6 分钟

每天一点点算法开始了，为什么我就写不出很爽的代码。今天被邀请去水了一场类似ACM的程序设计竞赛，他说是期末考试难度，结果那个难度……题目只做出了一半，剩下的实在是…….出题人的语文水平太差了，没交代清楚题要干什么，很多细节描述的模棱两可。如果你考我程序设计，我没问题；通过模糊的信息表达来考察语文理解能力就没意思了，为啥不多打几个字把问题交代清楚呢？为节省空间，本文压缩了某些代码，实际工程切勿模仿。

概念

哈希是一种典型的利用空间换时间的算法，通过申请大量的空间，来达到在$O(1)$的时间复杂度内快速查询元素的目的。如最简单的，假设输入序列是0,1,2,3,4,5，申请一个数组作为哈希表。那么此时的哈希计算公式就可以是：H[i] = i % size。size是哈希表的长度，或者说是数组的长度。那么0存储在0号位置，5存储在5号位置。元素插入哈希表和查询哈希表内元素都可以在内完成。

假设表长为5，如果要插入的序列是0,2,4,7，就不能用上面的映射公式了，因为7%5 == 2%5，也就是2号位置会存储2或7，导致了冲突(collision)。这个时候就需要用探测的方法来确定7该存在哪里，常用的方法有：线性探测法、平方探测法。

道理就是这么个道理，有很多方法可以实现哈希，如数组、map等。

哈希插入

现在手动模拟一下用平方探测法（只考虑正数项）来模拟下哈希插入的过程。经验而言，哈希表的长度最好是素数。第一行中，首先输入表长，若表长不为素数，则增加表长转换为最近的素数，而后输入元素的数量$N$。在下一行输入$N$个数据，插入到哈希表中，并输出插入的位置；若无法插入，则输出-。

样例输入：

1
2
4 4
10 6 4 15

样例输出：

1
0 1 4 -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <array>
using namespace std;
// 申请这么长的数组作为哈希表
array<int, 10005> arr;
int m, n;
// 判断是否为素数
bool isprime(int num) {
    if(num == 1) 
        return false;
    for(int i = 2; i * i <= num; i++)
        if(num % i == 0) 
            return false;
    return true;
}
// 二次探测法插入元素
void insert(int a){
    // i 是步长，m 是表长
    for (int i = 0; i < m; i++){
        int idx = (a + i * i) % m;
        // 如果为空，插入，并输出索引位置
        if (arr[idx] == 0){
            arr[idx] = 1;
            cout << idx;
            return;
        }
    }
    // 否则表示插入失败
    cout << "-";
}
int main(){
    int a;
    cin >> m >> n;
    // 逐步叠加，找到素数的表长
    while (!isprime(m)) 
        m += 1;
    // 开始插入元素
    for (int i = 0; i < n; i++){
        cin >> a;
        if (i != 0) 
            cout << " ";
        insert(a);
    }
    return 0;
}

哈希查找

第二种常见应用是先把一个序列的元素插入到哈希表中；而后查询另一个序列的元素有没有在哈希表中，计算总共的查找次数。和上面不同的是，插入元素时不能单纯的将哈希表的数值设为1了，而应该是具体的数值，来看一个实例。在第一行输入三个数字，第一个数字是哈希表长度，和上述问题一样需要处理为素数；第二个为输入序列的长度$N$；第三为查询序列长度是$M$。第二行给出$N$个元素，用二次探测法插入到哈希表中，如果不能插入，打印插入失败信息；第三行给出$M$个元素，在哈希表中查询这些元素，记录查询次数。

输入样例：

1
2
3
4 5 4
10 6 4 15 11
11 4 15 2

输出样例：

1
2
15 cannot be inserted.
2.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <array>
using namespace std;
array<int, 10005> arr;
int size_, n, m;
bool isPrime(int m){
    if (m == 1)
        return false;
    for (int i = 2; i * i <= m; i++)
        if (m % i == 0)
            return false;
    return true;
}
void insert(int val){
    for (int i = 0; i < size_; i++){
        int idx = (val + i * i) % size_;
        // 插入元素为对应的数值
        if (arr[idx] == 0){
            arr[idx] = val;
            return;
        }
    }
    cout << val << " cannot be inserted." << endl;
}
int main(){
    cin >> size_ >> n >> m;
    while (!isPrime(size_))
        size_ ++;
    cout << size_ << endl;
    int t;
    double cnt{0};
    for (int i = 0; i < n; i++){
        cin >> t;
        insert(t);
    }
    for (int i = 0; i < m; i++){
        cin >> t;
        for (int j = 0; j < size_; j++){
            cnt++;
            int idx = (t + j * j) % size_;
            // 如果和查询元素相等，表示查找到，退出
            // 如果查找为 0，表示序列中无此元素，查找结束，退出
            if (arr[idx] == t || arr[idx] == 0)
                break;
        }
    }
    printf("%0.1f", cnt / m);
    return 0;
}

哈希应用

哈希在算法领域还是很常见的一种技巧，有很高的应用价值。接下来看几道例题，比单纯的哈希插入、查找要有意思的多。

映射唯一

一种最简单的实例，通过数组实现哈希。先给出一个整数$N$，随后给出$N$行的人员信息，格式为：队伍编号-队员编号 成绩，以队伍编号为单位，计算得分最多的单位。思路就是：以每个队伍的编号为数组的下标，下标对应的数组元素为队伍的分数。这里能这么做的原因是，在哈希的过程中，队伍编号是唯一的。

输入样例:

1
2
3
4
5
6
7
6
3-10 99
11-5 87
102-1 0
102-3 100
11-9 89
3-2 61

输出样例:

1
11 176

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <array>
using namespace std;
array<int, 1005> arr = {0};
int main(){
    int n, g, p, s, maxn{-1}, id{-1};
    cin >> n;
    for (int i = 0; i < n; i++){
        scanf("%d-%d %d", &g, &p, &s);
        // 队伍加分
        arr[g] += s;
    }
    // 输出最大
    for (int i = 0; i < 1005; i++){
        if (arr[i] > maxn){
            maxn = arr[i];
            id = i;
        }
    }
    cout << id << " " << maxn;
    return 0;
}

map 实现哈希

map数据结构是什么请移步此处。假设开学要查抄学生携带的违规物品，输入第一行给出两个正整数$N$和$M$，分别是学生人数和需要被查缴的物品种类数。第二行给出$M$个需要被查缴的物品编号，其中编号为 4 位数字。随后$N$行，每行给出一位学生的姓名缩写（由 1-4 个大写英文字母组成）、个人物品数量$K$、以及$K$个物品的编号，顺次检查每个学生携带的物品，如果有需要被查缴的物品存在，则按以下格式输出该生的信息和其需要被查缴的物品的信息（注意行末不得有多余空格）。

输入样例：

1
2
3
4
5
6
4 2
2333 6666
CYLL 3 1234 2345 3456
U 4 9966 6666 8888 6666
GG 2 2333 7777
JJ 3 0012 6666 2333

输出样例：

1
2
3
4
U: 6666 6666
GG: 2333
JJ: 6666 2333
3 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <map>
using namespace std;
int main(){
    int n, m, k, cnt1{0}, cnt2{0};
    cin >> n >> m;
    string s, name;
    // 将违规物品映射为1
    map <string, int> check;
    for (int i = 0; i < m; i++){
        cin >> s;
        check[s] = 1;
    }
    for (int i = 0; i < n; i++){
        cin >> name >> k;
        int flag{0};
        for (int j = 0; j < k; j++){
            cin >> s;
            // 如果查询到就说明违规，违规物品记录多次
            if (check[s] == 1){
                cnt2++;
                // 只记录一次违规人数
                if (flag == 0){
                    cout << name << ":";
                    flag = 1;
                    cnt1 ++;
                }
                cout << " " << s;
            }
        }
        if (flag == 1)
            cout << endl;
    }
    cout << cnt1 << " " << cnt2;
    return 0;
}

字符串过滤

给定两个字符串，删除第一个字符串中所包含的第二个字符串的字符，实现两个字符串相减。如果每次输出字符都判断一下这个字符是否在第二个字符串中，复杂度约为$O(n^2)$，必然会超时。如果使用哈希，开辟一块内存空间，就能大规模减少时间复杂度到$O(n)$。

样例输入：

1
2
They are students.
aeiou

样例输出：

1
Thy r stdnts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int main() {
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);
    bool flag[256] = {false};
    // 遍历第一个字符串，全部设为 true
    for (int i = 0; i < str1.length(); i++)
        flag[str1[i]] = true;
    // 遍历第二个字符串，设为 false
    for (int i = 0; i < str2.length(); i++)
        flag[str2[i]] = false;
    // 再次遍历第一个，只输出 true，false的会被屏蔽
    for (int i = 0; i < str1.length(); i++)
    {
        if (flag[str1[i]] == true)
            printf("%c", str1[i]);
    }  
    return 0;
}

减少计算量

$3n+1$猜想的步骤是：如果一个数是偶数，那将它除以2；如果一个数是奇数，那么将它乘以3后加1，经过有限步骤一定可以取值为1。为了节省计算，可以记录递推过程中遇到的每一个数。如计算$n=3$时，需要计算3、5、8、4、2、1，当下一次遇到5、8、4、2的时候，就不用计算了，可以直接判断得到结果。称5、8、4、2是3的覆盖数。我们称一个序列中的某几个数是关键数，如果这几个关键数不被其他数字所覆盖。现在给出一个序列，序列中元素的最大值为100，最小值为2，计算其中的关键数，并从大到小输出。

这就是一个典型的哈希问题，创建一个数组，以序列元素为数组的下标进行查询；数组的取值表示是否为关键数，这里设取值为1表示关键数。如果序列中的值对应数组元素的取值是1，则输出。因为序列中最大值为100，所以能设计的最大取值范围是99*3+1=298。凑个整，直接申请300大小的数组。那么来编写代码。

输入样例：

1
2
6
3 5 6 7 8 11

输出样例：

1
7 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
using namespace std;
array<int, 300> arr = {0};
vector<int> v;
bool cmp(int a, int b){
    return a > b ? true : false;
}
int main(){
    int k, tmp, flag{0};
    cin >> k;
    v.resize(k);
    for (int i = 0; i < k; i++){
        cin >> tmp;
        v[i] = tmp;
        while (tmp != 1)
        {
            if (tmp % 2 != 0)
                tmp = tmp * 3 + 1;
            tmp = tmp / 2;
            // 如果已经是非关键数了，那么之后的肯定是非关键数
            if (arr[tmp] == 1)
                break;
            // 非关键数全部记录为 1
            arr[tmp] = 1;
        }
    }
    // 对序列从大到小排序
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++){
        // 如果序列对应的哈希值不是1，那么就是非关键数，输出
        if (arr[v[i]] == 0){
            if (flag == 0){
                cout << v[i];
                flag = 1;
            }
            else cout << " " << v[i];
        }
    }
    return 0;
}

结语

如果后续遇到了其他类型的不错题目，会继续追加到这里。

本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章