Blackops

初心易得，始终难守

0%

哈希表的链式存储

发表于 更新于 分类于

哈希表（Hashtable）也叫散列表，平时竞赛或者编程中主要遇到的是对字符串、数字的哈希，比较常见的是使用除留余数法，用一个稍大且合适的质数作为哈希函数的取模数，计算得到哈希函数值之后加入哈希表，但是可能有两个数取模余数相同的情况，因此可能存在哈希冲突，此时可以用链式储存（数据结构教材上称为链地址法）来储存这些冲突的哈希值。这里主要是讲一下如何手写一个基于上述方法的简易哈希表。

其储存样子如下图：

img

其主要原理就是将较大的哈希值再一次取模，得到一个可以接受的值作为下标，然后去储存这个值，其中储存的指针就像图结构中的边那样储存即可。

哈希表还有个概念叫装填因子$\alpha = {关键字个数 / 哈希表长度}$，一般$\alpha$控制在$0.6～0.9$的范围之内；

链地址法中，装填因子为$1$比较合适，此时成功的探测长度是$1.5$，不成功是$2.0$

简易代码：

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
typedef unsigned long long ULL;
const int N = 2e6 + 7;//哈希表长
const ULL MOD = 2000003;//用于除留取余的模数，一般为最靠近但小于表长的质数
const ULL seed = 1e9 + 7;//哈希函数的种子值

struct Hash
{
    struct node
    {
        ULL v;
        int nxt;
        node(ULL _v = 0ULL, int _nxt = 0): v(_v), nxt(_nxt) {}
    } code[N];
    int head[MOD], tot;

    void init() {
        for (register int i = 0; i < N; ++i)
            head[i] = -1;
        tot = 0;
    }
    void add(ULL v) {
        int pos = v % MOD;
        code[tot] = node(v, head[pos]);
        head[pos] = tot++;
    }
    int Find(ULL v) {
        int p = v % MOD;
        for (register int i = head[p]; ~i; i = code[i].nxt) {
            if (code[i].v == v)
                return 1;
        }
        return 0;
    }
} hashtable;

附一道例题：Wannafly挑战赛11 D.白兔的字符串

代码：

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
typedef unsigned long long ULL;
const double PI = acos(-1.0);
const int M = 1e6 + 7;//题目中的字符串长度
const int N = 1e6 + 7;//哈希表长度，装填因子设为1.0
const ULL MOD = 1000003;//除留取余用的模数
const ULL seed = 1e9 + 7;//哈希函数的模数
char s[M];

struct Hash
{
    struct node
    {
        ULL v;
        int nxt;
        node(ULL _v = 0ULL, int _nxt = 0): v(_v), nxt(_nxt) {}
    } code[N];
    int head[MOD], tot;

    void init() {
        for (register int i = 0; i < N; ++i)
            head[i] = -1;
        tot = 0;
    }
    void add(ULL v) {
        int pos = v % MOD;
        code[tot] = node(v, head[pos]);
        head[pos] = tot++;
    }
    int Find(ULL v) {
        int p = v % MOD;
        for (register int i = head[p]; ~i; i = code[i].nxt) {
            if (code[i].v == v)
                return 1;
        }
        return 0;
    }
} hashtable;


int main(void)
{
    register int i, ans, ls, len;
    register ULL bas = 1, af = 0, be = 0;
    while (~scanf("%s", s + 1))
    {
        hashtable.init();
        len = strlen(s + 1);
        for (i = 1; i <= len; ++i)
        {
            af = (af * seed + * (s + i));
            bas = bas * seed;
        }
        hashtable.add(af);
        for (i = 1; i <= len; ++i)
        {
            af = (af * seed + s[i]);
            be = (be * seed + s[i]);
            hashtable.add(af - be * bas);
        }
        caseT
        {
            scanf("%s", s + 1);
            ls = strlen(s + 1);
            af = 0, be = 0;
            ans = 0;
            for (i = 1; i <= len && i <= ls; ++i)
            {
                af = af * seed + s[i];
            }
            ans += hashtable.Find(af);
            for (i = len + 1; i <= ls; ++i)
            {
                af = af * seed + s[i];
                be = be * seed + s[i - len];
                ans += hashtable.Find(af - be * bas);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}