是在某次模拟赛的时候写字符串哈希被卡常了搞出来的科技，其实挺简单的，但是好像很多人不知道？

STL

众所周知，我们有 unordered_map<>，它标准，坚如磐石，对于大多数情况来说足够快（原话来自 Martin 的哈希表基准测试），但是对于某些出题人来说还是太慢了。

直接手写

众所周知，我们有如下手写哈希表：

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 这样的第三方哈希表，跑的非常非常快，但是显然这个东西并不太能在合理时间内手写出来。

神秘科技

但是我们有一个不会退化的严格 $O(1)$ 无序关联结构。

考虑键值范围为 $[0,2^{32})$，有 $2^{32}=2^{32-A}2^A$，不妨假设 $2^{32-A}>N$，我们开两级结构，第一级结构只有一个大小为 $2^{32-A}$ 的桶，第二级结构为 $N$ 个 $2^A$ 大小的桶。

对于键值拆成两部分，前 $32-A$ 位查找第一级结构的桶，若无该键值则新开一个第二级结构桶，并令第一级结构的桶的对应位置指向该桶。

对于后 $A$ 位直接在前 $32-A$ 位对应的第二级结构桶中查询即可。

查询/插入/删除均为两次寻址操作，缺点是空间占用是 $2\sqrt{VN}$ 的（实际上需要对 $value$ 与 $key$ 的空间占用具体分析，由于简单此处略过），以及遍历是 $N2^A$ 的（虽然是有序遍历，但是实在太慢了）。

在 $V=2^{32},N=2^{18}$ 时需要 $256\texttt{MB}$。

看起来非常炫酷，但其实跑不过上面提到的 emhash。

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 键值，虽然大多数情况下是足够的，但是局限性还是很大。

扩域的方法我想了很久，在处理冲突上一直没有好的方案，直到我换了一个思路。

考虑键值 $[0,2^{64})$，前 $32$ 位与后 $32$ 位分开处理，使用两个上述的哈希表。

先在第一个哈希表中查找前 $32$ 位得到权值 $V_0$（如果没有就赋一个新权值），然后在第二个哈希表查找后 $32$ 位得到 $V_1$（两个哈希表的权值独立）。

然后当前键值就被映射为了 $V_0N+V_1$，再使用一个上述哈希表即可。

每次操作是 $6$ 次寻址，空间占用为 $4V^{1/4}\sqrt N+2N^{3/2}$，考虑到空间占用极大（估计常数也不小），我觉得这个东西完全没有优势区间（雾）。

个人认为最多扩域到 $[0,2^{44})$，拆成前 $12$ 位（直接等价的转为 $V_0$）与后 $32$ 位，这样在 $N=2^{20}$ 的时候可以把最后一个桶的键值值域缩小到 $[0,2^{32})$，空间占用就只比 $V=2^{32}$ 多一倍了。

感觉这样不太聪明的样子，不知道有没有什么好办法。

并且真的有用

显然，对于一些自动机，我们需要 $O(n|\Sigma|)$ 的空间来储存，这有时候会被卡空间。于是我们把 $n|\Sigma|$ 当作键值放到上述结构中，就可以以两倍时间常数的代价换取 $O(n\sqrt{|\Sigma|})$ 的空间。

有优势区间了，未来可期！（）