依据哈希函数构建的查找算法被称为哈希算法。本文前面已经归纳和总结过：哈希函数可以简化和归纳为商数类哈希函数和余数类哈希函数。那么构建哈希算法，也就主要在这两类函数中选择或由这两类函数派生。另外对于哈希函数的评价方式，同样适用于哈希算法，包括分辨能力和冲突概率。

本节中先补充前面对余数类哈希函数分辨能力\(D\)的计算，然后对比两类函数的优缺点，最后说明哈希算法的基本构建思路。

1 质数分辨定理

定理7：选取任意个互不相同的质数：\(P_1<P_2<P_3<……<P_{n−1}<P_n\)（\(n∈N^∗\)），定义：\(M = \prod\limits_{i = 1}^n {P_i}=P_1\times P_2\times P_3\times ……\times P_{n−1}\times P_n\)

设\(m≤k_1<k_2<m+M\)（\(m,k_1,k_2∈N\) ），那么对于任意的，\(i∈[1,n]\)（\(k_1\,mod\,P_i\)）＝（\(k_2\,mod\,P_i\)）不可能总成立。

证明：假设定理7的结论不正确，那么对于任意的，\(i∈[1,n]\) （\(k_1\,mod\,P_i\) ）＝（\(k_2\,mod\,P_i\) ）将总是成立。这个可以表达为： 

\[ k_1 = s_{1i} \times P_i + r_i,\, k_2 = s_{2i} \times P_i + r_i \quad (s_{1i}, s_{2i}, r_i \in N) \]

设：\(K = k_2 – k_1 = (s_{2i} – s_{1i}) \times P_i \ne 0\)

显然，\(K\)是一个合数，而且包含质因数\(P_i\)。根据质数的定义和质因数分解定理，\(K\)可以表达为：

\[K = P_1\times P_2\times P_3\times ……\times P_{n−1}\times P_n \times S \ge M \quad (S \in N^*) \]

而另外一方面，根据\(m \le k_1 < k_2 < m+M\)，可以得出\(0 < k_2 – k_1 < M \)

很明显，这两个结论是相互矛盾的。因此原定理7正确。

这个定理7可以简单的表述为：个不同的质数可以”分辨”的连续整数的个数和他们的乘积相等。”分辨”就是指这些连续的整数不可能有完全相同的余数序列。

2 余数分辨定理

在这里，对更为普遍的余数分辨方式做一个论述。

定理8：选取任意个互不相同的自然数：\( I_1<I_2<I_3<……<I_{n−1}<I_n\)（\(n∈N^∗\)），定义LCM（Lease Common Multiple）为的最小公倍数。

设\(m≤k_1<k_2<m+LCM\)（\(m,k_1,k_2∈N\)），那么对于任意的\(i∈[1,n]\) ，（\(k_1\,mod\, I_i\)）＝（\(k_2\,mod\, I_i\)）不可能总成立。

证明：假设定理8的结论不正确，那么对于任意的\(i \in [1,n]\)，（\(k_1\,mod\, I_i\)）＝（\(k_2\,mod\, I_i\)）将总是成立。这个可以表达为：

\[ k_1 = s_{1i} \times I_i + r_i,\, k_2 = s_{2i} \times I_i + r_i \quad (s_{1i}, s_{2i}, r_i \in N) \]

设：\(K = k_2 – k_1 = (s_{2i} – s_{1i}) \times I_i \ne 0\)

显然，\(K\)是一个合数，而且包含因素\(I_i\)。根据最小公倍数的定义，可以表达为：

\[K=k_2-k_1 = S \times LCM \ge LCM \quad (S \in N^*) \]

而另外一方面，根据\(m \le k_1 < k_2 < m+LCM\)，可以得出\(0 < k_2 – k_1 < LCM \)

很明显，这两个结论是相互矛盾的。因此原定理8正确。

这个定理8可以简单的表述为：个不同的数可以”分辨”的连续整数的个数不超过他们的最小公倍数。定理7是定理8的一个特例。