是在某次模拟赛的时候写字符串哈希被卡常了搞出来的科技，其实挺简单的，但是好像很多人不知道？
STL
众所周知，我们有 unordered_map<>
它标准，坚如磐石，对于大多数情况来说足够快（原话来自 Martin
的哈希表基准测试），但是对于某些出题人来说还是太慢了。
直接手写
众所周知，我们有如下手写哈希表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| const int MO=10000019;
struct HashMap{
int p[MO],a[MO];
int& operator[](int x){
int tmp=x%MO;
for(int i=tmp;i<MO;++i)
if(!p[i]||p[i]==x){
p[i]=x;
return(a[i]);
}
for(int i=0;i<tmp;++i)
if(!p[i]||p[i]==x){
p[i]=x;
return(a[i]);
}
}
};
|
这个哈希表非常适合用在字符串哈希这样，键值可以近似地看作完全随机的情况。但是只要数据不太随机（主要在数据结构方面）性能很容易迅速下降。
白嫖
众所周知，我们可以使用如 emhash
这样的第三方哈希表，跑得非常非常快，但是显然这个东西并不太能在合理时间内手写出来。
神秘科技
但是我们有一个不会退化的严格 无序关联结构。
考虑键值范围为 ，有
，不妨假设 ，我们开两级结构，第一级结构只有一个大小为
的桶，第二级结构为 个 大小的桶。
对于键值拆成两部分，前
位查找第一级结构的桶，若无该键值则新开一个第二级结构桶，并令第一级结构的桶的对应位置指向该桶。
对于后 位直接在前 位对应的第二级结构桶中查询即可。
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
| flowchart TB
subgraph ton[一级]
direction LR
00[0]
01[1]
02[2]
03[3]
04[4]
05[5]
06[6]
07[7]
end
subgraph ton2[二级]
subgraph 1
10[0]
11[1]
12[2]
13[2]
end
subgraph 2
20[0]
21[1]
22[2]
23[3]
end
subgraph 3
30[0]
31[1]
32[2]
33[3]
end
subgraph 4
40[0]
41[1]
42[2]
43[3]
end
subgraph 5
50[0]
51[1]
52[2]
53[3]
end
end
01 --> 1
03 --> 4
06 --> 2
04 --> 3
02 --> 5
|
查询/插入/删除均为两次寻址操作，缺点是空间占用是 的（实际上需要对 与
的空间占用具体分析，由于简单此处略过），以及遍历是
的（虽然是有序遍历，但是实在太慢了）。
在 时需要
。
看起来非常炫酷，但其实跑不过上面提到的 emhash。
1
2
3
4
5
6
7
8
9
| const int N=100010,A=7;
template<typename value>struct HashMap{
int a[1<<(32-A)],size;
value t[N][1<<A];
value& operator[](int x){
if(!a[x>>A]) a[x>>A]=++size;
return(t[a[x>>A]][x&((1<<A)-1)]);
}
};
|
Anything More Exciting?
显然上述方案差不多适用到 unsigned
键值，虽然大多数情况下是足够的，但是局限性还是很大。
扩域的方法我想了很久，在处理冲突上一直没有好的方案，直到我换了一个思路。
考虑键值 ，前 位与后 位分开处理，使用两个上述的哈希表。
先在第一个哈希表中查找前
位得到权值 （如果没有就赋一个新权值），然后在第二个哈希表查找后
位得到 （两个哈希表的权值独立）。
然后当前键值就被映射为了 ，再使用一个上述哈希表即可。
每次操作是 次寻址，空间占用为
，考虑到空间占用极大（估计常数也不小），我觉得这个东西完全没有优势区间（雾）。
个人认为最多扩域到 ，拆成前 位（直接等价的转为 ）与后 位，这样在
的时候可以把最后一个桶的键值值域缩小到 。
并且真的有用
显然，对于一些自动机，我们需要
的空间来储存，这有时候会被卡空间。于是我们把
当作键值放到上述结构中，就可以以两倍时间常数的代价换取 的空间。