哈希、哈希表和离散化

作者： 作者的头像   huolong , 时间：2025-11-11 13:47:10 , 所有人可见, 阅读  19

一、字符串哈希

1. 什么是哈希

哈希算法是通过 哈希函数 将字符串或较大的数转换为能够用变量表示或直接作为数组下标的数。通过哈希算法转换后的值，称为 哈希值。哈希值可以实现快速查找和匹配。

示例：
使用数组下标计数法，统计一个字符串中每种字母出现的次数是一种简单的哈希方法。例如，将每个字母映射为对应的 ASCII 码。

2. 如何构造哈希

原理

将字符串中的每个字符看作一个数字（例如，将 a-z 映射为 1-26），然后将整个字符串视为一个 b 进制的数进行计算。

注意：字符不能映射为 0，否则例如 a、aa 和 aaa 的哈希值都为 0。

示例

字符串 s = "abcd"，视为 26 进制的数，其哈希值为：

$ \text{hash}(s) = 1 \times 26^3 + 2 \times 26^2 + 3 \times 26^1 + 4 \times 26^0 $

注意问题

当字符串较长时，计算出的哈希值可能会超过 long long 的范围，因此通常需要取模：

$ \text{hash}(s) \% h $

其中，h 为一个固定的值。

常用参数选取

  • b：通常取31， 131 或 13331。
  • h：通常取 $2^{64}$，以减少哈希冲突的概率。用unsigned long long进行存储。

哈希函数定义

假设字符串 $C = c_1c_2c_3...c_m$，其哈希函数为：

$ H(C) = (c_1 \times b^{m-1} + c_2 \times b^{m-2} + ... + c_m \times b^0) \mod h $

3. 滚动哈希优化

在处理长字符串时，如果需要判断两个长度为 len 的子串是否相同，直接计算哈希值的时间复杂度为 $O(\text{len})$，这与直接比较子串并无优势。因此，可以通过 滚动哈希 技巧优化到 $O(1)$ 时间复杂度。

（1）滚动计算前缀哈希 $h(k)$

设 $h(k)$ 为字符串前 $k$ 个字符组成的子串的哈希值，不考虑取模时：

$ h(k+1) = h(k) \times b + c_{k+1} $

类比：
十进制数 12345，取前三位为 123，要取前四位，可以通过 $123 \times 10 + 4$ 计算得出 1234。

（2）利用前缀哈希 $H(k)$ 计算区间哈希值

设：

  • $H(R)$ 为字符串前 $R$ 个字符的哈希值；
  • $H(L-1)$ 为字符串前 $L-1$ 个字符的哈希值。

区间哈希值 $H(L, R)$ 的计算公式为：

$ H(L, R) = H(R) - H(L-1) \times b^{R-L+1} $

由上述公式可知，只需要预处理出$b^m$，就可以在$O(1)$的时间内求得任意子串的哈希值。

（3）时间复杂度

对于长度为 n 的字符串，任意取长度为 m 的子串进行匹配，总时间复杂度为 $O(n + m)$。

例题：子串判重

#include <bits/stdc++.h>
typedef unsigned long long ULL;
const int N = 1e6 + 10, P = 131;  // h[i]: represents the hash value of substring 1 to i, p[i]: represents P^i

ULL h[N], p[N];
char s[N];  // String input

// Returns the hash value of substring s[l...r]
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {    
    scanf("%s", s + 1);  // Input the string (1-based index)

    int len = strlen(s + 1);

    // Precompute p[] (P powers) and h[] (prefix hash values)
    p[0] = 1;
    for (int i = 1; i <= len; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + (s[i] - 'a' + 1);
    }

    int m;
    scanf("%d", &m);  // Number of queries

    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);  // Input the ranges of two substrings

        // Check if the two substrings are equal by comparing their hashes
        if (get(l1, r1) == get(l2, r2)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }

    return 0;
}

例题：前缀和后缀

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

const int N = 4e5 + 10, P = 131;
unsigned long long p[N], h[N]; // p[i] stores P^i, h[i] stores hash value of substring [1..i]
char s[N];  // Input string

// Calculate hash values for the string s
void gethash() {
    p[0] = 1;  // P^0 = 1
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++) {
        p[i] = p[i - 1] * P;  // Calculate P^i
        h[i] = h[i - 1] * P + (s[i] - 'a' + 1);  // Rolling hash for the prefix s[1..i]
    }
}

// Get hash value of substring s[l..r]
unsigned long long get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    while (scanf("%s", s + 1) != EOF) {
        gethash();  // Calculate hash values for the string s

        int len = strlen(s + 1);
        for (int i = 1; i <= len; i++) {
            // Check if prefix s[1..i] and suffix s[len-i+1..len] are equal
            if (get(1, i) == get(len - i + 1, len)) {
                printf("%d ", i);  // Print the length of matching prefix and suffix
            }
        }
        printf("\n");
    }
    return 0;
}

哈希表

1. 哈希表原理

（1）使用数组下标直接标记元素

哈希表（也叫散列表）是一种高效的数据结构，通过将关键码值映射到表中的一个位置来访问记录。
哈希表的查找时间复杂度接近常数时间，但其缺点是可能需要消耗较多的内存。

示例：
现在要存储和使用以下线性表：A = {12, 83, 284, 49, 183, 13491, 58}。
如果直接使用数组下标，可以开一个一维数组 A[1...13491]，并让 A[key] = key，从而实现 $O(1)$ 时间的查找。
但这种方法会造成严重的空间浪费，尤其是当数据范围很大时。

（2）除余法构造哈希值

为减少空间开销，可以优化哈希表的设计，通过 除余法 构造哈希值。
设计哈希函数： $ H(\text{key}) = \text{key} \mod 17 $ 然后令： $ A[H(\text{key})] = \text{key} $

这种方法仅需定义一个一维数组 A[0...16] 即可，大大减少了空间占用。但此方法可能会导致 哈希冲突。
示例：
当 H(2) 和 H(19) 的值都是 2 时，发生了哈希冲突。

2. 哈希冲突解决方法

由于可能难以完全避免哈希冲突，可以采用以下方法：

链地址法（拉链法）

为每一个哈希值维护一个链表（类似于邻接表），将所有映射到同一哈希值的元素存储在链表中。
查询时，只需遍历对应链表即可。实际复杂度取决于链表的长度，通常视为常数级。

示例：哈希运算与插入

定义哈希函数： $ H(x) = x \mod 16 $

对数组 $A = {12, 83, 284, 49, 183, 13491, 58}$ 进行哈希运算并插入数据后的结果如下：

哈希值 $H(x)$ 链表存储值
0 -
1 49
2 -
3 83，13491
4 -
5 -
6 58
7 183
8 -
9 -
10 -
11 -
12 12，284
... -

通过此方法，既节省了空间，又在一定程度上解决了冲突问题。

（3）哈希函数的构造

取余法构造哈希函数

通过取余法构造哈希函数： $ H(\text{key}) = \text{key} \% b $

其中，b 是哈希表的大小，通常选择为能存储所有数据且尽量大的素数。

原因

选择质数作为模数 b 的原因是： 1. 减少冲突：
如果 b 的约数较多，不同数据映射到同一哈希值的概率会增加，从而导致冲突。
质数作为模数时，不同数据的分布会更加均匀，冲突的概率更小。

  1. 空间与效率的平衡：
    通常根据可用空间大小选择一个接近 $10^6$ 的素数，既节省空间，又保证足够低的冲突率。比如：1000003

实践建议

在实际应用中，建议结合具体需求和数据规模，选择适合的 b 值。例如： - 如果数据规模较小，可以选取一个略大于数据范围的质数。 - 如果数据范围非常大，可以使用动态哈希或其他高级哈希策略。

C++代码举例：

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

#include <iostream>
#include <vector>

using namespace std;

const int N = 100003; // 哈希表的大小（质数）

// 哈希表
vector<vector<int>> hashTable(N);

// 插入操作
void insert(int x) {
    int k = (x % N + N) % N; // 计算哈希值
    for (int val : hashTable[k]) {
        if (val == x) return; // 如果已经存在，则不重复插入
    }
    hashTable[k].push_back(x); // 插入到对应链表
}

// 查找操作
bool find(int x) {
    int k = (x % N + N) % N; // 计算哈希值
    for (int val : hashTable[k]) {
        if (val == x) return true; // 找到返回 true
    }
    return false; // 未找到返回 false
}

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

    while (n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if (*op == 'I') {
            insert(x);
        } else {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

离散化

1. 什么是离散化

离散化是在 不改变数据相对大小 的条件下，将数据进行相应的缩小处理。
例如：
- 原数据：1, 999, 100000, 15
处理后：1, 3, 4, 2
- 原数据：{100, 200}, {20, 50000}, {1, 400}
处理后：{3, 4}, {2, 6}, {1, 5}

离散化本质上可以看作是一种特殊的哈希，其特点是：
- 数据在哈希之后，仍然保持原来的全序或偏序关系。
- 通常用于解决 仅依赖元素之间的相对大小关系 的问题。

2. 离散化的步骤

离散化通常包括以下步骤：

（1）去重

由于数组中可能存在重复元素，因此需要对数据去重。
这一步可以通过将所有元素放入集合中实现，也可以对数组排序并去除重复项。

（2）计算离散化后的值

为每个元素计算离散化后的值，常用的方法是 二分查找：
- 对原数组排序，得到去重后的有序数组 sorted_arr。
- 对于每个原数组中的元素 a[i]，找到其在 sorted_arr 中的索引位置，并赋值为离散化后的值。

示例：
- 原数组：{10, 50, 20, 10}
- 排序去重：sorted_arr = {10, 20, 50}
- 离散化结果：
- 10 对应 1
- 20 对应 2
- 50 对应 3
- 最终离散化数组：{1, 3, 2, 1}

时间复杂度分析

  • 去重和排序：$O(n \log n)$
  • 二分查找：$O(n \log n)$
  • 总复杂度：$O(n \log n)$

C++代码：

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com