cover.png#Hash

散列即 hash

hash 函数就是压缩映像函数，绝大多数使用的函数都不是一一对应，会存在冲突

常用 hash 函数

• 映射应是简单的
• 应以与应该包含所有需要存储的 key
• 映射后分布概率是均等的

除留余数法

\[hash(key) = key\%p\]

关键码 \(key=100\)，表 \(m=15\)，取 \(p=13\) 这里剩余的用来解决冲突

直接定址法

线性变换

\[hash(key)=a \times key + b\]

要求 hash 地址的空间大小和关键词空间大小相同

数字分析法

设有 \(n\) 个 \(d\) 位数，每一位有 \(r\) 种不同的符号，这些符号出现频率不同，根据 hash 表的大小选取各种符号分布均匀的若干位作为散列地址，第 \(k\) 位符号分布均匀度 \(t_k\)

\[t_k = \sum_{i=1}^r(\alpha_i^k-\frac{n}{r})\]

其中 \(\alpha_i^k\) 为第 \(k\) 位上符号 \(i\) 出现的次数，\(\frac{n}{r}\) 表示各种符号在 \(n\) 个关键字中均匀出现时的次数

计算出的 \(t_k\) 越小，表示该位符号分布越均匀

平方取中法

通过求关键字的平均值扩大相近数的区别，根据表长度取中间的几位数作为 hash 函数的值

又因为一个乘积的中间几位数和乘数的每一位都相关，所以产生的散列地址比较均匀

在平方取中法中一般取散列的地址总数为2的幂次方

折叠法

将关键字分割成位数相同的几部分，最后取这几部分的叠加和（舍去进位）作为 hash 地址

比如关键码 \(key=12345678933\)，存储空间限定 \(3\) 位时 分为四组 \(123,456,678,33\)，相加或者用一些特殊的函数得到 \(hash(key)=123+456+789+033=1401\)，取后三位 \(401\) 作为散列地址

解决冲突的方法

所谓解决冲突，就是在发生冲突的时候，给要插入的节点找到另一个“空的”散列地址，即新地址上没有存放其他节点

开放定址法

\[h_i=(hash(key) + d_i + m) \%m\]

其中 \(d_i\) 为增量序列

常见有线性探测再散列、二次探测再散列、双重散列探测再散列、伪随机探测再散列

线性探测再散列：\(d_i = i\)

二次探测再散列：\(d_i = \begin{cases}[\frac{i}{2}]^2，i为奇数 \\ -[\frac{i}{2}]^2，i为偶数\end{cases}\)

双重散列探测再散列：\(d_i = i \times hash2(key)\)

相当于在 \(a\) 处发生了冲突，继续向后探测 \(d_i\) 个位置，直到找到空位置

拉链法

拉链法是一种开散列方法，即散列表的大小是可变的

它解决冲突的做法是将所有映射到同一散列地址的关键字存放在一个链表中

hash 算法复杂度分析

装载因子 \(\alpha\)，含义是表中元素个数与表长的比值

我们假设散列函数是均匀分布的，插入、查找、删除序列是随机的

成功搜索：记 \(C_n\) 为成功搜索过程中遍历的探测地址的平均数量

非成功搜索：记 \(U_n\) 为非成功搜索过程中遍历的探测地址的平均数量

解决冲突的方法	\(C_n\)	\(U_n\)	备注
线性探测	\(\frac{1}{2}(1+\frac{1}{1-\alpha})\)	\(\frac{1}{2}(1+\frac{1}{(1-\alpha)^2})\)	要求\(\alpha < 1\)
二次探测	\(-\frac{1}{\alpha}\ln(1-\alpha)\)	\(\frac{1}{1-\alpha}\)	要求\(\alpha < 1\)
伪随机探测	\(-\frac{1}{\alpha}\ln(1-\alpha)\)	\(\frac{1}{1-\alpha}\)	要求\(\alpha < 1\)
双重散列探测	\(-\frac{1}{\alpha}\ln(1-\alpha)\)	\(\frac{1}{1-\alpha}\)	要求\(\alpha < 1\)
拉链法	\(1+\frac{\alpha}{2}\)	\(\alpha+e^{-\alpha}\)	无要求

实验表明，对于开放定址法，我们应该保持\(\alpha<0.5\)

对于拉链法，我们应该保持\(\alpha<0.9\)

使用开放定址法，随着装载因子增长超过0.5并开始接近1时，散列表中的集群现象越来越严重

在极限处，当 \(\alpha\) 接近1时，所有散列表操作都需要线性的运行时间，因为在这种情况下，我们希望在找到少数剩余的空槽之前，需要遍历线性数量的已经被占用的槽

如果散列表的装载因子明显高于指定的阀值，则通常需要调整散列表的大小以重新获得新的装载因子。这个过程称为重新散列或动态散

全域散列

全域散列（Universal Hashing）通过从一个哈希函数族中随机选取哈希函数来避免对手针对特定哈希函数构造最坏情况输入

定义

设 \(\mathcal{H}\) 是一个从全域 \(U\) 到 \(\{0, 1, \ldots, m-1\}\) 的哈希函数族，若对任意不同的 \(x, y \in U\)，满足

\[\Pr_{h \in \mathcal{H}}[h(x) = h(y)] \le \frac{1}{m}\]

则称 \(\mathcal{H}\) 是一个全域散列族

直观含义：随机选取哈希函数时，任意两个不同 key 冲突的概率不超过完全随机的水平 \(\frac{1}{m}\)

构造方法

除留余数族：取一个大于 \(|U|\) 的素数 \(p\)，定义

\[h_{a,b}(k) = ((ak + b) \bmod p) \bmod m\]

其中 \(a \in \{1, 2, \ldots, p-1\}\)，\(b \in \{0, 1, \ldots, p-1\}\)

函数族 \(\mathcal{H} = \{h_{a,b} : 1 \le a < p, 0 \le b < p\}\) 是全域散列族，证明见 Introduction to Algorithms（CLRS）第 11 章

struct UniversalHash {
    long long a, b, p, m;
    
    UniversalHash(long long tableSize, long long prime) : m(tableSize), p(prime) {
        mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
        a = uniform_int_distribution<long long>(1, p - 1)(rng);
        b = uniform_int_distribution<long long>(0, p - 1)(rng);
    }
    
    int operator()(long long key) const {
        return ((__int128(a) * key + b) % p) % m;
    }
};

性能分析

使用全域散列族，对于任意 \(n\) 个 key 插入大小为 \(m\) 的表中，每个槽的期望链长为 \(\frac{n}{m} = \alpha\)

与固定哈希函数不同，全域散列的期望性能不依赖于输入数据的分布，对任何输入都能保证平均 \(O(1+\alpha)\) 的查找时间

---

完全散列

完全散列（Perfect Hashing）是一种无冲突的静态散列方案，适用于键集合事先已知且不变的场景

FKS 完全散列

Fredman、Komlós 和 Szemerédi（1984）提出的二级散列方案

第一级：使用全域哈希 \(h\) 将 \(n\) 个 key 映射到 \(m = n\) 个桶中，设第 \(j\) 个桶中有 \(n_j\) 个 key

第二级：对每个桶 \(j\)，使用一个独立的全域哈希 \(h_j\) 将该桶中的 \(n_j\) 个 key 映射到大小 \(m_j = n_j^2\) 的子表中

由生日悖论，当子表大小为 \(n_j^2\) 时，随机选取的全域哈希函数产生冲突的概率小于 \(\frac{1}{2}\)，因此期望只需常数次随机选取即可找到无冲突的哈希函数

空间分析：总空间为 \(\sum_{j=0}^{m-1} n_j^2\)。可以证明，当第一级使用全域哈希时，\(E[\sum n_j^2] < 2n\)

因此 FKS 完全散列的总空间为 \(O(n)\)，查询时间为 \(O(1)\) 最坏情况

struct PerfectHash {
    int m;
    vector<UniversalHash> secondLevel;
    vector<vector<pair<long long, int>>> table;
    
    void build(vector<long long>& keys, long long p){
        int n = keys.size();
        m = n;
        // 第一级哈希
        UniversalHash h1(m, p);
        vector<vector<long long>> buckets(m);
        for(auto key : keys) buckets[h1(key)].push_back(key);
        
        // 第二级哈希
        table.resize(m);
        secondLevel.resize(m, UniversalHash(1, p));
        for(int j = 0; j < m; ++j){
            int nj = buckets[j].size();
            if(nj == 0) continue;
            int mj = nj * nj;
            table[j].resize(mj, {-1, -1});
            // 反复随机选取直到无冲突
            bool ok = false;
            while(!ok){
                secondLevel[j] = UniversalHash(mj, p);
                ok = true;
                fill(table[j].begin(), table[j].end(), make_pair(-1LL, -1));
                for(auto key : buckets[j]){
                    int pos = secondLevel[j](key);
                    if(table[j][pos].first != -1){ ok = false; break; }
                    table[j][pos] = {key, 0};
                }
            }
        }
    }
};

最小完美散列

最小完美散列（Minimal Perfect Hashing, MPH）在完全散列的基础上要求表的大小恰好为 \(n\)，即空间利用率为 \(100\%\)

常见算法有 CHD（Compress, Hash, and Displace）和 BDZ/BMZ 算法，它们可以在 \(O(n)\) 时间内构造，查询 \(O(1)\)，空间接近信息论下界

---

局部敏感散列

局部敏感散列（Locality-Sensitive Hashing, LSH）用于高维数据的近似最近邻搜索

与传统哈希追求冲突最小化相反，LSH 希望相似的数据被映射到同一个桶中

定义

一个哈希函数族 \(\mathcal{H}\) 称为 \((d_1, d_2, p_1, p_2)\)-敏感的（其中 \(d_1 < d_2\)，\(p_1 > p_2\)），若对任意 \(x, y\)

• 若 \(d(x, y) \le d_1\)，则 \(\Pr_{h \in \mathcal{H}}[h(x) = h(y)] \ge p_1\)
• 若 \(d(x, y) \ge d_2\)，则 \(\Pr_{h \in \mathcal{H}}[h(x) = h(y)] \le p_2\)

其中 \(d(\cdot, \cdot)\) 为距离度量

常见方法

随机超平面法（SimHash）：用于余弦相似度，取随机向量 \(r\)，定义 \(h_r(x) = \text{sign}(r \cdot x)\)

\[\Pr[h_r(x) = h_r(y)] = 1 - \frac{\theta(x,y)}{\pi}\]

其中 \(\theta(x,y)\) 为 \(x,y\) 之间的夹角

Min-Hash：用于 Jaccard 相似度，对元素进行随机排列 \(\pi\)，定义 \(h_\pi(S) = \min_{s \in S} \pi(s)\)

\[\Pr[h_\pi(A) = h_\pi(B)] = \frac{|A \cap B|}{|A \cup B|} = J(A, B)\]

放大技巧

为了增大 \(p_1\) 和 \(p_2\) 之间的间隔，使用 AND-OR 放大

• AND 构造（\(k\) 个哈希取交集）：\(p_1^k\) 和 \(p_2^k\)，同时降低两个概率
• OR 构造（\(L\) 个独立组取并集）：\(1-(1-p)^L\)，同时提高两个概率

组合使用 \(k\) 个哈希做 AND，\(L\) 组做 OR，查询时间为 \(O(L)\) 次哈希计算加桶内遍历

LSH 在信息检索、推荐系统、图像搜索等领域有广泛应用

Locality-sensitive hashing - Wikipedia

散列和其他数据结构的对比

	插入	查找	删除
无序数组	\(O(n)\)	\(O(n)\)	\(O(n)\)
有序数组	\(O(n)\)	\(O(\log n)\)	\(O(n)\)
无序链表	\(O(n)\)	\(O(n)\)	\(O(n)\)
有序链表	\(O(n)\)	\(O(n)\)	\(O(n)\)
平衡树	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)
散列	\(O(1)\)	\(O(1)\)	\(O(1)\)