哈希表
组别：提高组
难度：6
散列表（Hashtable，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。这种方式不需要进行任何的比较，其查找的效率相较于前面所介绍的查找算法是更高的。
哈希技术的基本思想是通过由哈希函数决定的键值。(key)与哈希地址(H(x.key))之间的对应关系来实现存储组织和查找运算，哈希技术的核心是哈希函数。
这里有一个电话簿（查找表），电话簿中有 5个人的联系方式：
张三 13911879643
李四 13309876542
王五 13498456821
赵六 13546738294
孙七 13648391025
假如想查找王四的电话号码，对于一般的查找方式最先想到的是从头遍历，一一比较。而如果将电话簿构建成一张哈希表，可以直接通过名字“李四”直接找到电话号码在表中的位置。哈希函数为：每个名字的姓的首字母的 ASCII 值即为对应的电话号码的存储位置。
哈希冲突
张三和赵六两个关键字的姓的首字母都是 Z ，最终求出的电话号码的存储位置相同，这种现象称为冲突。
即：不同关键字通过哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
哈希函数设计原则：
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 所以哈希函数设计原则：
1、哈希函数的定义域必须包括需要存储的全部关键码
2、如果散列表允许有m个地址时，其值域必须在0到m-1之间
3、哈希函数计算出来的地址能均匀分布在整个空间中
4、哈希函数应该比较简单
哈希冲突的避免
通常用的处理冲突的方法有以下几种：
1、开放定址法
H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量） 当得出的哈希地址产生冲突时，选取以下 3 种方法中的一种获取 d 的值，然后继续计算，直到计算出的哈希地址不在冲突为止，这 3 种方法为：
线性探测法：d=1，2，3，…，m-1
二次探测法：d=12，-12，22，-22，32，…
伪随机数探测法：d=伪随机数
2、再哈希法
当通过哈希函数求得的哈希地址同其他关键字产生冲突时，使用另一个哈希函数计算，直到冲突不再发生。
3、链地址法
将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。
数值哈希函数构造方法
1、直接定制法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）=a*Key +b 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况 面试题：字符串中第一个只出现一次字符。
2、除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：
Hash(key) = key% p(p<=m),将关键码转换成哈希地址 。
3、平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
4、折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。
5、随机数法–(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法。
6、数学分析法–(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
字符串哈希函数构造方法
构造字符串哈希函数通常是为了快速比较字符串的相等性或者用于字符串的查重等场景。常见的字符串哈希函数使用的是 Rolling Hash 技术，基于多项式哈希的思想。下面是一个基本的字符串哈希函数的实现思路和示例代码。
哈希函数的构造步骤
- 选择基数和模数：
- 基数 P：一般选择一个大于字符串字符集大小的质数，比如26、31、或其他合适的质数。
- 模数
mod：选择一个大的质数，避免哈希冲突，一般选取如109 + 7或261-1。
- 哈希的基本原理：
- 设字符串s(s1,s2,s3,….sn)，n为字符串长度，第i个字符对应数值函数为s[i]-‘a’+1，hash[i]表示字符串子串S(1,i)的哈希值
- 哈希计算公式如下： hash=(hash[i-1]*p+s[i]-‘a’+1)%mod
例如：字符串s=”hellworld”，该字符串哈希表达如下。
代码实现：
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 50 51 | /**************************************************************** * 代码作者: Alex Li * 创建时间: 2024-08-13 18:55:40 * 最后修改: 2025-01-17 18:24:31 * 文件描述: 字符串哈希函数， ****************************************************************/ #include <iostream> #include <vector> #include <string> using namespace std; // 哈希函数配置 const int base = 31; const int mod = 1e9 + 7; /*compute_hash 函数： 计算字符串 s 的前缀哈希值并存储在 hash_values 数组中。 使用了 base 和 mod 来计算哈希值，避免溢出并减少哈希冲突。 */ vector<long long> compute_hash(const string &s) { int n = s.size(); vector<long long> hash_values(n + 1, 0); // 哈希值数组 for (int i = 1; i <= n; i++) { hash_values[i] = (hash_values[i-1]*base + (s[i] - 'a' + 1) ) % mod; } return hash_values; } //get_substring_hash 函数：用于计算子串的哈希值，这里利用前缀哈希值的性质，在常数时间内计算子串的哈希。 long long get_substring_hash(int l, int r, const vector<long long> &hash_values) { long long hash_r = hash_values[r]; long long hash_l = hash_values[l - 1]; return (hash_r - hash_l + mod) % mod; } int main() { string s; cin>>s; s=' '+s; vector<long long> hash_values = compute_hash(s); // 输出整个字符串的哈希值 cout << "Hash of the string: " << hash_values[s.size()] << endl; for(int i=1;i<=s.size();i++) { cout<<hash_values[i]<<' '; } return 0; } |
字符串子串哈希值的计算
如果是两个不同的字符串比较，只需要比较两个字符串最后一个点的哈希值即可。如果是同一个字符串的两个不同的子串比较，则涉及如何计算字符串子串s(i,j)的哈希值问题。
hash[j]表示前缀子串s(i,j)的哈希值，现在前面多计算了s(1,i-1)这部分的哈希值，需要将这部分哈希值减掉，如果设s(i,j)的长度是len，公式如下 ：
hashs(i,j)=hash[j]-hash[i-1]*plen
只需要预处理P0到pn,哪么上面戒子就变成O(1)复杂度。
如下代码实现对于一个给定的字符串，执行q次询问，每次询问子串s(s1,e1)和s(s2,e2)是否相等，每次询问如果相等输出YES， 否则输出NO.
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 | /**************************************************************** * 代码作者: Alex Li * 创建时间: 2025-01-16 18:40:24 * 最后修改: 2025-01-17 01:01:35 * 文件描述: 计算字符串的子串是否相等 ****************************************************************/ #include <bits/stdc++.h> using namespace std; const int P = 31; // 基数，用于计算哈希值 const int MOD = 1e9 + 7; // 模数，用于避免哈希值溢出 int main() { ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率 cin.tie(0); // 解除 cin 与 cout 的绑定，提高输入输出效率 int n, q, s1, e1, s2, e2; string s; cin >> s; s = ' ' + s; // 在字符串前添加一个空格，使索引从1开始 n = s.length(); vector<long long> hash_value(n + 1, 0), f(n + 1, 1); // 初始化哈希值数组和幂数组 // 计算字符串的前缀哈希值和幂值 for (int i = 1; i < n; i++) { hash_value[i] = (hash_value[i - 1] * P + s[i] - 'a' + 1) % MOD; // 计算前缀哈希值 f[i] = (f[i - 1] * P) % MOD; // 计算幂值 } cin >> q; // 读取查询次数 while (q--) { cin >> s1 >> e1 >> s2 >> e2; // 读取两个子串的起始和结束位置 // 计算两个子串的哈希值 long long hs1 = (hash_value[e1] - hash_value[s1 - 1] * f[e1 - s1 + 1] % MOD + MOD) % MOD; // + MOD 是为了确保结果为正数。由于模运算可能会导致负数结果，因此需要加上 MOD 再取模，以确保结果在 [0, MOD-1] 范围内。 long long hs2 = (hash_value[e2] - hash_value[s2 - 1] * f[e2 - s2 + 1] % MOD + MOD) % MOD; // 比较两个子串的哈希值 if (hs1 == hs2) { cout << "Yes\n"; // 如果哈希值相等，输出 "Yes" } else { cout << "No\n"; // 如果哈希值不相等，输出 "No" } } return 0; } |