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时，所有散列表操作都需要线性的运行时间，因为在这种情况下，我们希望在找到少数剩余的空槽之前，需要遍历线性数量的已经被占用的槽

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

全域散列和完全散列

局部散列

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

	插入	查找	删除
无序数组	\(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)\)