一本通提高篇学习笔记-哈希和哈希表

曾经也是学过的东西,现在重新学一遍。其实就是通过一个人为制造的函数H,把一些比较大的数字或者字符串转化成能直接通过变量或者数组下标表示的东西,这个函数就是哈希函数。通过哈希函数转化得到的数值一般称之为哈希值。通过哈希值可以快速查找和匹配。


字符串哈希

用来解决子串类问题。一个比较常见的问题是寻找长度为n的主串上出现了多少次长度为m的子串,这类问题可以使用kmp解决,也可以使用字符串哈希解决。但是如果是这种问题:从主串中每次选取两个子串,问是否匹配(可能相当大),此时便只能使用字符串哈希。

具体操作?哈希函数并不是一个具体的函数,它是可以进行人为定义的,任何一种可以离散化的方法都可以作为一个哈希函数使用。一个比较简单直观的方法是取余法,令hash(k) = k % m,m代表哈希表的大小,取决于你的空间。m越小哈希冲突概率越大, m越大空间开销越大,所以m的值要合理分配。

一个可能的代码实现:

1
2
3
4
5
6
7
8
9
10
int hash(string s) {
int seed = (随便一个数);
int m = HASH_SIZE;
int Hash = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
Hash = (Hash * seed + x[i] - '0') % m;
}
return Hash;
}

这样可以在O(n)的复杂度内完成哈希操作。但是这样做缺点是明显的,极有可能哈希冲突,也就是不同的串得到了相同的哈希值,这样可能会导致错误。解决哈希冲突的方法有多种,这里介绍双哈希。其实就是把哈希函数再写一遍,这次换一个不同的种子,只有两个哈希值都相等才能断定两个字符串相等。实际证明这个方法实用性不错。

下面介绍一下滚动哈希的优化技巧。选取两个合适的互质常数b和h(b < h),假设有字符串C = c1c2…cm,那么定义哈希函数Hash(C) = (c1bm-1+c2bm-2+…+cmb0) % h

正常的数字是十进制的,这里相当于把字符串C看成一个b进制的“数”,用b做基数。这一过程是递推计算的,设Hash(C,k)为前k个字符构成的字符串的哈希值,则有H(C,k+1) = H(C,k) × b + ck+1 (暂不考虑取模)

通常,题目要求的是判断主串的一段字符与另一个字符串是否匹配,即判断字符串C = c1c2…cm从k+1位置的长度n的子串C’ = ck+1ck+2…ck+n的哈希值与另一匹配字符串S = s1s2…sn的哈希值是否相等,于是有Hash(C’) = Hash(C,k+n) - Hash(C,k) × bn

(代码有问题,debug中)

哈希表

哈希表是一种高效的数据结构,它的优点同字符串哈希一样,查找的算法时间效率几乎就是常数,同时也很容易实现,多产生的代价仅仅是消耗较多内存。

假设现在有一个线性表A(1,75,324,1353,43,91,40),用n代表元素个数,存储它很简单,只需要一个一维数组。但是这样的数据结构为查找带来了麻烦。如果是顺序存放还好说,我们可以使用二分查找,但是大部分情况下序列是无序的,我们只能使用线性复杂度的算法进行查找。但当n非常大时,速度依然会变得很慢。

我们考虑使用“桶”,开一个特殊的数组,其下标最大值为序列A中的最大值,也就是有一个数组b[1354](C/C++中数组从0开始,长度为n的话最大值到n-1,这里应该是1354而不是1353),然后我们令A中的所有元素都在这个b数组里“对号入座”,将数值作为下标,值只有0和1两种(其实不拘泥于这两个数,只是比较常用,只要能区分“有”和“没有”就可以),这样根据这个“桶”来进行查找,时间复杂度变成了常数。但这样仍然会存在一个问题,数组下标并不能很大,这样对于大数据来说仍然是不太合适的。并且这样会造成很大的空间浪费。不过我们可以采用哈希技术,为每个数设置一个哈希值。人为构造哈希函数Hash(x) = x % 123,这样所有的数都变成了0到122之间的数,空间变小了很多。

实际上,这样做仍然存在问题。单纯的进行取模操作会导致大量的数据经过哈希操作后有重复,这就是哈希冲突。那么在查询时就有概率出现错误。哈希表与字符串哈希有所不同,有时题目的测试数据足够大,导致无论如何选择哈希函数都无法避免冲突,而且为了避免冲突去刻意构造一个复杂的哈希函数也得不偿失。这里我们的做法是使用链表。当发生冲突时把这个值挂在链表的下一个结点上,这样虽然查找时的复杂度不是严格的O(1),但是期望仍然是O(1),实际复杂度取决于链表长度,也就是冲突的程度。

假设以6为模数,哈希表应该是类似于下面这样:

(实际上,实际使用的模数一般要比6大得多,而且一般都是质数,这里仅是举例)

显然,如何构造哈希函数是决定哈希表查找效率的关键。因为只要哈希值的分布足够平均,链表查找的复杂度就会变小。下面是三种比较常用的哈希函数构造方法,

1.取余法

选择一个适当的正整数m,用原数据对m取模的结果作为哈希值,也就是Hash(x) = x % m,这个方法应用是比较广泛的,使用率也比较高。这个方法的关键在于如何选取合适的m,一般是选择一个比较大的质数,这里给出一个从网上找的常用取模质数表,可供参考:

61, 83, 113, 151, 211, 281, 379, 509, 683, 911 / 一千以下

1217, 1627, 2179, 2909, 3881, 6907, 9209, /一万以下

12281, 16381, 21841, 29123, 38833, 51787, 69061, 92083, /十万以下

122777, 163729, 218357, 291143, 388211, 517619, 690163, 999983, /百万以下

1226959, 1635947, 2181271, 2908361, 3877817, 5170427, 6893911, 9191891, /千万以下

12255871, 16341163, 21788233, 29050993, 38734667, 51646229,68861641, 91815541,/一亿以下

1e9+7 和 1e9+9 //十亿左右

122420729,163227661,217636919,290182597,386910137,515880193,687840301,917120411,/十亿以下

1222827239,1610612741, 3221225473ul, 4294967291ul /十亿以上

一般来说,如果m的约数越多,造成冲突的概率就会越大,所以尽量选择质数。

2.乘积取整法

用值乘以一个在(0,1)中的实数A(最好是无理数,(√5 - 1)/2是一个实际效果很不错的数),这样能得到一个(0,k)之间的实数,取其小数部分再乘以哈希表的大小M,再向下取整,然后得到在哈希表中的位置。

这个听起来就挺麻烦的(摊)

3.基数转换法

类似于字符串哈希使用的方法:将值看成是另一种进制的数,然后把它转化成十进制数,然后用取余法。一般取大于10的数作为转换基数,并且最好和原来进制的10互质。比如将一个十进制数强行看作是13进制,然后按照进制转换规则转成10进制,就得到一个值。

听起来也好麻烦。。。

事实上,哈希函数的构造方法有很多,并没有硬性规定,能避免冲突就可以。

取余法代码实现:

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 <cstdio>
#define maxn 500000
#define m 999983
using namespace std;

int tot, adj[maxn], nxt[maxn], num[maxn];
int top, stk[maxn];

void init() {
//初始化哈希表,在多组数据时用来清空哈希表
//用一个栈存储出现过的哈希值,每次只要把出现过的哈希值的链表清零就可以,节省时间
tot = 0;
while (top) {
adj[stk[top--]] = 0;
}
}

void insert(int key) {
//使用取余法进行插入
int h = key % m;
for (int e = adj[h]; e; e = nxt[e]) {
if (num[e] == key)
return; //遍历链表如果已经出现过这个值就没必要再存一遍
}
if (!adj[h]) // 如果能走到这里说明这个值没存过,要进行存储,把第一次出现的哈希值入栈
stk[++top] = h;
nxt[++tot] = adj[h];
adj[h] = tot;
num[tot] = key; //用类似于建立邻接表的方式建立链表,存储下所有哈希值等于h的数字
}

bool query(int key) {
//查询操作
//先求哈希值再遍历链表,查找到则表示存在
int h = key % h;
for (int e = adj[h]; e; e = nxt[e]) {
if (num[e] == key)
return true;
}
return false;
}


int main() {
//此处请自由发挥
return 0;
}


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:一本通提高篇学习笔记-哈希和哈希表

文章作者:Shawn Zhou

发布时间:2019年01月22日 - 16:01

最后更新:2019年01月25日 - 21:01

原始链接:http://shawnzhou.xyz/2019/01/22/19-01-22-02/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%