第三章 31 哈希表

1、什么是哈希表什么是哈希表设表的长度为设表的长度为n n，如果存在一个函数，如果存在一个函数i= i(k),i= i(k),对于对于表中的任意一个元素的关键字表中的任意一个元素的关键字k k，满足，满足 则称此表为则称此表为HashHash表。其中函数表。其中函数i= i(k)i= i(k)称为关键字称为关键字k k的的HashHash码。码。ni 1Hash表技术的关键是要处理好表中元素的冲突问题，表技术的关键是要处理好表中元素的冲突问题，它主要包括以下两方面的工作：它主要包括以下两方面的工作：构造合适的构造合适的Hash码，以便尽量减少表中元素冲突码，以便尽量减少表中元素冲突的次数，即的次数

2、，即Hash码的均匀性要比较好。码的均匀性要比较好。当表中元素发生冲突时，要进行适当的处理。当表中元素发生冲突时，要进行适当的处理。Hash码的构造码的构造 Hash表技术的主要目标是提高查找效率，即缩表技术的主要目标是提高查找效率，即缩短查表的时间。短查表的时间。截断法。是指选取与关键字对应的数字串中的截断法。是指选取与关键字对应的数字串中的一段（一般选取低位数）作为该关键字的一段（一般选取低位数）作为该关键字的Hash码。码。分段叠加法。将关键字的编码串分割成若干段，分段叠加法。将关键字的编码串分割成若干段，然后把他们叠加后再进行截段。然后把他们叠加后再进行截段。除法。将关键字的编码除以表

3、的长度，最后所除法。将关键字的编码除以表的长度，最后所得的余数作为得的余数作为Hash码，即取码，即取Hash码为码为i=mod(k,n)(当当mod(k,n)0时，取时，取i=n)本方法构造的本方法构造的Hash码，其均匀性比较好，但是以码，其均匀性比较好，但是以一次除法为代价，在除法较快的机器上可以采一次除法为代价，在除法较快的机器上可以采用。用。乘法。将关键字编码与一个常数乘法。将关键字编码与一个常数 相乘后，相乘后，再除以表长度再除以表长度n，取其余数作为，取其余数作为Hash码码线性线性Hash表是一种最简单的表是一种最简单的Hash表。表。设线性表的长度为设线性表的长度为n，则将关

4、键字，则将关键字k及有关信息及有关信息填入线性填入线性Hash表的步骤如下：表的步骤如下：计算关键字计算关键字k的的Hash码码i=i(k).检查表中第检查表中第i项的内容：项的内容：若第若第i项为空，则将关键字项为空，则将关键字k及有关信息填入该项；及有关信息填入该项；若第若第i项不空，则令项不空，则令i=mod(i+1，n)，转，转继续检查。继续检查。1.线性线性hash表表线性线性Hash表的取出表的取出计算关键字计算关键字k的的Hash码码i=i(k).检查表中第检查表中第i项的内容：项的内容：若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；，则取出该项元素即可；若第若第

5、i项为空，则表示在项为空，则表示在Hash表中没有该关键字的信表中没有该关键字的信息；息；若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则令，则令i=mod(i+1,n)，转，转继续检查。继续检查。线性表的优缺点：线性表的优缺点：优点：简单优点：简单缺点：缺点：在线性在线性Hash表填入的过程中，当发生冲突表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当时，首先考虑的是下一项，因此，当Hash码的冲码的冲突较多时，在线性突较多时，在线性Hash表中会存在表中会存在“堆聚堆聚”现象，现象，即许多关键字被连续登记在一起，从而会降低查即许多关键字被连续登记在一起，从而会

6、降低查找效率。找效率。在线性在线性Hash表的填入过程中，处理冲突时会带来表的填入过程中，处理冲突时会带来新的冲突，即线性新的冲突，即线性Hash表的填入方法是表的填入方法是不顾后效不顾后效的的。2.随机随机Hash表表 当当Hash表的长度表的长度n设计成设计成n=2m时时,还可以定还可以定义另外一种义另外一种Hash表表随机随机Hash表。随机表。随机Hash表与线性表与线性Hash表的不同之处在于：一表的不同之处在于：一旦发生元素冲突时，表项序号旦发生元素冲突时，表项序号i的改变不是的改变不是采用加采用加1取模的方法，而是用某种伪随机数取模的方法，而是用某种伪随机数来改变。来改变。随机随

7、机Hash表的填入：表的填入：计算关键字计算关键字k的的Hash码码i0=i(k)，且令，且令i=i0.伪随机数序列初始化，令伪随机数序列初始化，令j=1（将随机数指针指向（将随机数指针指向伪随机数序列的第伪随机数序列的第1个随机数）个随机数）检查表中第检查表中第i项的内容：项的内容：若第若第i项为空，则将关键字项为空，则将关键字k及有关信息填入该项；及有关信息填入该项；若第若第i项不空，则令项不空，则令i=mod(i0+RN(j)，n)，并令，并令j=j+1（将随机数指针指向下一个随机数），转（将随机数指针指向下一个随机数），转继续继续检查。检查。随机随机Hash表的取出：表的取出：计算关键

8、字计算关键字k的的Hash码码i0=i(k)，且令，且令i=i0伪随机数序列初始化，令伪随机数序列初始化，令j=1（将随机数指针指向伪随机（将随机数指针指向伪随机数序列的第数序列的第1个随机数）。个随机数）。检查表中第检查表中第i项的内容：项的内容：若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；，则取出该项元素即可；若第若第i项为空，则表示在项为空，则表示在Hash表中没有该关键字的信息；表中没有该关键字的信息；若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则令，则令i=mod(i0+RN(j)，n)，并令，并令j=j+1（将随机数指针指向下一个随机数），转

9、（将随机数指针指向下一个随机数），转继续检查。其中继续检查。其中RN(j)表示伪随机数序列表示伪随机数序列RN中的第中的第j个个随机数。随机数。3.溢出溢出Hash表表 线性线性Hash表与随机表与随机Hash表均存在两个致命的缺表均存在两个致命的缺点：一是在点：一是在Hash表填入过程中不顾后效，从而表填入过程中不顾后效，从而在填入过程中其冲突的机会在不断增多；二是在填入过程中其冲突的机会在不断增多；二是当当Hash表填满时，不能正常地进行查找。如果表填满时，不能正常地进行查找。如果将冲突的元素安排在另外的空间内，而不占用将冲突的元素安排在另外的空间内，而不占用Hash表本身的空间，则不会产

10、生新的冲突，这表本身的空间，则不会产生新的冲突，这就是溢出就是溢出Hash表。表。 溢出溢出Hash表包括表包括Hash表表和和溢出表溢出表两部分。在两部分。在Hash表的填入过程中，将冲突的元素顺序填入溢表的填入过程中，将冲突的元素顺序填入溢出表，而当查找过程中发现冲突时，就在溢出表出表，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。中进行顺序查找。溢出表的填入过程：溢出表的填入过程：计算关键字计算关键字k的的Hash码码i=i(k).检查表中第检查表中第i项的内容：项的内容：若第若第i项为空，则将关键字项为空，则将关键字K及有关信息填入该项；及有关信息填入该项；若第若第i项不空，则将

11、关键字项不空，则将关键字k及有关信息依次填入溢及有关信息依次填入溢出表中的自由项出表中的自由项。溢出溢出Hash表的取出：表的取出：计算关键字计算关键字k的的Hash码码i=i(k).检查表中第检查表中第i项内容：项内容：若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；，则取出该项元素即可；若第若第i项为空，则表示在项为空，则表示在Hash表中没有该关键字的信表中没有该关键字的信息；息；若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则转入在溢，则转入在溢出表中进行顺序查找。出表中进行顺序查找。4.拉链拉链Hash表表-1 拉链拉链Hash表分为外链表分为外链Hash表与内链表与内链Hash表。我表。我们只讨论外链们只讨论外链Hash表。表。 外链外链Hash表由表由Hash表及表外结点所组成。在表及表外结点所组成。在Hash表中登记的并不是关键字表中登记的并不是关键字k及有关信息，而及有关信息，而只是登记指针。只是登记指针。外链外链Hash表的填入：表的填入：计算关键字计算关键字k的的Hash码码i=i(k).取得一个新结点取得一个新结点p，并将关键字，并将关键字k及有关信息填入及有关信息填入结点结点p。将结点将结点p链入以链入以H(i)为头指针的链表的链头。为头指针的链表的链头。4.拉链拉链Hash表表-2外链外链HashH