最理想的查找算法是不经过任何比较，一次操作便能得到所查的数据记录。那就必须在数据记录的实际位置和它的关键字之间建立一个唯一确定的对应关系\(f\)，使每个关键字和数据集合中某个唯一的实际位置相对应。

在依据给定值\(k\)查找时，只要根据这个对应关系\(f\)可以得到给定值的像。若数据集合中存在关键字\(key\)和给定值\(k\)相等的数据记录，则数据记录必定在\(f(k)\) 所指的实际位置上。由此，不需要进行比较便可直接取得所查的数据记录。在此称这个对应关系\(f\)为哈希（Hash）函数。哈希函数的平均查找长度是1，时间复杂度是\(O(1)\) 。

哈希函数是一种运用于计算机查找算法的函数，是一个实际应用。所有针对哈希函数的讨论，均是基于整数范围内的讨论。也即：给定值\(k\)、关键字\(key\)以及\(f(k)\)应均为整数或整数序列。如果给定值\(k\)、关键字\(key\)或者\(f(k)\)不为整数（例如：浮点数、字符串、字节数组等），均可以在计算机中”转化”为适用的整数或者整数序列予以表达。

1 单调哈希函数

一个哈希函数\(f(k)\)与给定值\(k\)之间存在“一一映射”关系，则称该函数为“一一映射”哈希函数。

如果在某一个映射下，对于集合A中的不同元素，在集合B中有不同的象；而且B中的每一元素在A中都有原象，那么这个映射叫做A到B上的“一一映射”。
“一一映射”是一种特殊的映射，\(f\)：A→B满足条件：①A中不同的元素对应的象不同；②B每个元素都有原象。

在某个关键字数值区间内，随着关键字数值的增加，哈希函数\(f(k)\)单调递增或者单调递减，则称该哈希函数为单调哈希函数。单调哈希函数都是“一一映射”哈希函数。

例如：哈希函数\(f(k)=k\, mod\, n\, ( n∈N^∗ )\)，在区间内\([0,−1]\)就是单调递增函数。

定义如下哈希函数\(sqrt(k)\)：对于所有正整数关键字进行开方运算，取小数点后三位的有效数字组成新的数字。显然这个哈希函数在区间内\([0,100]\)不是单调函数。

给定值\(k\)	开方结果	\(sqrt(k)\)
0	0	0
1	1	0
2	1.414	414
3	1.732	732
4	2	0
5	2.236	236
6	2.449	449
7	2.645	645
8	2.828	828
9	3	0
10	3.162	162
……	……	……
100	10	0

2 冲突

在哈希函数中对于不同数值的关键字有可能得到同一实际地址值，即\(k_1≠k_2\)，而\(f(k_1)=f(k_2)\)。这种现象称做冲突（Collision）。

哈希函数是从关键字集合到实际地址集合的映射。通常关键字的集合比较大，包括所有可能的关键字。而实际地址集合的元素则受限于所分配的物理空间。

例如：标识符可定义为以字符为首的8位字符，则以标识符为关键字的集合大小为\(C_{26}^1 \times C_{36}^7 \times 7!≅1.09338×10^{12}\)。如将其全部记录存储，则需要的物理存储空间大约为8.75TB。显然这个数据量已经超过常规计算机内存或磁盘的存储能力。

换个角度简单点说：设有4个关键字元素，都需要映射到实际地址集合中。地址编号从1到3。那么必然有两个元素会有同一个实际地址值，与具体所选择的哈希函数无关。这个压缩映射也是”抽屉原则”的体现。

总而言之，哈希函数是一个压缩映像函数，不可避免的要产生冲突。冲突只能尽可能地减少，而不能完全避免。

3 评价哈希函数

同样的关键字集合和实际地址集合，可以有很多哈希函数可供选择。本节将讲述哈希函数的主要性质以及如何评价哈希函数。

3.1 分辨能力

定义1：分辨能力\(D\)是指关键字集合经哈希函数的映射后，所得像集合中所有不重复元素的个数。

像集合中至少要有一个元素，即\(D∈N^∗\)。例如：所有整数关键字元素都需要压缩映射到编号从0到9999的实际地址集合中。那么该哈希函数的分辨能力\(D=10000\)；对于哈希函数\(f(k)=C\)（其中为任意常数），该哈希函数的分辨能力 \(D=1\)；对于哈希函数\(f(k)=k\)，该哈希函数的分辨能力\(D=∞\)；对于哈希函数 \(f(k)=k\,mod\,n\,(n∈N^∗)\)，该哈希函数的分辨能力\(D=n\)。

分辨能力的数值越大，说明哈希函数”越好”。当分辨能力\(D=∞\)的时候，哈希函数的分辨能力最强，同时像集合所使用的实际物理空间也将是无穷大。实际应用中，是不可能有足够的资源来预先分配出所有的存储空间。因此对于分辨能力\(D=∞\)的哈希函数是没有实际应用意义的。更多地是需要在分辨能力、存储空间和时间复杂度中寻找平衡点。

性质2：对于“一一映射”哈希函数，任何两个间隔不超过其分辨能力\(D\)的关键字不可能具有完全相同的压缩映像数值。

在整数范畴内，关键字\(key\)具有一定的排列规律，且这种排列是连续的。当哈希函数是单调函数时，那么从任意给定值\(k\)起始至\((k+D−1)\)这个范围内，这样\(D\)个不同的关键字将拥有\(D\)种不同的压缩映像数值（否则就与预设条件矛盾）。也就是说，对于任意两个给定值\(k_1\)和\(k_2\)，如果间隔不超过\(D\)，就不可能获得同样的压缩映像数值。

3.2 冲突概率

定义3：两个任意给定值\(k_1\)和\(k_2\)（\(k_1≠k_2\)），导致哈希函数出现\(f(k_1)=f(k_2)\)的概率。这个概率被称作冲突概率\(\lambda\)。

根据定义1，可知哈希函数分辨能力\(D\)意味着压缩映像集合中有\(D\)种不同元素。随机选择\(N\)个不同的给定值\(k\)，经过哈希函数映射后，得到不超过\(D\)种不同状态的计数统计结果：\(C=\{c_i| i \in [1,D]\}\) 。显然\(N=\sum \limits_{i=1}^D c_i \)。

某个压缩映像元素的冲突概率\(\lambda_{c_i}\)为：

\[ \lambda_{c_i} = \lim_{N \to \infty } (\frac{c_i}{N} \cdot \frac {c_i – 1}{N – 1}) \]

该哈希函数冲突概率\(\lambda\)为：

\[ \lambda = \sum_{i=1}^{D} \lambda_{c_i} = \lim_{N \to \infty} \sum_{i=1}^{D} (\frac{c_i}{N}\cdot\frac{c_i-1}{N})= \lim_{N \to \infty} \frac{\sum_\limits{i=1}^D c_i^2}{N^2} \]

由此可以看出，对于一般哈希函数的冲突概率计算是比较复杂的。

推论4：单调哈希函数的冲突概率\(\lambda=\frac {1}{D}\) 。

对于单调哈希函数，每种压缩映像元素出现的概率都相等，均为\(\frac {1}{D}\) 。所以对于任意两个给定值\(k_1\)和\(k_2\)。出现\(f(k_1)\)的概率是\(\frac {1}{D}\)，出现\(f(k_2)\) 的概率也是\(\frac {1}{D}\)，一共有\(D\)种状态。因此哈希函数的冲突概率（即\(f(k_1)=f(k_2)\)）：

\[0≤\lambda=\frac{1}{D^2}⋅D=\frac {1}{D}≤1\]

可以由上式看出：如果一个单调哈希函数的像集合中元素的个数仅有1个，那么冲突概率就是100%；如果一个单调哈希函数的像集合中元素的个数是无穷多个，那么冲突概率就是0。

3.3 等价函数

等价函数是哈希函数中一个非常重要的概念。

判定5：两个具有相同分辨能力且每种压缩映像元素均具有相同冲突概率的哈希函数是等价函数。

严格的说：两种完全不同分辨能力的哈希算法肯定不是等价算法。但有些哈希函数随着关键字取值范围的扩大，分辨能力和每种压缩映像元素的冲突概率会相互接近。这些哈希函数被称为条件等价函数。

推论6：具有相同分辨能力或者冲突概率的单调哈希函数是等价函数。

由前面所述单调哈希函数的性质，以及判定5可以很容易证明上述推论。

如以下有两个单调哈希函数：

1. 函数1：将所有整数关键字元素压缩映射到编号从0到9999的实际地址集合中。
2. 函数2：将所有长度为8位标识符（字符串）元素缩映射到编号从0到9999的实际地址集合中。

那么函数1和函数2的分辨能力是相等的（\(D=10000\)），因此函数1和函数2是等价函数。所以评价两个单调哈希函数是否等价，主要与压缩映射后的集合元素个数有关。

对于“一一映射”哈希函数，可以通过一个取值对换表，将非单调“一一映射”哈希函数变换成为单调哈希函数。仅从这个角度来看，两者是具有等价性的。而判断两个单调哈希函数的等价性，仅需要看分辨能力是否相同即可。该方法一样适用于“一一映射”哈希函数。

4 哈希函数分类

哈希函数可以按照原始对应关系\(f\)，可以分为线性哈希函数和非线性哈希函数。其中线性哈希函数又可以分为：商数类哈希函数和余数类哈希函数。所有的哈希函数均可以通过”等价函数“的概念，简化和归纳成为：商数类哈希函数和余数类哈希函数。

4.1 线性哈希函数

线性类哈希函数是指利用整数除法作为对应关系\(f\)生成方式的哈希函数。

为了方便讨论，将不超过实数\(x\)的最大整数称为\(x\)的整数部分，记作取整函数\([x]\) （其中\(x∈R\)）。

那么一个整数数值\(k\)可以表达为：\(k=[\frac{k}{m}] \cdot m + n\)，（其中\(m \in N^*\)，\(n \in N \)）。

\([\frac{k}{m}]\)部分被成为商，\(m\)称为除数，\(n\)成为余数（也可以表达为\( n = k\, mod \, n\)）。

4.1.1 商数类哈希函数

给定一个除数序列\(M = \{ m_i | m_i \in N^* 且 m_i > 1, i \in N^*\}\)，按照如下方式对整数值求得一个结果序列\( R = \{ r_i | r_i \in N, i \in N^* \}\)。这个结果序列的“倒序”\(R^*\)就是哈希函数的结果：\(f_M (k) = R^*\)。

\[ q_1 = [\frac{k}{m_1}] \\ r_1 = k \, mod \, m_1 \\
q_2 = [\frac{q_1}{m_2}] \\ r_2 = q_1 \, mod \, m_2 \\ …… \\ q_i = [\frac{q_{i-1}}{m_i}] \\ r_i = q_{i-1} \, mod \, m_i \\ …… \\ \]

例如：\(k=9527\)，除数序列\(M=\{ 10,10,10,10\}\)。结果序列就是\(R=\{7,5,2,9\}\)，其倒序就是\(R^*=\{9,5,2,7\}\)。

显然依据上例，当除数序列\(M\)中的元素均为10时，这个哈希函数的结果就是整数数值\(k\)的十进制计数结果。

当除数序列\(M\)中的元素不完全相同时，此时哈希函数的结果可以称为变进制计数结果。在实际应用中，结果序列\(R\)和其倒序\(R^*\)均可以作为哈希函数的结果。具体使用哪一种，可以根据实际情况具体安排。

根据哈希函数的结果序列\(R\)，可以得到一个整数数值\(k^*\)：

\[ k^* = (……(q_i \times m_i + r_i) \times m_{i-1} + ……+ r_2) \times m_1 + r_1 \quad (q_i = 0,\, 0 \le r_i \le m_i)\]

实际应用中，除数序列\(M\)不可能有无限多元素，因此该哈希函数的分辨能力\(D\)就是整数数值\(k^*\)的数值范围。

\[D = \prod\limits_{i – 1}^n {m_i} = m_1 \times m_2 \times m_3 \times …… \times m_n \]

另外可以证明在区间\([0,D-1]\)内，该哈希函数为单调哈希函数，其冲突概率为\(\frac{1}{D}\)。

4.1.2 余数类哈希函数

给定一个除数序列\(M = \{ m_i | m_i \in N^* 且 m_i > 1, i \in N^*\}\)，按照如下方式对整数值求得一个结果序列\( R = \{ r_i | r_i \in N, i \in N^* \}\)。这个结果序列就是哈希函数的结果：\(f_M(k)=R\)。

\[r_1 = k \, mod \, m_1 \\ r_2 = k \, mod \, m_2 \\ …… \\ r_i = k \, mod \, m_i \\ ……\]

例如：\(k=9527\)，除数序列\(M=\{2,3,5,7,11,13\} \)。那么经哈希函数运算可以得到结果：\(R=\{1,2,2,0,1,11\}\)。

有关余数类哈希函数的分辨能力\(D\)的计算将会比较复杂，将放在后面进行讨论。此处只做一个初步的概念介绍。

另外可以证明在任意一个长度为\(D\)的关键字区间内，该哈希函数为”一一映射”哈希函数。由于”一一映射”哈希函数与单调哈希函数具有相同的性质，所以其冲突概率为\(\frac{1}{D}\)。

4.2 非线性哈希函数

非线性类指是哈希函数为非线性函数。也就是说哈希函数完全使用非线性函数，或者非线性函数和线性函数混合使用。只要哈希函数使用了非线性函数，那么就被划分至非线类。

这些非线性类对应关系可以分成两类：非线性函数和分段处理方法。

4.2.1 非线性函数

利用非线性函数构建的哈希函数被称为非线性哈希函数。这些函数主要导致映射后的像元素冲突概率发生不均衡改变，而并不能使哈希函数分辨能力的增加（甚至是减少）。

例如本文前面所定义的函数\(sqrt(k)\)。根据其描述，就可以推测这种哈希函数的分辨能力\(D \le 1000\)。因为对于任意给定值\(k∈[0,999]\)，其中的完全平方数，必然会被映射到像集合中的同一个元素上。这种哈希函数不会比线性哈希函数\(g(k)=k\, mod \, 1000\)具有更大的分辨能力\(D\)。另外在计算机中，整数运算更加简单快捷，所以这种非线性哈希函数是不会得到广泛应用的。在构建哈希算法时完全可以摒弃非线性哈希函数。

4.2.2 分段处理方法

分段处理方法就是将任意给定值\(k\)分成若干部分，针对每个部分分别建立一定的对应关系。例如：某个手机号码一共11位（13001071272），前三位130代表了运营商，后续三位0107代表的归属地，1272则是用户识别码。这样可以加快查询手机用户的数据实际存储地址。而不是在用户数据集合中逐一比较。

假设任意给定值\(k\)可以被分成段\(n\)，每段所有可能的状态个数为\(S_i\)（其中\(i∈[1,n] ，n∈N^*\)）。那么可以得出以下结论：

任何一个段的状态至少是有两个状态，或者换个角度说每一个段都是\(S_i\)进制。当所有\(S_i\)=10 时，那么其实就等价于10进制计数；当所有\(S_i\)=2 时，那么其实就等价于2进制计数；当所有\(S_i\)=26 时，那么其实就等价于26进制计数，可以相当于英文单词字母。

例如： \(k=9527\)，如果按照10进制分成四段，那么每段可以是9，5，2，7；如果按照2进制数值0010 0101 0011 0111，则可以分为16段；如果按照16进制数值2537，也可以分成四段。

由此可以发现分段对应关系可以看成是一种变进制计数方法，其与商数类哈希函数一致，完全可以将其归纳至由商数类表达方法中。

4.3 构造哈希函数

哈希函数而构建，可以是单一的哈希函数，也可以依据多个单一哈希函数组合而成。无论如何选择和构造，都必须要保证哈希函数的最终分辨能力\(D\)。

选择一组对应关系\(f_i\)（其中\(i∈[1,n]\)，\(n∈N^*\)），通过”串联”或者”并联”方式来组合出一种新的哈希函数：

\[ F_{串}(k)=f_n(f_{n−1}(f_{n−2}(……f_1(k)))) \]

或者

\[F_{并}(k)={f_1(k),f_2(k),……f_{n−1}(k),f_n(k)}\]

显然对于两种组合方式，时间复杂度均为\(O(n)\)。 \(F_{串}(k)\)的总体分辨能力取决于\(f_i\)中分辨能力的最小值。 \(F_{并}(k)\)的总体分辨能力计算较为比较复杂，但不低于\(f_i\)中分辨能力的最小值。

因此最佳的多层次构建方式只能是”单纯”的并联方式，而且这些并联方式必须”无关“。与并联形式相比，串联形式是应当被摒弃的。

在实际构建时，要使得总体分辨能力尽可能的大，层次要尽可能少（以减少平均查找长度）。

AlgMain : 整数化
AlgMain : 求原值
AlgMain : 查找长度
AlgMain : 模拟评估

知乎：哈希树（HashTree）查找算法
CSDN : 哈希树（HashTree）查找算法