ZJU_DS_11-散列查找

Posted on | Edited on | In ,
| 12k | 1:40

本周将介绍散列查找

引子

先来回顾一下其他的查找方法：

名称 时间复杂度
顺序查找 $O(N)$
二分查找（静态查找） $O(log_2N)$
二叉搜索树 $O(h), h$为树高
平衡二叉树 $O(log_2N)$

上表中的查找方法都是建立在容易比较关键字的情况下，如果关键字不容易比较呢？

散列查找

散列查找所要解决的问题就是：

  1. 计算位置：构造散列函数确定关键词存储位置
  2. 解决冲突：应用某种策略解决多个关键词位置相同的问题

按照散列查找的做法，每次查找只进行计算就够了，时间复杂度为$O(1)$，也就是说查找时间与问题规模无关！

抽象数据类型描述

类型名称：符号集（Symbol Table）
数据对象集：符号表是“名字（Name）- 属性（Attribute）”对的集合
操作集：Table ∈ Symbol Table, Name ∈ NameType, Attr ∈ AttributeType

  1. SymbolTable InitializeTable(int TableSize)，创建一个长度为TableSize的符号表
  2. Boolean IsIn(SymbolTable Table, NameType Name)，查找特定的名字Name是否在符号表Table中
  3. AttributeType Find(SymbolTable Table, NameType Name)，获取Table中指定名字Name对应的属性
  4. SymbolTable Modefy(SymbolTable Table, NameType Name, AttributeType Attr)，将Table中指定名字Name的属性修改为Attr
  5. SymbolTable Insert(SymbolTable Table, NameType Name, AttributeType Attr)，向Table中插入一个新名字Name及其属性Attr
  6. SymbolTable Delete(SymbolTable Table, NameType Name)，从Table中删除一个名字Name及其属性

基本思想

散列（Hashing）的基本思想如下：

  1. 以关键字$key$为自变量，通过散列函数$h$，计算出对应的函数值$h(k)$，作为数据对象的存储地址。
  2. 可能不同关键字会映射到同一散列地址上，这种情况称为冲突（Collision），这需要某种冲突解决策略。

这里引入装填因子(Loading Factor)的概念，即：散列表内元素个数（$n$）与散列表空间（$m$）的比值，即$\alpha = n / m$。

散列函数

按照前面的思路，在构造散列函数时需要注意两点：

  1. 计算简单，以便提高地址转换速度
  2. 关键词对应的地址空间分布均匀，以尽量减少冲突

根据数据元素的不同，可以分为以数字关键词和字符关键词构造的散列函数。

数字关键词

以数字为关键词的散列函数构造方法又有多种，依次如下：

名称 散列函数
直接定址法 $h(key) = a \times key + b, a, b$为常数
除留余数法 $h(key) = key mod p, p$取素数
数字分析法 $h(key) = atoi(key + 7)$
折叠法 关键词分割成位数相同的几个部分叠加
平方取中法 关键字平方后取其中几位

字符关键词

以字符为关键词的散列函数构造也有多种，依次如下：

散列函数：$h(key) = (\sum key[i])\ mod\ TableSize$，此法产生的冲突较为严重

散列函数：$h(key) = (key[0] \times 27^2 + key[1] \times 27 + key[2])\ mod\ TableSize$，这里看作 27 进制数，依然存在冲突，

散列函数：$h(key) = (\sum_{i=0}^{i-1} key[n-i-1] \times 32^i)\ mod\ TableSize$，看作 32 进制数涉及关键词，所有n个字符，并且分布比较均匀

1
2
3
4
5
6
7
Index Hash(const char *Key, int TableSize) {
    unsigned int h = 0;
    while(*Key != ‘\0’) {
        h = (h << 5) + *Key++;    // h << 5 <==> h*32
    }
    return h%TableSize;
}

冲突处理方法

对于散列查找而言，产生冲突必定会影响效率，那么如何处理冲突呢？

开放定址法

开放定址法的思路比较简单，说白了，就是这个不行换另外一个，一旦产生了冲突（该地址已有其它元素），就按照某种规则寻找另一个空的地址。
按照这种思路，寻找下一空地址的过程，称为探测，而它也有多种不同的探测方法。

线性探测

顾名思义，线性探测法就是线性的探测法（说了没说系列？😏），也即以增量序列${1, 2, \ldots}（TableSize - 1）$循环试探下一个地址，也就是检测到冲突了，下标加一试试下一个地址，注意循环到末尾后若还没有空位置，则继续从头部开始循环，此法容易产生“聚集”现象。

平方探测

平方探测也叫二次探测，以增量序列${1^2, -1^2, 2^2, -2^2, \ldots, q*2, -q^2}, q \le \lfloor TableSize \rfloor$，循环试探下一个存储地址，此法与线性探测唯一的区别只是增量序列不同而已。但平方探测存在一个很严重的问题，就是“抖动”现象，明明有空位置，但是就是无法探测到散列表的空位置，不过好在可以借助下面这个定理（感谢数学家🙇‍）。

定理：如果散列表长度TableSize是某个$4k+3$（$k$是正整数）形式的素数时，平方探测就可以探查到整个散列表空间。

双散列

顾名思义，双散列，就是产生冲突了，再进行一次散列，两次散列的散列函数不同，而是第一次散列的结果将作为第二次散列的key，也即$d_i$为$i \times h_2(key)$，其探测序列为$h_2(key),\ 2h_2(key),\ 3h_2(key), \ldots$，很明显，对任意的key，$h_2(key) \neq 0$，为保证所有的散列存储单元都可以被探测到，$h_2$选为$h_2(key) = p - (key\ mod\ p)$，$p,\ TableSize$都是素数。

再散列

当散列表元素太多（即装填因子$\alpha$太大）时，查找效率会下降，实际最大装填因子一般取$0.5 \le \alpha \le 0.85 $，对应的解决办法就是加倍扩大散列表，这个过程就叫做“再散列（Rehashing）”，注意，再散列时，原先的散列序列不是简单的复制，而是要重新计算。

分离链接法

分离链接法最终产生的结构有点类似图的邻接表，其基本思想就是将相应位置上冲突的所有关键词存储在同一个单链表中，也就是说这种结构需要一个数组，并且数组内每个元素除了表示关键字还得有一个指针域，用来将链表串起来。

性能分析

对于查找而言，衡量其效率的指标，依然是平均查找长度（ASL，分查找成功和不成功两种），平均查找长度的计算方法要视具体的散列方法而定。另外，影响产生冲突多少有以下三个因素：

  1. 散列函数是否军运
  2. 处理冲突的方法
  3. 散列表的装填因子$\alpha$

下面直接给出其期望探测次数 p，不做深入的数学探讨。

  • 线性探测法：
    $p =
    \begin{cases} \frac{1} {2} [1+\frac{1} {(1-\alpha)^2}],
    & \text {对插入和不成功查找而言} \\
    \frac{1}{2}[1+\frac{1}{(1-\alpha)}],
    & \text {对成功查找而言}
    \end{cases}$
  • 平方探测法：
    $p =
    \begin{cases} \frac{1} {(1-\alpha)},
    & \text {对插入和不成功查找而言} \\
    \frac{-1} {\alpha} ln(1-\alpha),
    & \text {对成功查找而言}
    \end{cases}$
  • 分离链接法：
    $p =
    \begin{cases} \alpha + e^{-\alpha},
    & \text {对插入和不成功查找而言} \\
    1+ \frac{\alpha} {2},
    & \text {对成功查找而言}
    \end{cases}$

根据上面的公式我们可以得出下面几点结论：

  1. 当装填因子$\alpha < 0.5$时，各种探测法的期望探测次数都不大
  2. 随着$\alpha$的增大，线性探测法的期望探测次数增加较快，不成功查找和插入操作的期望探测次数比成功查找的期望探测次数要大
  3. 合理的最大装填因子$\alpha$应该不超过0.85

总结

散列查找的优点很明显，选择合适的散列函数，散列查找效率的期望是常数$O(1)$，它几乎与关键字的空间的大小$n$无关，也适合于关键字直接比较计算量过大的问题；但它是以较小的$\alpha$为前提，是一个以空间换时间的查找方法；另外，它对关键字的存储是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大、最小值查找。

开放定址法的存储效率很高，但是存在“聚集”现象；分离链接法是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低，关键字的删除不需要“懒惰删除（不断链，只标记为空）”，从而没有存储“垃圾”，但太小的$\alpha$可能导致空间浪费，大的$\alpha$又将付出更多的时间代价，且不均匀的链表长度会导致时间效率的严重下降。

Homework

11-1 电话聊天狂人

这个题姥姥已经讲过了，直接用姥姥的代码有点麻烦，借助 C++ 的 MAP 和散列的思想，可以很轻松的解决这个问题。

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
#include <iostream>
#include <string>
#include <map>
using namespace std;
const int maxn = 2000000 + 5;
map<string, int> phonenum2num;
map<int, string> num2phonenum;
int times[maxn] = { 0 }, n, index = 1;
int main() {
    cin >> n;
    string num;
    for (int i = 0; i < 2 * n; i++) {
        cin >> num;
        int tmp = phonenum2num.find(num)->second;
        if (!tmp) {
            phonenum2num[num] = index;
            num2phonenum[index] = num;
            times[index] = 1;
            index++;
        } else {
            times[tmp]++;
        }
    }
    int max = times[1], maxindex = 1, count = 1;
    string madman = num2phonenum.find(1)->second;
    for (int i = 2; i < index; i++) {
        if (times[i] > max) {
            max = times[i];
            maxindex = i;
            madman = num2phonenum.find(i)->second;
        } else if (times[i] == max) {
            if (num2phonenum.find(i)->second < num2phonenum.find(maxindex)->second) {
                maxindex = i;
                madman = num2phonenum.find(i)->second;
            }
            count++;
        }
    }
    if (count == 1) cout << madman << ' ' << max;
    else cout << madman << ' ' << max << ' ' << count;
    return 0;
}

/*
samples:
in:
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832
out:
13588625832 3

*/

11-2 Hashing

本题考察散列查找的冲突处理方法，题目很直白的告诉了处理冲突的方法是平方探测法，但题目要求的平方探测只会用正整数探测。这方面的知识，课上何老师已经讲的很清楚了，不过这个题的难点在于如何处理无法进行散列的数。

由于题目告诉了只会用正整数探测，其实算是变相的告诉你了，只要经过散列函数得到的下标值大于散列表长度，就认为无法存放了，也就是说并不会循环试探，明白这点后就好办了。

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
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 20000 + 10;
bool hashTable[maxn] = { 0 };
bool isprime(int n) {
    if (n <= 1) return false;
    else {
        int tmp = (int)sqrt(n);
        for (int i = 2; i <= tmp; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}
int nextprime(int m) {
    while (!isprime(m)) m++;
    return m;
}
int hashfunc(int num, int hashkey) {
    return num % hashkey;
}
int main() {
    int m, n, tmp;
    cin >> m >> n;
    m = nextprime(m);
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        int index = hashfunc(tmp, m);
        if (hashTable[index] == false) {
            hashTable[index] = true;
            if (i == 0) cout << index;
            else cout << ' ' << index;
        } else {
            int step;
            for (step = 1; step < m; step++) {
                index = hashfunc(tmp + step * step, m);
                if (hashTable[index] == false) {
                    hashTable[index] = true;
                    if (i == 0) cout << index;
                    else cout << ' ' << index;
                    break;
                }
            }
            if (step >= m) {
                if (i > 0) cout << ' ';
                cout << '-';
            }

        }
    }
    return 0;
}

/*
samples:
in:
4 4
10 6 4 15
out:
0 1 4 -

in:
5 5
10 6 4 15 25
out:
0 1 4 - -

in:
5 5
5 10 6 4 15 
out:
0 1 2 4 -

in:
1 1
1
out:
1

*/

11-3 QQ 账户的申请与登陆

这题用 MAP 简直太容易了，要是全部自己写，代码量略大。

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
#include <iostream>
#include <string>
#include <map>
using namespace std;
map<string, string> qqnum;
int main() {
    int n;
    char ope;
    cin >> n;
    string tmp_num, tmp_pass;
    for (int i = 0; i < n; i++) {
        cin >> ope >> tmp_num >> tmp_pass;
        map<string, string>::iterator it;
        it = qqnum.find(tmp_num);
        switch (ope) {
            case 'L': {
                if (it == qqnum.end()) {
                    cout << "ERROR: Not Exist" << endl;
                } else {
                    if (it->second == tmp_pass) {
                        cout << "Login: OK" << endl;
                    } else cout << "ERROR: Wrong PW" << endl;
                }
                break;
            }
            case 'N': {
                if (it != qqnum.end()) {
                    cout << "ERROR: Exist" << endl;
                } else {
                    qqnum[tmp_num] = tmp_pass;
                    cout << "New: OK" << endl;
                }
                break;
            }
            default: break;
        }
    }
    return 0;
}

/*
samples:
in:
5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com
out:
ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK

*/

11-4 Hashing - Hard Version

这个题的意思很直观，就是给定一个用线性探测法构建的散列表，然后要根据这个得到数字序列的输入顺序。

这个题看起来很容易，其实有点难想。因为就样例而言，33 和 1 都有可能是第一个输入的，该怎么确定数字的输入顺序其实就是难点。

一般而言，做一道题时，想到的都是跟这个题相关的知识。但是这个题，确定输入顺序其实需要用到拓扑排序的知识。

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
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
const int maxn = 1000 + 3;
vector<int> AdjL[maxn];
int n, hashTable[maxn], elements = 0;
bool isvis[maxn] = {false};
map<int, int> value2index;
map<int, int> index2value;
void toposort() {
    int indegree[maxn] = {0};
    for(int v = 0; v < n; v++) {
        for(int w = 0; w < AdjL[v].size(); w++) {
            indegree[AdjL[v][w]]++;
        }
    }
    priority_queue<int, vector<int>, greater<int> > q;
    for(int i = 0; i < n; i++) {
        if(indegree[i] == 0 && hashTable[i] >= 0) {
            q.push(hashTable[i]);
        }
    }
    int count = 0;
    while(!q.empty()) {
        int tmp = q.top();
        q.pop();
        cout << tmp;
        if(count < elements - 1) {
            cout << ' ';
            count++;
        }
        int v = value2index[tmp];
        for(int w = 0; w < AdjL[v].size(); w++) {
            indegree[AdjL[v][w]]--;
            if(indegree[AdjL[v][w]] == 0) q.push(hashTable[AdjL[v][w]]);
        }
    }
}
int main() {
    cin >> n;
    memset(hashTable, -1, sizeof(hashTable));
    for(int i = 0; i < n; i++) {
        cin >> hashTable[i];
    }
    for(int i = 0; i < n; i++) {
        if(hashTable[i] < 0) continue;
        value2index[hashTable[i]] = i;
        index2value[i] = hashTable[i];
        elements++;
        int tmp = hashTable[i];
        int index = tmp % n;
        if(hashTable[index] == hashTable[i] && index == i) continue;
        else {	
            bool flag = true;
            queue<int> q;
            for(; index < n || flag; index++) {
                if(flag && index >= n) {
                    index %= n;
                    flag = false;
                }
                if(hashTable[index] == tmp) break;
                q.push(index);
            }
            while(!q.empty()) {
                int front = q.front();
                q.pop();
                AdjL[front].push_back(index); 
            }
        }
    }
    toposort();
    return 0;
}

Buy me a coffee ? :)
0%