10.哈希与字典树

发表于 更新于 分类于 ，

哈希与字典树

哈希（Hash）也叫散列，记录存储位置与关键字之间存在对应关系 \(Loc(i)=H(key_{i})\)，从而在查找数据时可以接近 \(O(1)\) 的效率直接找到位置，而不需要顺序摸排或二分查找。

哈希函数自由度很高，能完成数据范围到哈希表范围的映射就可以，映射之后有概率产生冲突，通过一定手段解决冲突即可。

工程应用中，MD4、SHA-1、SHA-256、SHA-512 等都是哈希算法。

链表法处理哈希冲突

哈希表每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中

1
2
3
4
5
6
7
8
9
list<int> hl[maxn];
int Find(int x) {
    int ith = 0, hsNum = x % maxn;
    list<int>::iterator jt;
    for(jt = hl[hsNum].begin(); jt != hl[hsNum].end(); jt ++, ith ++) {
        if(*jt == x) break;
    }
    return jt == hl[hsNum].end() ? (hl[hsNum].push_front(x), -1) : ith + 1;
}

STL 的 map 与 unorderd_map

C++ 的 STL 利用红黑树封装了 \(O(logn)\) 的 map 映射，以及一套哈希方案封装的接近\(O(1)\)的 unordered_map 映射，用起来很方便。

1
2
3
std::unordered_map<string, int> mp;
mp["bob"] = 5;
mp["alice"] = 6;

不同版本的C++，unordered_map内部实现不尽相同，一些题目可能会专门Hack unordered_map 导致其退化不再是 \(O(1)\)，所以比赛中如果理论复杂度用map没问题的话，还是推荐用map。

字典树

字典树是针对“串”类数据结构的哈希方案，比如对小写英文字符串做哈希，可以构建一个“26叉树”，将任意单词从左到右在树上进行分支查找，完成匹配。

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
const int maxn = 1100;
struct Node {
    int cnt;
    int nex[26];
};
Node trie[maxn];
int tp;
char buf[11];
int n;
void Insert(int now, char *b) {
    trie[now].cnt ++;
    if(!*b) return;
    if(!trie[now].nex[*b - 'a'])
    trie[now].nex[*b - 'a'] = tp ++;
    Insert(trie[now].nex[*b - 'a'], b + 1);
}
int Search(int now, char *b) {
    // 统计以输入字符串为前缀的单次个数
    // 对于其他任务（比如统计多少个单次是输入字符串的前缀）
    // 改变cnt的意义并维护对应值
    int nex = trie[now].nex[*b - 'a'];
    if(!*b) return trie[now].cnt;
    if(!nex) return 0;
    return Search(nex, b + 1);
}

思考题

  1. 给n个单词，和1个长单词，求有多少个单词是这个长单词的前缀 —— 用 n 个单词建字典树，节点统计单词个数，长单词去匹配，路径上个数求和
  2. 给n个单词，和1个短单词，求这个短单词是多少个单词的前缀 —— 用 n 个单词建字典树，节点统计单词个数，短单词匹配成功的节点个数为答案
  3. 给两种语言单词对照表，输入任意单词，输出对照另一个语言的单词