数据结构与算法（七）—— 散列表结构及其实现和应用

谁践踏了优雅 2023-06-25 08:13 45阅读 0赞

注：本篇内容参考了《Java常用算法手册》、《大话数据结构》和《算法导论（第三版）》三本书籍。并参考了百度百科。

本人水平有限，文中如有错误或其它不妥之处，欢迎大家指正！

**目录**

1. 散列技术

1.1 直接寻址表

1.2 散列表

1.3 散列技术

1.3.1 简介

1.3.2 完全哈希

1.4 散列过程

1.5 与其它数据结构的不同

2 散列函数

2.1 好的散列函数原则

2.1.1 计算简单

2.1.2 散列地址分布均匀

2.1.3 独立于数据可能可在的任何模式

2.2 散列函数方法

2.2.1 直接定址法

2.2.2 数字分析法

2.2.3 平方取中法

2.2.4 折叠法

2.2.5 除留余数法

2.2.6 随机数法

2.2.7 除法散列法

2.2.8 乘法散列法

2.2.9 全域散列法

2.2.10 使用总结

3 哈希冲突

3.1 哈希冲突

3.2 冲突解决方法

3.2.1 链接法

3.2.2 开放寻址法

3.2.3 再散列法

3.2.4 公共溢出区法

3.3 哈希算法不可逆

4. 散列表的查找

4.1 查找算法实现

4.1.1 初始化

4.1.2 插入散列

4.1.3 查找

4.2 查找性能

4.2.1 散列函数是否均匀

4.2.2 处理冲突的方法

4.2.3 散列表的装载因子

5. 常用的散列算法

5.1 MD4

5.2 MD5

5.3 SHA-1及其他

6. Java中的散列表

7.  散列表应用

7.1 文件检验

7.2 数字签名

7.3鉴权协议

7.4 实际应用

--------------------

# 1. 散列技术 #

在实际应用中，许多应用都需要一种动态集合结构，它至少要支持插入、查找和删除这样的字典操作。比如，用于程序语言编译的编译器维护了一个符号表，其中元素的关键字为任意字符串，它与程序中的标识符对应。

散列表（Hash Table）是实现字典操作的一种有效数据结构。尽管在最坏情况下，散列表中查找一个元素的时间与链表中查找的时间相同，时间复杂度为O(n)。然而在实际应用中，散列表查找的性能是极好的。在一些合理的假设下，在散列表中查找一个元素的平均时间是O(1)。

散列表是普通数组概念的推广。由于对普通数组可以直接寻址，使得能在O(1)时间内访问数组中的任意位置。若存储空间允许，可以提供一个数组，为每个可能的关键字保留一个位置，以利用直接寻址技术的优势。

当实际存储的关键字数量比全部的可能关键字总数要小时，采用散列表就成为直接数组寻址有一种有效替代。因为散列表使用一个长度与实际存储的关键字数量成比例的数组存储。在散列表中，不是直接把关键字作为数组的下标，而是根据关键字计算出相应的下标。

然而，在根据关键字计算下标时可能会出现冲突，就是常说的哈希冲突。这样会使多个关键字映射到数组的同一个下标，本篇后面会说明如何去解决这种冲突。

【说明】：直接寻址、立即寻址和间接寻址，只是CPU在通过总线与内存交互时的不同交互方法而产生的三种概念。直接寻址就是在指令格式的地址的字段中，直接给出操作数在内存地址，因为操作数的地址直接给出而不需要经过某种变换，故有此称谓。间接录址是相对于直接录址而言的，指令地址字段的形式地址D不 是操作数的真正地址，而是操作数地址的指标器，或说是D单元的内容才是操作数的有效地址。立即寻址：编程语言中的一种寻址方式，将操作数紧跟在操作码后，与操作码一起放在指令代码段中，在程序运行时，程序直接调用该操作数，而不需要到其它地址单元中去取相应的操作数，上述的写在指令中的操作数也称作立即数。

## 1.1 直接寻址表 ##

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都是取自于全域U = \{0，1，…，m-1\}中的一个关键字，这里m不是一个很大的数。另外，假设没有两个元素具有相同的关键字。

为表示动态集合，我们用一个数组，或称为直接寻址表（direct-address table），记为T\[0..m-1\]。其中每个位置，或称为槽（slot），对应全域U中的一个关键字。如下图。槽k指向集合中一个关键字为k的元素。若该集合中没有关键字为k的元素，则T\[k\]=NULL。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70][]

在上图中，全域U = ｛0，1，…，9｝中的每个关键字都对应于表中的一个下标值，由实际关键字构成的集合K=｛2，3，5，8｝决定表中的一些槽，这些槽包含元素的指针。而另一些槽包含NULL，用深阴影表示。其中，卫星数据可以认为是除了关键字k以外的其它数据，因为这里重点关心的是k，其它数据应该会像卫星一样围绕着k走。

对于某些应用，直接寻址表本身就可以存放动态集合中的元素。也就是说，并不是把每个元素的关键字及其卫星数据都放在直接寻址表外部的一个对象中，再由表中某个槽的指针指向该对象，而是直接把该对象存放在表的槽中，从而节省了空间。使用对象内的一个特殊关键字来表明该槽为空槽。而且，通常不必存储该对象的关键字属性，因为若知道一个对象在表中的下标，就可以得到它的关键字。然而，若不是存储关键字，就必须有某种方法来确定某个槽是否为空。

## 1.2 散列表 ##

从上面的描述可以看出，直接寻址技术的缺点非常明显：若全域U很大，则在一台标准的计算机可用内存容量中，要存储大小为|U|的一张表T也许不太实际，甚至是不可能的。还有，实际存储的关键字集合K相对U来说可能很小，使得分配给T的大部分空间都被浪费掉。

当存储在字典中的关键字集合K比所有可能的关键字的全域U要小许多时，散列表需要的存储空间要比直接发址表少得多。特别地，能将散列表的存储需要降至![\\Theta (|K|)][Theta _K]，同时散列表中查找一个元素的优势仍得到保持，只需要O(1)的时间。问题是这个界是针对平均情况时间的，而对直接寻址来说，它是适用于最坏情况时间的。

在直接寻址方式下，具有关键字k的元素被放在槽k中。在散列方式下，该元素存放在槽h(k)中；即利用散列函数（hash  function）h，由关键字k计算得到槽的位置。这里函数h将关键字的全域U映射到散列表（hash  table）T\[0..m-1\]的槽位上。

![h:U\\rightarrow \\left \\\{ \\left. 0, 1, ..., m-1\\right \\\} \\right.][h_U_rightarrow _left _ _left. 0_ 1_ ..._ m-1_right _ _right.]

这里散列表的大小m一般要比|U|小很多。可以说一个具有关键字k的元素被散列到槽![h(k)][h_k]上，也可以说![h(k)][h_k]是关键字k的散列值。下图描述了这个基本方法。散列函数缩小了数组下标的范围，即减少了数组的大小，使其由|U|减小为m。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 1][]

散列是一种极其有效和实用的技术：基本的字典操作平均只需要O(1)的时间。

## 1.3 散列技术 ##

### 1.3.1 简介 ###

先看一个生活中的例子。以前在上学的时候，如果家长要来学校找一个人，那时学校基本上没有软件系统，找起来很麻烦，学校可能是根据登记的名册一个一个的找，相当于通过名字顺序查找学校的人。假如你问的人刚好知道这个人，他就直接告诉你那个人的位置甚至可以带你去找那个人。这就相当于通过某个函数，没有遍历，也没有比较，使得

![20200101215324994.png][]

这样我们可以通过查找的关键字不需要比较就可以获得需要的记录的位置。这就是一种新的存储技术——散列技术。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。

把这种对应关系 f 称为散列函数，又称哈希（Hash）函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。

### 1.3.2 完全哈希 ###

完美哈希是当关键字和值是静态时，可以使得在最差情况下的查询性能也相当出色。所谓静态，就是指一旦各关键字存入表中，关键字集合就不再变化了。实际应用中，有很多地方都用到了静态的关键字集合，比如一种语言的保留字集合，还有一张CD-ROM里的文件名集合。完美哈希可以在最坏情况下以O(1)查找，且性能非常的出色，下文中有些地方也会提到。其结构如下图。

![70][]

利用完全散列技术来存储关键字集合K = ｛10，22，37，40，52，60，70，72，75｝。外层的散列函数为![h(k) = ((ak + b)][h_k_ _ _ak _ b]  ![mod][]  ![p][]![)][gif.latex_5Cdpi_7B120_7D_20_29]  ![mod][]  ![m][]，这里 a = 3，b = 42， p = 101，m = 9。例如，![h(75) = 2][h_75_ _ 2]，因此，关键字75散列到表T的槽2中。一个二级散列表![S\_\{j\}][S_j]中存储了所有散列表到槽 j 中的关键字。散列表![S\_\{j\}][S_j]的大小为![m\_\{j\}][m_j] = ![n\_\{2\}^\{j\}][n_2_j]，并且相关的散列函数为![h\_\{j\} (key) = ((a\_\{j\}k + b\_\{j\})][h_j_ _key_ _ _a_j_k _ b_j]  ![mod][]  ![p][]![)][gif.latex_5Cdpi_7B120_7D_20_29] ![mod][]  ![m\_\{j\}][m_j]。因为![h\_\{2\}(75) =7][h_2_75_ _7]，故关键字75被存储在二级散列表![S\_\{2\}][S_2]的槽中。二级散列表没有冲突，因而查找操作在最坏情况下所需要的时间为常数。

它采用两级的散列方法来设计完全散列方案，在每一级上都使用全域散列。第一级和带链表的哈希基本上是一样的：利用从某一处全域散列函数簇中仔细选出的一个散列函数h，将 n 个关键字散列到 m 个槽中。

但为了确保在第二级上不出现冲突，需要让散列表![S\_\{j\}][S_j]的大小![m\_\{j\}][m_j]为散列到槽 j 中的关键字![n\_\{j\}][n_j]的平方。尽管![m\_\{j\}][m_j]对![n\_\{j\}][n_j]的这种二次依赖看上去可能使得总体存储需求很大，但通过适当的选择第一级散列函数，可以将预期使用的总体存储空间限制为O(n)。

采用了一个较小的二次散列表![S\_\{j\}][S_j]及相关的散列函数![h\_\{j\}][h_j]，而不是将散列到槽 j 中的所有关键字建立一个链表。利用精心选择的散列函数![h\_\{j\}][h_j]，可以确保在第二级上不出现冲突。

只是第一级在发生冲突后，后面接的不是链表，而是一个新的哈希表。后面的哈希结构，可以看到前端存储了一些哈希表的基本性质：

1.  m 哈希表槽数；
2.  a, b全域哈希函数要确定的两个值（一般是随机选择然后确定下来的），后面跟着哈希表。

为了保证不冲突，每个二级哈希表的数量是第一级映射到这个槽中元素个数的平方，这样可以保证整个哈希表非常的稀疏。

需要处理两个问题：首先要确定如何才能保证第二级散列表中不发生冲突。其次要说明使用总体存储空间的期望数O(n)，这里包含主散列表和所有的二级散列表所占的空间。

如果一个全域散列函数类中随机选出散列函数h，将 n 个关键字存储在一个大小为![m = n^\{2\}][m _ n_2]的散列表中，那么表中出现冲突的概率小于1/2。在《算法导论》中这是一个定量，证明过程这里不论述了。

## 1.4 散列过程 ##

整个散列过程其实比较简单，也比较好理解，一共就两步。

第一步，在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。

比如要存储学生小明的信息，关键字就是小明的学号123456，当然也可以是名字，但名字可能会有重复的。根据散列函数对小明的学号123456进行计算，得到一个地址3-2-4-8（这里是举例，所以地址是自己定义的，其意思是小明的位置是在3年级2班教室的第4排第8列），这个地址就是小明在学校的位置。就像居里夫人，就让她在化学实验室，巴顿将军就在战场，当然你可让他在网吧。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 2][]

第二步，当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。就是上一步在哪存的，这里就上哪去找，由于存取用的是同一个散列函数，因此结果自然也是相同的。上一步说明小明的地址是3-2-4-8，这里在查找时会提供小明的学号123456，根据散列函数计算得出小明的位置仍然是3-2-4-8，这样就找到小明的位置了。

所以说散列技术既是一种存储方法，也是一种查找方法。散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率会大大提高。但万事有利就有弊，散列技术不具备很多常规结构的能力。

比较那种同样的关键字，它能对应很多记录的情况，却不适合用散列技术。比如，一个班级几十个学生，他们的性别有男有女，你用关键字“男”去查找，对应的有许多学生的记录，这显然是不合适的。只有如用班级学号或身份证号来散列存储，此时一个号码唯一对应一个学生才比较合适。

同样散列表也不适合范围查找，比如查找一个班级18~22岁的同学，在散列表中没法进行。想获得表中记录的排序也不可能，像最大值、最小值等结果也都无法从散列表中计算出来。

总之，设计一个简单均匀、存储利用率高的散列函数是散列技术中最关键的问题。

## 1.5 与其它数据结构的不同 ##

散列表与线性表、树、图结构不同的是，其它几种结构，数据元素之间都存在某种逻辑关系，可以用连线图表示出来，而散列技术的记录之间不存在什么逻辑关系，它只关键字有关联。因此，散列主要是面向查找的存储结构。

# 2 散列函数 #

经过上面的介绍也知道一个散列函数对散列表来说非常重要，那一个好的散列函数有什么的原则标准呢？又有什么样的方法呢？

## 2.1 好的散列函数原则 ##

什么样的散列函数才算是好的散列函数呢？这里有几个原则可以参考：

1.  计算简单；
2.  散列地址分布均匀；
3.  独立于数据可能可在的任何模式。

### 2.1.1 计算简单 ###

假如设计了一个算法可以保证所有的关键字都不会产生冲突，但这个算法需要很复杂的计算，会耗费很多时间，这对于需要频繁地查找来说，就会大大降低查找的效率了。因此散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。

### 2.1.2 散列地址分布均匀 ###

一个好的散列函数应满足简单均匀散列假设：每个关键字都被等可能地散列到m个槽位中的任何一个，并与其他关键字已散列到哪个槽位无关。就是说若对关键字集合中的任一个关键字，经散列函数映射到地址集合中任何一个地址的概率是相等的。简单来说，就是尽量让散列地址均匀分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。遗憾的是，一般无法检查这一条件是否成立，因为很少能知道关键字散列所满足的概率分布，而且各关键字可能并不是完全独立的。

有时若知道关键字的概率分布。如各关键字都随机的实数![k][]，它们独立均匀地分布于![0\\leqslant k< 1][0_leqslant k_ 1]范围中，那么散列函数![20200101134859749.png][]

就能满足简单均匀散列的假设条件。

在实际应用中，常常可以运用启发式方法来构造性能好的散列函数。在设计过程中，可利用关键字分布的有用信息。如在一个编译器的符号表中，关键字都是字符串，表示程序中的标识符。一些很相近的符号经常会出现在同一个程序中，如pt和pts。好的散列函数应能将这些相近符号散列到相同槽中的可能性最小化。

### 2.1.3 独立于数据可能可在的任何模式 ###

一种好的散列方法导出的散列值，在某种程度上应独立于数据可能存在的任何模式。例如，“除法散列”用一个特定的素数来除所给的关键字，所得的余数即为该关键字的散列值。假定所选择的素数与关键字分布中的任何模式都是无关的，这种方法常常可以给出好的结果。

最后，注意到散列函数的某些应用可能会要求比简单均匀散列更强的性质。例如，可能希望某些很近似的关键字具有截然不同的散列值。下面介绍几种常用的散列函数构造方法。

## 2.2 散列函数方法 ##

如何设计一个好的散列函数呢？这里总结了《大话数据结构》和《算法导论》两本书的内容。下面先讲的是《大话数据结构》的内容。

### 2.2.1 直接定址法 ###

直接定址法是直接取关键字的某个线性函数的值作为散列地址，公式如下。这样的散列函数简单均匀，也不会产生冲突，但问题是需要事先知道关键字的分布情况，适合查找表比较小且连续的情况。由于这样的限制，在实际应用中，此方法虽然简单，但并不常用。

![f(key) = a \* key + b][f_key_ _ a _ key _ b]（a、b为常数）

若现在要对0~100岁的人口数字统计表，如下表。因为年龄是数字，可以直接用年龄这个关键字作为地址。此时![f(key) = key][f_key_ _ key]。

![20200102180449597.png][]

又比如我们要统计80年出生年份的人口数，如下表。那么可以用出生年份这个关键字 减去1980来作为地址。此时![f(key) = key - 1980][f_key_ _ key - 1980]。

![20200102180808889.png][]

### 2.2.2 数字分析法 ###

数字分析法是使用关键字的一部分来计算散列位置的方法。通常适合处理关键字位数比较大的情况，若事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑使用此方法。

若关键字是多位数字，比如11位的手机号，其中前三位是接入号，一般对应不同的运营商公司的子品牌，如130是联通如意；中间四位是HLR识别号，表示用户归属地；后四位才是真正的用户号，如下表。

![20200102190630765.png][]

现在要存储某家公司员工登记表，可用手机号作为关键字，那极有可能前7位都是相同的，那么后四位作为散列地址就是不错的选择。若这样的抽取工作还是容易出现冲突问题的话，还可对抽取出来的数字再进行反转（如1234转成4321）、右环位移（如1234转成4123）、左环位移、甚至前两个数与后两个数叠加（如1234转12+34=46）等方法。总的目的就是为了提供一个散列函数，能够合理地将关键字分配到散列表的各个位置。

这里用到了一个关键词——抽取。抽取方法就是使用关键字的一部分来计算散列位置的方法，这在散列函数中是经常用到的手段。

### 2.2.3 平方取中法 ###

平方取中法，就是对关键字进行平方运算，再取结果中的几位。它比较适合于不知道关键字的分布，而位数又不是很大的情况。使用此方法时，首先关键字是数字，或容易转成数字。

假设关键字是1234，那么它的平方就是1522756，再提取中间的3位就是227，用做散列地址。

### 2.2.4 折叠法 ###

折叠法是将关键字从左到右分割成位数相等的几部分（需要注意最后一部分位数不够时可以短一些），然后将这几部分叠加求和，并按散列表表，取后几位作为散列地址。运用此方法时一般事先不需要知道关键字的分布，适合关键字倍数较多的情况。

例如关键字是9876543210，散列表表长为3位，将关键字作为四组987 | 654 | 321 | 0，然后它们叠加求和为987+654+321+0=1962，再求后3位得到散列地址为962.

有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。例如将987和321反转，再与654和0相加，变成789+654+123+0=1566，此时散列地址为566。

### 2.2.5 除留余数法 ###

此方法作为最常用的构造散列函数的方法。对于散列表长为m的散列函数公式为：

![f(key) = key][f_key_ _ key]  ![mod][mod 1]  ![p][p 1]   ![(p\\leq m)][p_leq m]

其中，mod是取模（求余数）的意思。事实上，此方法不仅可以对关键字直接取模，也可以在折叠、平方取中后再取模。

很显然，此方法的关键在于选择合适的 p，如果 p 选择的不好，很可能导致冲突，出现同义词。

例如下表中，对有12个记录的关键字构造散列表时，就用了![f(key) = key.mod 12][f_key_ _ key.mod 12]的方法。如29  mod  12 = 5，所以它存储在下标为5的位置。

![20200102192849420.png][]

但这也可能存在冲突。比如上面的29=2\*12+5，17=12+5，它们的余数都是5，还有其它很多种情况。本身是因为数学运算较为简单，结果很多时候是一位数，如果关键字一多很容易产生冲突。

甚至会出现一些极端情况，如下表中的关键字。若让p = 12的话，就会出现下面的情况，所有的关键字都得到了0这个地址数。

![20200102193352912.png][]

此时不选用p = 12， 而是选用 p = 11。如下表所示。这样就只有12和144冲突了。相对来说要好很多。

![20200102193601348.png][]

所以，若散列表表长为m，通常 p 为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数（自然数中除了能被1和本身整除外，还能被其它数【0除外】整除的数）。

### 2.2.6 随机数法 ###

随机数法是选择一个随机法，取关键字的随机函数值作为它的散列地址。也就是![f(key) = random(key)][f_key_ _ random_key]。这里random是随机数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。下面介绍《算法导论》一书中的三种方法。

在《算法导论》一书中介绍了三种方法：用除法进行散列、用乘法进行散列和全域散列。前两种本质上属于启发式方法，第三种则利用了随机技术来提供可证明的良好性能。

多数散列函数都假定关键字的全域为自然数集![N = \{0, 1, 2, ...\}][N _ _0_ 1_ 2_ ...]。因此若所给关键字不是自然数，就需要找到一种方法来将它们转换为自然数。例如，一个字符串可以被转换为按适当的基数符号表示的整数。这样就可以将标识符ps转换为十进制整数对（112， 116），这是因为在![ASC\\amalg][ASC_amalg]字符集中，p =112， t = 116。然后以128为基数来表示，pt即为(112 x 128) + 116 = 14452。在一特定的应用场全，通常还能设计出其它类似的方法，将每个关键字转换为一个（可能是很大的）自然数。在后面的内容中，假定所给的关键字都是自然数。

### 2.2.7 除法散列法 ###

在除法散列法中，通过取关键字![k][]除以m（散列表的大小）的余数，将关键字![k][]映射到m个槽中的某一个上，即散列函数为：

![20200101142305872.png][]

例如，若散列表的大小m = 12，所给关键字![k][] = 100，则![h(k)][h_k]=4。由于只需做一次除法操作，所以除法散列法是非常快的。

在应用除法散列法时，要避免选择m的某些值。例如，m不应为2的幂，因为若m = ![2^\{p\}][2_p]，则![h(k)][h_k]就是k的p个最低位数字。除非已知各种最低p的排列形式为等可能的，否则在设计散列函数时，最好考虑关键字的所有位。

一个不太接近2的整数幂的素数，常常是m的一个较好的选择。例如，假定要分配一张散列表并用链接法解决冲突，表中大约要存放n = 2000个字符串，其中每个字符有8位。若不介意一次不成功的查找需要平均检查3个元素，这样分配散列表的大小m = 701。选择701这个数的原因是，它是一个接近2000 / 3的数但又不接近2的任何次幂的素数。把每个关键字视为一个整数，则散列函数如下：

![20200101212606502.png][]

### 2.2.8 乘法散列法 ###

构造散列函数的乘法散列法包含两个步骤。第一步用关键字![k][]乘上常数A（0 < A < 1），并提取![k][]A的小数部分；第二步用m乘以这个值，再向下取整。散列函数为：

![20200101212914593.png][]

这里“![k][]A  mod  1”是取![k][]A的小数部分，即![20200101213002252.png][]

乘法散列法的一个优点是对 m 的选择不是特别关键，一般选择它为2的某个幂次（![m = 2^\{p\}][m _ 2_p]，p 为某个整数），这是因为哥以在大多数计算器上，按下面所示的方法较容易的实现散列函数。

假设某个计算机的字长为 w 位，而 k 正好可用一个单字表示。限制A为形如![s / 2^\{w\}][s _ 2_w]的一个分数，其中 s 是一个取自 ![0< s < 2^\{w\}][0_ s _ 2_w]的整数。如下图。先用 w 位整数 ![s = A \\cdot 2^\{w\}][s _ A _cdot 2_w]乘上k，其结果是一个2w 位的值![r\_\{1\}2^\{w\} + r\_\{0\}][r_1_2_w_ _ r_0]，这里![r\_\{1\}][r_1]为乘积的高位字，![r\_\{0\}][r_0]为乘积的低位字。所求的 p 位散列值中，包含了![r\_\{0\}][r_0]的 p 个最高有效位。

散列的的乘法方法，关键字 k 的 w 位表示乘上 ![s = A \\cdot 2^\{w\}][s _ A _cdot 2_w]的 w 位值。在乘积的低 w 位中， p 个最高位构成了所需要的散列值![h(k)][h_k 1]。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 3][]

虽然这个方法对任何的A 都适用，但对某些值的效果更好。最佳的选择与待散列值的数据有特征有关。Knuth\[211\]认为下面的是一个比较理想的值。

![A\\approx (\\sqrt\{5\} -1)/2 = 0.618][A_approx _sqrt_5_ -1_2 _ 0.618] ![033][] ![988][] 7...

假设k = 123 456，p = 14，m = ![2^\{14\}][2_14] = 16384，且 w = 32。依据Knuth的建议，取A 的值形如![s/2^\{32\}][s_2_32]的分数，它与![(\\sqrt\{5\}-1)/2][sqrt_5_-1_2]最为接近，于是A = 2 654 435 769/![2^\{32\}][2_32]。那么，k \* s = 327 706 022 297 664 = ![(76300 \* 2^\{32\}) +][76300 _ 2_32_]17 612 864，从而有![r\_\{1\}][r_1] = 76300和![r\_\{0\}][r_0]=17 612 864。![r\_\{0\}][r_0]的14个最高有效位产生了散列值![h(k)][h_k 1] = 67。

### 2.2.9 全域散列法 ###

全域散列法（universal  hashing）就是随机的选择散列函数，使之独立于要存储的关键字。当然这里不是每次计算时都随机选择散列函数，这样会导致查找时不知道所用的散列函数。而是在构建一个哈希表时随机选择一个散列函数，选定之后这个哈希表的所有操作都是基于这个散列函数。这样即使选择了怎么样的关键字，平均性能较好。可以防止恶意的对手来针对某个特定的散列函数选择要散列的关键字，那可以将 n 个关键字全部散列到同一槽中，使得平均的检索时间为O(n)，这是一种令人恐怖的最坏情况。换句话说，全域散列法因为可以随机的选择散列函数，所以在一定程序上可以防止对手的恶意操作导致冲突。

此散列法在执行开始时，就从一组精心设计的函数中，随机的选择一个作为散列函数。就像在快速排序中一样，随机化保证了没有哪一种输入会始终导致最坏情况性能。因为随机地选择散列函数，算法在每一次执行时都会有所不同，甚至对相同的输入都会如此。这样就可确保对于任何输入，算法都具有较好的平均情况性能。

设![\\mu][mu]为一组有限散列函数，它将给定的关键字全域U映射到\{0, 1, ..., m-1\}中。这样的一个函数组称为全域的（universal），若对每一对不同的关键字 k，![l\\in U][l_in U]，满足![h(k) = h(l)][h_k_ _ h_l]的散列函数![h\\in \\mu][h_in _mu]的个数至少为![\\mid \\mu \\mid/ m][mid _mu _mid_ m]，这里可以叫做全域哈希。换句话，若从![\\mu][mu]中随机选择一个散列函数，当关键字![k\\neq l][k_neq l]时，两者发生冲突的概率不大于![1/m][1_m]，这也正好是从集合\{0, 1, ..., m-1\}中独立地随机选择![h(k)][h_k]和![h(l)][h_l]时发生冲突的概率。

下面的定理证明，全域散列函数的平均性能是比较好的。注意![n\_\{i\}][n_i]表示链表![T\[i\]][T_i]的长度。

> **定理**    如果![h][]选自一组全域散列函数，将![n][]个关键字散列到一个大小为![m][m 1]的表![T][]中，并用链表链接法解决冲突。若关键字![k][]不在表中，则![k][]被散列至其中的链表的期望长度![E\[n\_\{h(k)\}\]][E_n_h_k]至多为![a = n/m][a _ n_m]。若关键字![k][]在表中，则包含关键字![k][]的链表的期望长度![E\[n\_\{h(k)\}\]][E_n_h_k]至多为![1+a][1_a]个。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 4][]

上图是证明过程。下面来说明如何设计一个全域散列函数类。

设计一个全域散列函数类很容易，只需要一点数论方面的知识。首先选择一个足够大的素数p，使得每一个可能的关键字k 都落在0到p-1的范围内（包含0和p-1）。设![Z\_\{p\}][Z_p]表示集合\{0，1，...，p-1\}，![\\bg\_black \\large Z\_\{p\}^\{\\cdot \}][bg_black _large Z_p_cdot]表示集合\{1，2，...，p-1\}。由于p是一个一素数，故可以用模运算方法来求解模 p 的方程。假定关键字全域的大小大于散列表的槽数，故有p > m。

现在，对于任何![\\bg\_white \\large a\\in Z\_\{p\}^\{\\cdot \}][bg_white _large a_in Z_p_cdot]和![\\bg\_white \\large b\\in Z\_\{p\}][bg_white _large b_in Z_p]，定义散列函数![\\bg\_white \\large h\_\{ab\}][bg_white _large h_ab]。利用一次线性变换，再进行模 p 和模 m 的归约，有  
                                                   ![\\large h\_\{ab\}(k) = ((ak + b)modp)modm][large h_ab_k_ _ _ak _ b_modp_modm]

例如，若 p = 17和 m = 6，则有![h\_\{3.4\}(8) = 5][h_3.4_8_ _ 5]。所有这样的散列函数构成的函数簇为

![\\mu \_\{pm\} =][mu _pm_] ｛ ![h\_\{ab\}:a\\in Z\_\{p\}^\{\\cdot \},b\\in Z\_\{p\}][h_ab_a_in Z_p_cdot _b_in Z_p] ｝

每一个散列函数![h\_\{ab\}][h_ab]都将![Z\_\{p\}][Z_p]映射到![Z\_\{m\}][Z_m]。这一类散列函数具有一个良好的性质，即输出范围的大小 m 是任意的，不必是一个素数。由于对 a 来说有 p-1种选择，对 b 来说有 p 种选择，故![\\mu \_\{pm\}][mu _pm]中包含![p(p-1)][p_p-1]个散列函数。

### 2.2.10 使用总结 ###

其实工作中会经常遇到一些字符串，那它是如何处理的呢？其实无论是英文字符，还是中文字符，也包括各种各样的符号，它们都可以转化为某种数字来处理。比如![ASC\\amalg][ASC_amalg 1]码或Unicode码等，因此也就可以使用上面的这些方法了。

在实际应用中，应该视不同的情况采用不同的散列函数。下面给出一些考虑因素以提供参数，综合下面的这些因素，才能决策选择哪种散列函数更合适。同时也可以几种方法混合适合。

1.  计算散列地址所需要的时间；
2.  关键字的长度；
3.  散列表的大小；
4.  关键字的分布情况；
5.  记录查找的频率。

最后的三种方法结合了一定的理论基础，较为深入，但需要一定的功力去理解。前面的几种方法是《大话数据结构》一书中讲的几种方法，相对来说，比较通俗易懂，白话形式的讲解，很容易去接受。

# 3 哈希冲突 #

在散列过程中，可能会出现中冲突，即多个关键字映射到同一个槽中，这个问题是比较严重的。但也要知道一点，设计的再好的散列函数，也不定可以完全避免冲突。但仍然要去解决冲突，并尽量预防这样的问题。

## 3.1 哈希冲突 ##

若两个关键字可能映射到同一个槽中，称这种情况为冲突（collision）。幸运的是，能找到有效的方法来解决冲突。当然，理想的解决方法是避免所有的冲突。

可以试图选择一个合适的散列函数h来做到这一点。一个想法就是使h尽可能的“随机”，从而避免冲突或者使冲突的次数最小化。实际上，术语“散列”的原意就是随机混杂和拼凑，即体现了这种思想。当然，一个散列函数 h 必须是确定的，因为某一个给定的输入 k 应始终产生相同的结果![h(k)][h_k]。但由于|U| > m，故至少有两个关键字其散列值相同，所以要想完全避免冲突是不可能的。因此一方面可以通过精心设计的散列函数来尽量减少冲突的次数，另一方面仍需要有解决可能出现冲突的办法。

通俗一点说，就是在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，然而现实中，仍然有冲突。常会碰到两个关键字![key1\\neq key2][key1_neq key2]，但却有![f(key1) = f(key2)][f_key1_ _ f_key2]，这种现象称为冲突（collision），并把 ![key1][]和![key2][]称为这个散列函数的同义词（synonym）。出现了冲突当然非常糟糕，将造成数据查找错误。尽管我们可以通过精心设计的散列函数让冲突尽中可能的少，但还是不能完全避免。于是如何解决冲突就成了一个非常重要的问题。

下面介绍两种解决冲突的办法：链接法（chaining）和开放寻址法（open  addressing）。

## 3.2 冲突解决方法 ##

### 3.2.1 链接法 ###

在链接法中，把散列到同一个槽中的所有元素都放在一个链表中，叫也链路法、链地址法。如下图所示。槽 j 中有一个指针，它指向存储所有散列到 j 的元素的链表的表头；若不存在这样的元素，则槽 j 中为NIL。比如每个散列地址设置一个单链表，这样就不存在冲突换地址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。当然也可以使用双链表等，这样就把冲突转换成增加链表结点的问题了。前面介绍过链表，知道这样的处理就带来了查找时需要遍历链表而产生的性能损耗。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 5][]

插入操作的最坏情况运行时间为O(1)。插入过程在某种程度上要快一些，因为假设待插入的元素 x 没有出现在表中；若需要可以在插入前执行一个搜索来检查这个假设（需付出额外代价）。查找操作的最坏情况运行时间与表的长度成正比。

若散列表中的链表是双向链表，则删除一个元素 x 的操作可在O(1)的时间内完成。注意到，删除元素 x 而不是它的关键字k作为输入，所以无需先搜索 x。若散列表支持删除操作，为了能更快的删除某一元素，应该将其链表设计为双向链表。若是单链表，为了删除元素 x 要先在表![T\[h(x, key)\]][T_h_x_ key]中找到元素 x，然后通过更改 x 的前驱元素的属性，把 x 从链表中删除。在单链表情况下，删除和查找操作的渐近运行时间相同。

通过链接法解决冲突，每个散列表槽![T\[j\]][T_j] 都包含一个链表，其中所有关键字的散列值均为 j 。如![h(k\_\{1\})][h_k_1]=![h(k\_\{4\})][h_k_4]。这个链表可能是单链表，也可能是双链表。上图中链表为双链表，因为删除操作比较快。下面分析下采用链接法后散列的性能。

给定一个能存放n个元素的、具有m个槽位的散列表T，定义T的装载因子（load  factor）a = n / m，即一个链的平均存储元素数。后面的分析将借助a来说明，a可以小于、等于或大于1。

用链接法散列的最坏情况性能很差：所有的n个关键字都散列到同一个槽中，从而产生出一个长度为n的链表。此时最坏情况下查找的时间为O(n)，再加上计算散列函数的时间，如此就和用一个链表来链接所有元素差不多了。显然，并不是因为散列表的最坏情况性能差，就不使用它。当公完全散列能够在关键字集合为静态时，能提供比较好的最坏情况性能。

散列方法的平均性能依赖于所选取的散列函数h，将所有的关键字集合分布在m个槽位中的任何一个。先假设任何一个给定元素等可能的散列到m个槽位中的任何一个，且与其他元素被散列到什么位置上无关。我们称这个假设为简单均匀散列（simple  uniform  hashing）。

对于 j = 0，1，...，m-1，列表T\[j\]的长度用![n\_\{j\}][n_j 1]表示，于是有

![n = n\_\{0\} + n\_\{1\} + ... + n\_\{m-1\}][n _ n_0_ _ n_1_ _ ... _ n_m-1]

并且![n\_\{j\}][n_j 1]的期望值为![E\[n\_\{j\}\] = a = n / m][E_n_j_ _ a _ n _ m]。

假定可以在O(1)时间内计算出散列值h(k)，从而查找关键字为k的元素的时间线性的依赖于表![T\[h(k)\]][T_h_k]的长度![n\_\{h(k)\}][n_h_k]。先不考虑计算散列函数和访问槽![h(k)][h_k]的O(1)时间，来看看查找算法查找元素的期望数，即为比较元素的关键字是否为![k][]而检查表![T\[h(k)\]][T_h_k]中的元素数。分两种情况来考虑。在第一种情况中，查找不成功：表中没有一个元素的关键字为![k][]。在第二种情况中，成功的查找到关键字为![k][]的元素。

> **定理1**  在简单均匀散列的假设下，对于用链接法解决冲突的散列表，一次不成功查找的平均时间为![\\Theta (1+a)][Theta _1_a]。

> **定理2**   在简单均匀散列的假设下，对于用链接支解决冲突的散列表，一次成功查找所需的平均时间为![\\Theta (1+a)][Theta _1_a]。

上面的分析意味着，若散列表中槽数至少与表中的元素数成正比，则有 n = O(m)，从而 a = n / m = O(m) / m = O(1)。所以查找操作平均需要常数时间。当链表采用双向链接时，插入操作在最坏情况下需要O(1)的时间，删除操作最坏情况下也需要O(1)的时间，因而，全部的字典操作平均情况下都可以在O(1)时间内完成。

例如，将所有关键字为同义词的记录存储在一个单链表中，称这种表为同义词子表，在散列表中存储所有同义词子表的头指针。对于关键字集合｛12，67，56，16，25，37，22，29，15，47，48，34｝，表中个数为12，以12为除数，进行除留余数法，可以得到下图所示的结构。这样就不存在冲突换地址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 6][]

### 3.2.2 开放寻址法 ###

开放寻址法（open  addressing），也叫开放定址法，是指一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录记入。这样的话，所有的元素都放在散列表中。即每个表项要不包含动态集合的一个元素，要不包含空。当查找某个元素时，要系统地检查所有的表项，直到找到所需要的元素，或者最终查明该元素不在表中。

为了使用开放寻址法插入一个元素，需要连续地检查散列表，或称为探查（probe），直到找到一个空槽来放置待插入的关键字为止。检查的顺序不一定是0，1，...，m-1（这种顺序下的查找时间为O(n)），而是要依赖于待插入的关键字。为了确定要探查哪些槽，将散列函数加以扩充，使之包含探查号（从0开始）以作为其第二个输入参数。这样散列函数就变为：

![h:U \*][h_U] \{ ![0, 1, ..., m-1][0_ 1_ ..._ m-1]\} ![\\rightarrow][rightarrow] \{ ![0, 1, ..., m-1][0_ 1_ ..._ m-1]\}

对每个关键字 k，使用开放寻址法的探查序列（probe  sequence）![h(k,0),h(k,1),...,h(k,m-1)][h_k_0_h_k_1_..._h_k_m-1]，是0，1，...，m-1的一个排列，使得当散列表逐渐填满时，每一个表位最终都可以被考虑为用来插入新关键字的槽。

在《大话数据结构》中，定义它的公式是（辅助散列函数）：

![f\_\{i\}(key) = (f(key) + d\_\{i\})][f_i_key_ _ _f_key_ _ d_i]  ![mod][]  ![m][] ![(d\_\{i\} =1,2,3,...,m-1)][d_i_ _1_2_3_..._m-1]

例如，关键字集合为｛12，67，56，16，25，37，22，29，15，47，48，34｝，表长为12。用散列函数

![f(key) = key][f_key_ _ key 1]  ![mod][] 12。当计算前5个数｛12，67，56，16，25\}时，都是没有冲突的的散列地址，所以是直接存入，如下表。

![20200104131040709.png][]

当计算key = 37时，发现 f (37) = 1，此时与25所在的位置冲突了。于是应用上面的公式f (37) = (f (37) + 1)   mod  12 = 2，可以直接存入，于是将37存入下标为2的位置。接下来的22，29，15，47和都没有冲突，正常存入。如下表。

![20200104133036234.png][]

到了key = 48，计算得到f (48) = 0，与12所在的位置冲突了，于是用上面的公式 f (48) = (f(48) + 1)  mod  12 = 1，此时又与25所在的位置冲突，于是再用上面的公式 f (48) = (f(48) + 2)  mod  12 = 2，还是冲突了...，一直到 f (48) = (f(48) + 6)  mod  12 = 6时才有空位，此时存入。

![20200104133338698.png][]

把这种解决冲突的开放寻址法，称为线性探测法。 这种本来都不是同义词却需要争夺一个地址的情况，称这种现象为堆积。堆积的出现，使得需要不断的处理冲突，无论是存入还是查找效率都会大大降低。

可以看出，线性探测法比较容易实现，但它存在一个问题，称为一次群集（primary  clustering）。随着连续被占用的槽不断增加，平均查找时间也随之不断增加。群集现象很容易出现，这是因为当一个空槽前有 i 个满的槽时，该空槽的下一个将被占用的概率是 (i+1)/m。连续被占用的槽就会变得越来越多，因而平均查找时间也会越来越长。

**二次探测法**

考虑深一步，若发生这样的情况：当最后一个key = 34，f (key) = 10，与22所在的位置冲突，可是22后面没有位置了，反而它的前面有一个空位置，尽管可以不断的求余数后得到结果，但效率很差。因此我们可以改进![d\_\{i\} = 1^\{2\},-1^\{2\},2^\{2\},-2^\{2\},...,q^\{2\},-q^\{2\},(q\\leq m/2)][d_i_ _ 1_2_-1_2_2_2_-2_2_..._q_2_-q_2_q_leq m_2]，这样就等于是可以双向寻找可能的位置。对于34来说，我们取 ![d\_\{i\}][d_i]=-1 就可以找到空位置了。另外增加平方运算的目的是为了不让关键字都聚焦在某一区域。称这种方法为二次探测法。

![f\_\{i\}(key) = (f(key) + d\_\{i\})][f_i_key_ _ _f_key_ _ d_i]  ![mod][]  ![m][]  ![(d\_\{i\} = 1^\{2\},-1^\{2\},2^\{2\},-2^\{2\},...,q^\{2\},-q^\{2\},q\\leq m/2)][d_i_ _ 1_2_-1_2_2_2_-2_2_..._q_2_-q_2_q_leq m_2 1]

上面的公式是在《大话数据结构》中定义的，而在《算法导论》中给出的公式如下：

![h(k, i) = (h^\{'\}(k)+c\_\{1\}i+c\_\{2\}x^\{2\})][h_k_ i_ _ _h_k_c_1_i_c_2_x_2]   ![mod][]   ![m][]

其中![h^\{'\}][h 1]是一个辅助散列函数，![c\_\{1\}][c_1]和![c\_\{2\}][c_2]为正的辅助常数，![i = 0,1,...,m-1][i _ 0_1_..._m-1]。初始的探查位置为![T\[h^\{'\}(k)\]][T_h_k 1]，后续的探查位置要加上一个偏移量，该偏移量以二次的方式依赖于探查序号 i。这种探测方法的效果要比线性探测好得多。但为了能充分利用散列表，![c\_\{1\}][c_1]、![c\_\{2\}][c_2]和 m 的值要受到限制。此外，若两个关键字的初始探查位置相同，那它们的探查序列也是相同的，这是因为![h(k\_\{1\},0)=h(k\_\{2\},0)][h_k_1_0_h_k_2_0]蕴涵着![h(k\_\{1\},i)=h(k\_\{2\},i)][h_k_1_i_h_k_2_i]。这一性质可导致一种轻度的群集，称为二次群集（secondary  clustering）。像在线性探测中一样，初始探查位置决定了整个序列，这样也仅有 m 个不同的探查序列被用到。

可以认为《大话数据结构》给的公式（上面一个公式）是《算法导论》中公式的一种特殊形式，更容易理解和使用。

**双重散列**

双重散列（double  hashing）是用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择排序的许多特性。双重散列采用如下的散列函数：

![h(k,i)=(h\_\{1\}(k)+ih\_\{2\}(k))][h_k_i_h_1_k_ih_2_k]   ![mod][]   ![m][]

其中，![h\_\{1\}][h_1]和![h\_\{2\}][h_2]均为辅助散列函数。初始探查位置为![T\[h\_\{1\}(k)\]][T_h_1_k]，后续的探查位置是前一个位置加上偏移量![h\_\{2\}(k)][h_2_k]和 m。因此不像线性探查法或二次探查，这里的探查序列以两种不同方式依赖于关键字 k ，因为初始探查位置、偏移量或者二者都可能发生变化。下图给出了一个使用双重散列法进行插入的例子。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 7][]

为了能查找整个散列表，值![h\_\{2\}(k)][h_2_k]必须要与表的大小 m 互素。有一种简便的方法确保这个条件成立，就是取 m 为2的幂，并设计一个总产生奇数的![h\_\{2\}][h_2]。另一种方法是取 m 为素数，并设计一个总是返回较 m 小的正整数的函数![h\_\{2\}][h_2]。例如，可以取 m  为素数，并取![h\_\{1\}(k)=k][h_1_k_k]  ![mod][]   ![m][]，![h\_\{2\}(k)=1+(k][h_2_k_1_k]   ![mod][]  ![m^\{'\}][m 2]![)][gif.latex_5Cdpi_7B120_7D_20_29]

其中![m^\{'\}][m 2]略小于 m (比如m-1)。例如，若k = 123  456， m = 701，![m^\{'\}][m 2] = 700，则有![h\_\{1\}(k)=][h_1_k]80，![h\_\{2\}(k)=][h_2_k 1]257，可以知道第一个探查的位置是80，然后检查第257个槽（模 m），直到找到该关键字，或者遍历了所有槽。

在上图中，此处散列表的大小为13，![h\_\{1\}(k)=k][h_1_k_k]  ![mod][] 13，![h\_\{2\}(k)=1+(k][h_2_k_1_k]  ![mod][] 11![)][gif.latex_5Cdpi_7B120_7D_20_29]。因为14 ![\\equiv][equiv]1  ![mod][]  13，且14 ![\\equiv][equiv] ![(][gif.latex_5Cdpi_7B120_7D_20_28]3  ![mod][]  11![)][gif.latex_5Cdpi_7B120_7D_20_29]，故在探查了槽1和槽5，并发现它们被占用后，关键字14被插入到槽9中。

当 m 为素数或者2的幂时，双重散列法中用到了![\\Theta (m^\{2\})][Theta _m_2]种探查序列，而线性探查或二次探查序列中只用了![\\Theta (m)][Theta _m]种，故前者是后两种方法的一种改进。因为每对可能的（![h\_\{1\}(k)][h_1_k 1]，![h\_\{2\}(k)][h_2_k]）都会产生一个不同的探查序列。因此对于 m 的每一种可能取值，双重散列的性能看起来就非常接近理想的均匀散列的性能。

尽管除素数和2的幂以外的 m 值理论上也能用于双重散列中，但在实际中，要高效的生产![h\_\{2\}(k)][h_2_k]确保使其与 m 互素，将变得更加困难。部分原因是这些数据的相对密度![\\phi (m) / m][phi _m_ _ m]可能较小。

**随机探测法**

在《大话数据结构》中提到还有一种一方法，是在冲突时，对于位移量![d\_\{i\}][d_i]采用随机函数计算得到，称之为随机探测法。可能有人会问，既然是随机，那在查找的时候不也随机生成![d\_\{i\}][d_i]吗？这里的随机数其实是伪随机数。伪随机数是说，若设置的随机种子相同，则不断调用随机函数可以生成不会重复的数列，在查找时用同样的随机种子，它每次得到的数列是相同的，相同的![d\_\{i\}][d_i]当然可以得到相同的散列地址。随机种子，Random Seed，计算机专业术语，一种以随机数作为对象的以真随机数（种子）为初始条件的随机数。一般计算机的随机数都是伪随机数，以一个真随机数作为初始条件，然后用一定的算法不停迭代产生随机数。随机种子是随机数的初始值。伪随机数一般是一直不变的随机数。根据随机种子得到的随机数值是不变的，而不加随机种子直接得到的随机数是真的随机数，会不断变化。

![f\_\{i\}(key) = (f(key) + d\_\{i\})][f_i_key_ _ _f_key_ _ d_i]  ![mod][]  ![m][]  ![(d\_\{i\}][d_i 1]是一个随机数列，其实是一个伪随机数序列![)][gif.latex_5Cdpi_7B120_7D_20_29]

开放寻址法只要在散列表未填满时，总能找到不发生冲突的地址，是我们常用的解决冲突的办法。

开放寻址法不像链接法，既没有链表，也没有元素存放存放在散列表外。因此在此方法中，散列表可能会被填满，以至于不能插入任何新的元素。该方法导致的一个结果便是装载因子a绝对不会超过1。开放寻址法的分析也是以散列表的装载因子a = n/m来表达的，使用此法，每个槽中至多只有一个元素，因而n ![\\leqslant][leqslant] m，也就意味着a ![\\leqslant][leqslant] 1。

当然也可以将用作链接的链表存放在散列表未用的槽中，但开放寻址法的**好处**就在于它不用指针，而是计算出要存取的槽序列。于是不用存储指针而节省的空间，使得可以用同样的空间来提供更多的槽，潜在地减少了冲突，提高了检索速度。

### 3.2.3 再散列法 ###

对散列表来说，事先准备多个散列函数，如下公式。其中![RH\_\{i\}][RH_i]就是不同的散列函数，可以把前面介绍的除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集。当然这样也相应的增加了计算的时间。

![f\_\{i\}(key)=RH\_\{i\}(key)][f_i_key_RH_i_key]     ![(i=1,2,...,k)][i_1_2_..._k]

在查找时，对关键字根据散列函数计算得到地址，然后去散列表中查找，如果找到了对应的关键字，就不需要再找了。如果没有找到就换一种散列函数重新计算后再去查找，直到找到为止。

### 3.2.4 公共溢出区法 ###

此方法就是将冲突的关键字放在一个公共的地方，即为冲突的关键字建立了一个公共的溢出区来存放。例如，对于关键字集合｛12，67，56，16，25，37，22，29，15，47，48，34｝，表中个数为12，以12为除数，进行除留余数法，会出现冲突。那就将冲突的关键字存放在一个公共的溢出区。如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 8][]

在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等则说明查找成功；如果不相等，就到公共溢出区的溢出表进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

## 3.3 哈希算法不可逆 ##

哈希算法是不可逆的，就像1+4=5和2+3=5一样，你现在知道我的结果是5，能知道我输入的什么数字吗？当然你也可以猜可以试，但你并不一定能一次性准确知道结果。

保密内容是有个有效期的，即在这段时间里面没有被解密出来，那这个内容就是安全的。

其实哈希算法并不是加解密算法。只有单向的，没有解密过程。

# 4. 散列表的查找 #

应用散列后，必须要有相应的查找关键字方法。

## 4.1 查找算法实现 ##

### 4.1.1 初始化 ###

首先需要定义一个散列表的结构，以及一些相关的常数。其中HashTable就是散列表结构，结构中的元素为一个动态数组，开始默认散列表的长度即为数组的长度。数组用来存放关键字，散列地址就是关键字在数组中的下标，因为是一个动态数组，就可以动态的分配数组了。

### 4.1.2 插入散列 ###

因为要进行散列，在插入元素时计算地址，需要定义散列函数，散列函数可以根据不同情况更改算法，假设用除留余数法。那散列函数的算法内容就是 key % m。因为可能存在冲突，所以在计算出散列地址后，判断数组当前位置是否有值，有则说明冲突了，解决冲突后再存入。

例如，要插入的关键字集合还是前面的｛12，67，56，16，25，37，22，29，15，47，48，34｝，先根据关键字关键得出其散列地址。以关键字12为例，其散列地址 addr = 12 % 12 = 0，那么关键字12就存放在数组的第一个位置。但要考虑到冲突的问题，所以当出现冲突时，可以使用开放寻址法中的线性探测，即addr = (addr + 1) % m，如果还是出现冲突，再次进行同样的处理，即循环使用开放寻址法的线性探测，直到不冲突为止。

### 4.1.3 查找 ###

散列表存放了元素，后面就会有取元素的时候。在需要时通过散列表查找记录。先根据关键字计算散列地址，然后根据散列地址从数组中取得关键字，如果取得的关键字与当前关键字不相等，则说明出现了冲突，此时根据散列函数中的冲突解决办法再次计算后查找，如果找不到所说明查找失败。

## 4.2 查找性能 ##

散列表的查找过程基本上与造表的过程相同。一些关键字可以通过散列函数转换的地址直接找到。散列查找比很多查找的效率都高，因为它们的时间复杂度为O(1)。但没有冲突只是一种理想，在实际应用中，冲突是不可避免的。另一个关键字根据散列函数得到的地址上产生了冲突，就需要按照处理冲突的方法进行查找。在上面给出的几种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以对散列表查找效率的量度，依然用平均查找长度（简称ALS【Average  Search  Length】，为确定记录在查找的表中的位置，需要与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度，只是只描述了定义，后面会写一篇关于查找的博客，再详细描述）来衡量。散列查找的平均查找长度取决于下面几方面的因素。

### 4.2.1 散列函数是否均匀 ###

散列函数的好坏直接影响着出现冲突的频繁程度，不过由于不同的散列函数对同一级随机的关键字，产生冲突的可能性是相同的，因此可以不考虑它对平均查找长度的影响。

### 4.2.2 处理冲突的方法 ###

相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链接法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。

### 4.2.3 散列表的装载因子 ###

上面介绍了，装载因子a = 填入表的记录个数 / 散列表的长度。a 标志着散列表的装满程度。当填入表中的记录越多，a 就越大，产生冲突的可能性就越大。比如我们前面的例子，若散列表的长度是12，而填入表中的记录个数为11，那此时的装载因了 a= 11 /12 = 0.9167，再填入最后一个关键字产生冲突的可能性就非常之大了。即散列表的平均查找长度取决于装载因子，而不是取决于查找集合中的记录个数。

在Java的HashMap中，默认的负载因子值为0.75，之所以取这个值是对空间和时间效率的一个平衡选择，建议不要修改，除非在时间和空间比较特殊的情况下。若内存空间很多而又对时间效率要求很高，那可以降低负载因子的值（可以小于0.75）；相对，若内存空间紧张而对时间效率要求不高的话，可以增加负载因子的值，这个值可以大于1。

# 5. 常用的散列算法 #

讲到这里，不得不提一些著名的散列算法，MD5和SHA-1可以说是目前应用最为广泛的散列算法了，这两种算法都是以MD4为基础设计的。下面详细描述。

## 5.1 MD4 ##

MD4(RFC 1320)是MT的Ronald  L.Rivest于1990年设计的，MD是Message  Digest的缩写，大概意思信息摘要。它适用在32位字长的处理器上用高速软件实现，它是基于32位操作数的位操作来实现的。

## 5.2 MD5 ##

MD5(RFC 1321)是Rivest 于1991年MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与MD4相同。MD5比MD4复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。

## 5.3 SHA-1及其他 ##

SHA-1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。它在设计时基于和MD4相同的原理，并且模仿了该算法。

2004年8月17日，在美国加州圣[芭芭拉][Link 1]召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组的研究成果——对MD5、HAVAL－128、MD4和[RIPEMD][]等四个著名[密码算法][Link 2]的破译结果。2005年2月宣布破解SHA-1密码。

# 6. Java中的散列表 #

查看Object类的hashCode()方法，发现它是一个native方法。如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 9][]

我们也可以重写hashCode()方法。示例如下：

public int hashCode() {
            int h = hash;
            if (h == 0 && value.length > 0) {
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) {
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }

其他内容待补充。。。

# 7.  散列表应用 #

散列表中生活中有很多的实际应用，Java中的HashMap等用到了，还有快速查找，emule，加密等。

## 7.1 文件检验 ##

比较熟悉的检验算法有奇偶检验和CRC检验，这2种检验并没有抗数据篡改的能力，它们一定程序上检测出数据传输中的信道误码，但却不能防止对数据的恶意破坏。

MD5 Hash算法的“数学指纹”特性，使它成为目前应用最为广泛的一种文件完整性检验和（Checksum，在数据处理和数据通信领域中，用于检验目的地一组数据项的和，它通常以十六进制为数制表示的形式。通常用来在通信中，尤其是远距离通信中保证数据的完整性和准确性）算法，不少Unin系统中提供计算MD5  checksum的命令。

## 7.2 数字签名 ##

Hash算法也是现代密码体系中的一个重要组成部分。由于非对称算法（指一个加密算法的加密密钥和解密密钥是不一样的，或者说不能由其中一个密钥推导出另一个密钥）的运算速度较慢，所以在数字签名协议中，单向散列函数（又称单向Hash函数、杂凑函数，就是把任意长的输入消息串变化成固定长的输出串且由输出串难以得到输入串的一种函数。这个输出串称为该消息的散列值。一般用于消息摘要，密钥加密等，常见的单向散列函数有MD5、SHA、MAC、CRC等）扮演了一个重要的角色。对Hash值，又称“数字摘要”进行数字签名，在统计上可以认为与文件本身进行数字签名是等效的。而且这样的还有其他的优点。

## 7.3鉴权协议 ##

下面的鉴权协议又被称作挑战—认证模式：在传输信息是可被侦听的，但不可被篡改的情况下，这是一种简单而安全的方法。

## 7.4 实际应用 ##

注：下面的内容摘自百度百科。

在emule中，散列也得到了应用。大家都知道emule是基于P2P （Peer-to-peer的缩写，指的是对等连接的软件）， 它采用了"多源文件传输协议”（[MFTP][]，the Multisource FileTransfer Protocol）。在协议中，定义了一系列传输、压缩和打包还有积分的标准，emule 对于每个文件都有md5-hash的算法设置，这使得该文件独一无二，并且在整个网络上都可以追踪得到。

什么是文件的hash值呢？MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何，它的Hash函数计算结果是一个固定长度的数字。与[加密算法][Link 3]不同，这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法，如MD5、SHA时，两个不同的文件几乎不可能得到相同的Hash结果。因此，一旦文件被修改，就可检测出来。

当我们的文件放到emule里面进行共享发布的时候，emule会根据hash算法自动生成这个文件的hash值，他就是这个文件唯一的身份标志，它包含了这个文件的基本信息，然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候， 这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后（如名称等）这个值就更显得重要。而且服务器还提供了，这个文件当前所在的用户的地址，端口等信息，这样emule就知道到哪里去下载了。

一般来讲我们要搜索一个文件，emule在得到了这个信息后，会向被添加的服务器发出请求，要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的[客户端][Link 4]就可以直接的和拥有那个文件的用户沟通，看看是不是可以从他那里下载所需的文件。

对于emule中文件的hash值是固定的，也是唯一的，它就相当于这个文件的信息摘要，无论这个文件在谁的机器上，他的hash值都是不变的，无论过了多长时间，这个值始终如一，当我们在进行文件的下载上传过程中，emule都是通过这个值来确定文件。

那么什么是userhash呢？道理同上，当我们在第一次使用emule的时候，emule会自动生成一个值，这个值也是唯一的，它是我们在emule世界里面的标志，只要你不卸载，不删除config，你的userhash值也就永远不变，积分制度就是通过这个值在起作用，emule里面的积分保存，身份识别，都是使用这个值，而和你的id和你的用户名无关，你随便怎么改这些东西，你的userhash值都是不变的，这也充分保证了公平性。其实他也是一个信息摘要，只不过保存的不是文件信息，而是我们每个人的信息。

那么什么是hash文件呢？我们经常在emule日志里面看到，emule正在hash文件，这里就是利用了hash算法的[文件校验][Link 5]性这个功能了，文章前面已经说了一些这些功能，其实这部分是一个非常复杂的过程，在ftp,bt等软件里面都是用的这个基本原理，emule里面是采用文件分块传输，这样传输的每一块都要进行对比校验，如果错误则要进行重新下载，这期间这些相关信息写入met文件，直到整个任务完成，这个时候part文件进行重新命名，然后使用move命令，把它传送到incoming文件里面，然后met文件自动删除，所以我们有的时候会遇到hash文件失败，就是指的是met里面的信息出了错误不能够和part文件匹配，另外有的时候开机也要疯狂hash，有两种情况一种是你在第一次使用，这个时候要hash提取所有文件信息，还有一种情况就是上一次你[非法关机][Link 6]，那么这个时候就是要进行排错校验了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200101093711892.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[Theta _K]: https://private.codecogs.com/gif.latex?%5CTheta%20%28%7CK%7C%29
[h_U_rightarrow _left _ _left. 0_ 1_ ..._ m-1_right _ _right.]: https://private.codecogs.com/gif.latex?h%3AU%5Crightarrow%20%5Cleft%20%5C%7B%20%5Cleft.%200%2C%201%2C%20...%2C%20m-1%5Cright%20%5C%7D%20%5Cright.
[h_k]: https://private.codecogs.com/gif.latex?h%28k%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200101110033671.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[20200101215324994.png]: https://img-blog.csdnimg.cn/20200101215324994.png
[70]: https://img-blog.csdn.net/20180531124904648?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6cTIwMTE1Mzk1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[h_k_ _ _ak _ b]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%28k%29%20%3D%20%28%28ak%20&plus;%20b%29
[mod]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20mod
[p]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20p
[gif.latex_5Cdpi_7B120_7D_20_29]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%29
[m]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20m
[h_75_ _ 2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%2875%29%20%3D%202
[S_j]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20S_%7Bj%7D
[m_j]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20m_%7Bj%7D
[n_2_j]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20n_%7B2%7D%5E%7Bj%7D
[h_j_ _key_ _ _a_j_k _ b_j]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7Bj%7D%20%28key%29%20%3D%20%28%28a_%7Bj%7Dk%20&plus;%20b_%7Bj%7D%29
[h_2_75_ _7]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B2%7D%2875%29%20%3D7
[S_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20S_%7B2%7D
[n_j]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20n_%7Bj%7D
[h_j]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7Bj%7D
[m _ n_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20m%20%3D%20n%5E%7B2%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200101222826683.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[k]: https://private.codecogs.com/gif.latex?k
[0_leqslant k_ 1]: https://private.codecogs.com/gif.latex?0%5Cleqslant%20k%3C%201
[20200101134859749.png]: https://img-blog.csdnimg.cn/20200101134859749.png
[f_key_ _ a _ key _ b]: https://private.codecogs.com/gif.latex?f%28key%29%20%3D%20a%20*%20key%20&plus;%20b
[f_key_ _ key]: https://private.codecogs.com/gif.latex?f%28key%29%20%3D%20key
[20200102180449597.png]: https://img-blog.csdnimg.cn/20200102180449597.png
[f_key_ _ key - 1980]: https://private.codecogs.com/gif.latex?f%28key%29%20%3D%20key%20-%201980
[20200102180808889.png]: https://img-blog.csdnimg.cn/20200102180808889.png
[20200102190630765.png]: https://img-blog.csdnimg.cn/20200102190630765.png
[mod 1]: https://private.codecogs.com/gif.latex?mod
[p 1]: https://private.codecogs.com/gif.latex?p
[p_leq m]: https://private.codecogs.com/gif.latex?%28p%5Cleq%20m%29
[f_key_ _ key.mod 12]: https://private.codecogs.com/gif.latex?%5Cinline%20f%28key%29%20%3D%20key.mod%2012
[20200102192849420.png]: https://img-blog.csdnimg.cn/20200102192849420.png
[20200102193352912.png]: https://img-blog.csdnimg.cn/20200102193352912.png
[20200102193601348.png]: https://img-blog.csdnimg.cn/20200102193601348.png
[f_key_ _ random_key]: https://private.codecogs.com/gif.latex?%5Cinline%20f%28key%29%20%3D%20random%28key%29
[N _ _0_ 1_ 2_ ...]: https://private.codecogs.com/gif.latex?N%20%3D%20%7B0%2C%201%2C%202%2C%20...%7D
[ASC_amalg]: https://private.codecogs.com/gif.latex?ASC%5Camalg
[20200101142305872.png]: https://img-blog.csdnimg.cn/20200101142305872.png
[2_p]: https://private.codecogs.com/gif.latex?2%5E%7Bp%7D
[20200101212606502.png]: https://img-blog.csdnimg.cn/20200101212606502.png
[20200101212914593.png]: https://img-blog.csdnimg.cn/20200101212914593.png
[20200101213002252.png]: https://img-blog.csdnimg.cn/20200101213002252.png
[m _ 2_p]: https://private.codecogs.com/gif.latex?%5Cinline%20m%20%3D%202%5E%7Bp%7D
[s _ 2_w]: https://private.codecogs.com/gif.latex?%5Cinline%20s%20/%202%5E%7Bw%7D
[0_ s _ 2_w]: https://private.codecogs.com/gif.latex?%5Cinline%200%3C%20s%20%3C%202%5E%7Bw%7D
[s _ A _cdot 2_w]: https://private.codecogs.com/gif.latex?%5Cinline%20s%20%3D%20A%20%5Ccdot%202%5E%7Bw%7D
[r_1_2_w_ _ r_0]: https://private.codecogs.com/gif.latex?%5Cinline%20r_%7B1%7D2%5E%7Bw%7D%20&plus;%20r_%7B0%7D
[r_1]: https://private.codecogs.com/gif.latex?%5Cinline%20r_%7B1%7D
[r_0]: https://private.codecogs.com/gif.latex?%5Cinline%20r_%7B0%7D
[h_k 1]: https://private.codecogs.com/gif.latex?%5Cinline%20h%28k%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200103101404856.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[A_approx _sqrt_5_ -1_2 _ 0.618]: https://private.codecogs.com/gif.latex?%5Cinline%20A%5Capprox%20%28%5Csqrt%7B5%7D%20-1%29/2%20%3D%200.618
[033]: https://private.codecogs.com/gif.latex?%5Cinline%20033
[988]: https://private.codecogs.com/gif.latex?%5Cinline%20988
[2_14]: https://private.codecogs.com/gif.latex?2%5E%7B14%7D
[s_2_32]: https://private.codecogs.com/gif.latex?s/2%5E%7B32%7D
[sqrt_5_-1_2]: https://private.codecogs.com/gif.latex?%28%5Csqrt%7B5%7D-1%29/2
[2_32]: https://private.codecogs.com/gif.latex?2%5E%7B32%7D
[76300 _ 2_32_]: https://private.codecogs.com/gif.latex?%2876300%20*%202%5E%7B32%7D%29%20&plus;
[mu]: https://private.codecogs.com/gif.latex?%5Cmu
[l_in U]: https://private.codecogs.com/gif.latex?l%5Cin%20U
[h_k_ _ h_l]: https://private.codecogs.com/gif.latex?h%28k%29%20%3D%20h%28l%29
[h_in _mu]: https://private.codecogs.com/gif.latex?h%5Cin%20%5Cmu
[mid _mu _mid_ m]: https://private.codecogs.com/gif.latex?%5Cmid%20%5Cmu%20%5Cmid/%20m
[k_neq l]: https://private.codecogs.com/gif.latex?k%5Cneq%20l
[1_m]: https://private.codecogs.com/gif.latex?1/m
[h_l]: https://private.codecogs.com/gif.latex?h%28l%29
[n_i]: https://private.codecogs.com/gif.latex?n_%7Bi%7D
[T_i]: https://private.codecogs.com/gif.latex?T%5Bi%5D
[h]: https://private.codecogs.com/gif.latex?h
[n]: https://private.codecogs.com/gif.latex?n
[m 1]: https://private.codecogs.com/gif.latex?m
[T]: https://private.codecogs.com/gif.latex?T
[E_n_h_k]: https://private.codecogs.com/gif.latex?E%5Bn_%7Bh%28k%29%7D%5D
[a _ n_m]: https://private.codecogs.com/gif.latex?a%20%3D%20n/m
[1_a]: https://private.codecogs.com/gif.latex?1&plus;a
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200103174216481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[Z_p]: https://private.codecogs.com/gif.latex?Z_%7Bp%7D
[bg_black _large Z_p_cdot]: https://private.codecogs.com/gif.latex?%5Cbg_black%20%5Clarge%20Z_%7Bp%7D%5E%7B%5Ccdot%20%7D
[bg_white _large a_in Z_p_cdot]: https://private.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cbg_white%20%5Clarge%20a%5Cin%20Z_%7Bp%7D%5E%7B%5Ccdot%20%7D
[bg_white _large b_in Z_p]: https://private.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cbg_white%20%5Clarge%20b%5Cin%20Z_%7Bp%7D
[bg_white _large h_ab]: https://private.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cbg_white%20%5Clarge%20h_%7Bab%7D
[large h_ab_k_ _ _ak _ b_modp_modm]: https://private.codecogs.com/gif.latex?%5Cbg_white%20%5Clarge%20h_%7Bab%7D%28k%29%20%3D%20%28%28ak%20&plus;%20b%29modp%29modm
[h_3.4_8_ _ 5]: https://private.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20h_%7B3.4%7D%288%29%20%3D%205
[mu _pm_]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Cmu%20_%7Bpm%7D%20%3D
[h_ab_a_in Z_p_cdot _b_in Z_p]: https://private.codecogs.com/gif.latex?h_%7Bab%7D%3Aa%5Cin%20Z_%7Bp%7D%5E%7B%5Ccdot%20%7D%2Cb%5Cin%20Z_%7Bp%7D
[h_ab]: https://private.codecogs.com/gif.latex?h_%7Bab%7D
[Z_m]: https://private.codecogs.com/gif.latex?Z_%7Bm%7D
[mu _pm]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Cmu%20_%7Bpm%7D
[p_p-1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20p%28p-1%29
[ASC_amalg 1]: https://private.codecogs.com/gif.latex?%5Cinline%20ASC%5Camalg
[key1_neq key2]: https://private.codecogs.com/gif.latex?key1%5Cneq%20key2
[f_key1_ _ f_key2]: https://private.codecogs.com/gif.latex?f%28key1%29%20%3D%20f%28key2%29
[key1]: https://private.codecogs.com/gif.latex?key1
[key2]: https://private.codecogs.com/gif.latex?key2
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200101111135144.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[T_h_x_ key]: https://private.codecogs.com/gif.latex?T%5Bh%28x%2C%20key%29%5D
[T_j]: https://private.codecogs.com/gif.latex?T%5Bj%5D
[h_k_1]: https://private.codecogs.com/gif.latex?h%28k_%7B1%7D%29
[h_k_4]: https://private.codecogs.com/gif.latex?h%28k_%7B4%7D%29
[n_j 1]: https://private.codecogs.com/gif.latex?n_%7Bj%7D
[n _ n_0_ _ n_1_ _ ... _ n_m-1]: https://private.codecogs.com/gif.latex?n%20%3D%20n_%7B0%7D%20&plus;%20n_%7B1%7D%20&plus;%20...%20&plus;%20n_%7Bm-1%7D
[E_n_j_ _ a _ n _ m]: https://private.codecogs.com/gif.latex?E%5Bn_%7Bj%7D%5D%20%3D%20a%20%3D%20n%20/%20m
[T_h_k]: https://private.codecogs.com/gif.latex?T%5Bh%28k%29%5D
[n_h_k]: https://private.codecogs.com/gif.latex?n_%7Bh%28k%29%7D
[Theta _1_a]: https://private.codecogs.com/gif.latex?%5CTheta%20%281&plus;a%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200106112302175.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[h_U]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%3AU%20*
[0_ 1_ ..._ m-1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%200%2C%201%2C%20...%2C%20m-1
[rightarrow]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Crightarrow
[h_k_0_h_k_1_..._h_k_m-1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%28k%2C0%29%2Ch%28k%2C1%29%2C...%2Ch%28k%2Cm-1%29
[f_i_key_ _ _f_key_ _ d_i]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20f_%7Bi%7D%28key%29%20%3D%20%28f%28key%29%20&plus;%20d_%7Bi%7D%29
[d_i_ _1_2_3_..._m-1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%28d_%7Bi%7D%20%3D1%2C2%2C3%2C...%2Cm-1%29
[f_key_ _ key 1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20f%28key%29%20%3D%20key
[20200104131040709.png]: https://img-blog.csdnimg.cn/20200104131040709.png
[20200104133036234.png]: https://img-blog.csdnimg.cn/20200104133036234.png
[20200104133338698.png]: https://img-blog.csdnimg.cn/20200104133338698.png
[d_i_ _ 1_2_-1_2_2_2_-2_2_..._q_2_-q_2_q_leq m_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20d_%7Bi%7D%20%3D%201%5E%7B2%7D%2C-1%5E%7B2%7D%2C2%5E%7B2%7D%2C-2%5E%7B2%7D%2C...%2Cq%5E%7B2%7D%2C-q%5E%7B2%7D%2C%28q%5Cleq%20m/2%29
[d_i]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20d_%7Bi%7D
[d_i_ _ 1_2_-1_2_2_2_-2_2_..._q_2_-q_2_q_leq m_2 1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%28d_%7Bi%7D%20%3D%201%5E%7B2%7D%2C-1%5E%7B2%7D%2C2%5E%7B2%7D%2C-2%5E%7B2%7D%2C...%2Cq%5E%7B2%7D%2C-q%5E%7B2%7D%2Cq%5Cleq%20m/2%29
[h_k_ i_ _ _h_k_c_1_i_c_2_x_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%28k%2C%20i%29%20%3D%20%28h%5E%7B%27%7D%28k%29&plus;c_%7B1%7Di&plus;c_%7B2%7Dx%5E%7B2%7D%29
[h 1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%5E%7B%27%7D
[c_1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20c_%7B1%7D
[c_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20c_%7B2%7D
[i _ 0_1_..._m-1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20i%20%3D%200%2C1%2C...%2Cm-1
[T_h_k 1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20T%5Bh%5E%7B%27%7D%28k%29%5D
[h_k_1_0_h_k_2_0]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%28k_%7B1%7D%2C0%29%3Dh%28k_%7B2%7D%2C0%29
[h_k_1_i_h_k_2_i]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%28k_%7B1%7D%2Ci%29%3Dh%28k_%7B2%7D%2Ci%29
[h_k_i_h_1_k_ih_2_k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h%28k%2Ci%29%3D%28h_%7B1%7D%28k%29&plus;ih_%7B2%7D%28k%29%29
[h_1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B1%7D
[h_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B2%7D
[T_h_1_k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20T%5Bh_%7B1%7D%28k%29%5D
[h_2_k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B2%7D%28k%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200105214637475.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[h_1_k_k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B1%7D%28k%29%3Dk
[h_2_k_1_k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B2%7D%28k%29%3D1&plus;%28k
[m 2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20m%5E%7B%27%7D
[h_1_k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B1%7D%28k%29%3D
[h_2_k 1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B2%7D%28k%29%3D
[equiv]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Cequiv
[gif.latex_5Cdpi_7B120_7D_20_28]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%28
[Theta _m_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5CTheta%20%28m%5E%7B2%7D%29
[Theta _m]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5CTheta%20%28m%29
[h_1_k 1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20h_%7B1%7D%28k%29
[phi _m_ _ m]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Cphi%20%28m%29%20/%20m
[d_i 1]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%28d_%7Bi%7D
[leqslant]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%5Cleqslant
[RH_i]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20RH_%7Bi%7D
[f_i_key_RH_i_key]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20f_%7Bi%7D%28key%29%3DRH_%7Bi%7D%28key%29
[i_1_2_..._k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20%28i%3D1%2C2%2C...%2Ck%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200106113118478.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[Link 1]: https://baike.baidu.com/item/%E8%8A%AD%E8%8A%AD%E6%8B%89
[RIPEMD]: https://baike.baidu.com/item/RIPEMD
[Link 2]: https://baike.baidu.com/item/%E5%AF%86%E7%A0%81%E7%AE%97%E6%B3%95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20210719145951510.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpbnhpYW4yMDEyMA==,size_16,color_FFFFFF,t_70
[MFTP]: https://baike.baidu.com/item/MFTP
[Link 3]: https://baike.baidu.com/item/%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95
[Link 4]: https://baike.baidu.com/item/%E5%AE%A2%E6%88%B7%E7%AB%AF
[Link 5]: https://baike.baidu.com/item/%E6%96%87%E4%BB%B6%E6%A0%A1%E9%AA%8C
[Link 6]: https://baike.baidu.com/item/%E9%9D%9E%E6%B3%95%E5%85%B3%E6%9C%BA