考研笔记-计算机之数据结构:集合结构-查找表(哈希表)

——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。

哈希表

哈希函数：建立在“比较”的基础上的查找方法中，顺序查找的比较结果为“=”和“≠”两种可能，折半查找、二叉排序树查找和B-树查找的比较结果为“<”、“=”和“>”三种可能。查找的效率依赖于查找过程中所进行的比较次数。理想的情况是不经过任何比较，一次存取便能得到所查记录，为此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应，称该对应关系f为哈希函数，按该思想建立的表为哈希表。哈希函数是关键字集合到地址集合的映像，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可。

哈希表：根据设定的哈希函数和冲突处理方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表（（哈希）表的地址空间是事先已知的，哈希函数和冲突处理方法需根据（哈希）表的地址空间来确定），这一映像过程称为散列（散列=哈希函数+冲突处理），所得到的存储位置称为哈希地址或散列地址。

冲突：不同的关键字可能得到相同的哈希地址，这种现象称为冲突。一般情况下，哈希函数是一个压缩映像，这就不可避免产生冲突。

同义词：具有相同函数值的关键字对该哈希函数来说称为同义词。

二次聚集：在处理冲突过程中发生的两个第一个（即由哈希函数得到的）哈希地址不同的记录争夺同一个后继（即由冲突处理方法得到的）哈希地址的现象（即在处理同义词的冲突过程中又添加了非同义词的冲突）称为二次聚集。

哈希函数的构造方法

（1）直接定址法

取关键字的某个线性函数值（如关键字本身）为哈希地址。。

（2）数字分析法

适用条件：关键字是以r为基的数，且哈希表中可能出现的关键字都是事先知道的。

构造方法：取关键字的若干数位（取的位数由表长决定，具体取哪些位依据的原则是使得到的哈希地址尽量避免冲突）组成哈希地址。

（3）平方取中法

适用条件：无法知道关键字的全部情况。

构造方法：取关键字平方后的中间几位（取的位数由表长决定）为哈希地址。（原理：一个数平方后的中间几位数和数的每一位都相关（可根据乘法竖式来理解），由此使随机分布的关键字得到的哈希地址也是随机的）

（4）折叠法

适用条件：关键字位数很多，且关键字中每一位上数字分布大致均匀。

构造方法：将关键字分割成位数相同的几部分（最后一部分的位数可以与其他部分的位数不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。（折叠法分为移位叠加和间界叠加，移位叠加是将分割后的每一部分的最低位对齐然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。）

（5）除留余数法

适用条件：不仅可以对关键字直接取模，而且可以在折叠、平方取中等运算之后取模。

构造方法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即。（若p>m，则H(key)可能大于m，这样得到的哈希地址便超出了哈希表的地址空间。若p含有质因子pf，则所有含有pf质因子的关键字的哈希地址均为pf的倍数（证明：令，，则。可将因子看作基本单位）。一般可以选取p为质数或不包含小于20的质因数的合数。）

（6）随机数法

适用条件：关键字的长度不等。

构造方法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即，其中random为随机函数。

冲突处理，即为冲突的该关键字的记录找到另一个“空”（未占用）的哈希地址。

冲突处理方法

（1）开放定址法

（），其中，为哈希函数，m为哈希表表长，为增量序列（每次增量均是在由哈希函数得到的哈希地址的基础上进行，而不是在由冲突处理方法得到的新哈希地址的基础上进行）。

1）时，称为线性探测再散列；（不会一直探测下去，当满足①新哈希地址单元为空，即存在可用空间；或②满足，即已探测完一圈，无可用的空间，则可结束。）

2）时，称为二次探测再散列；

3）=伪随机序列时，称为伪随机探测再散列。

（2）再哈希法

，，其中，均是不同的哈希函数，即在同义词产生地址冲突时计算关键字（哈希函数的自变量为关键字）的另一个哈希函数地址，直到冲突不再发生。

（3）链地址法

将所有关键字为同义词的记录存储在同一线性链表中，并保持同义词在同一线性链表中按关键字有序。（各个代表不同同义词的线性链表的首地址由哈希函数确定，即各个线性链表的头结点应为顺序存储。）

（4）建立公共溢出区

哈希表由基本表和溢出表组成，所有关键字和基本表中关键字为同义词的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。（该方法相当于将链地址法中的各个同义词独有的线性链表合并为一个公共溢出表）

哈希表的查找

按哈希函数和冲突处理方法找到的存储位置中的关键字与查找的关键字相同时则查找成功，只有按哈希函数和冲突处理方法找到的存储位置为空（关键字字段为空）时，才认为查找失败。

由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。因此仍需以平均查找长度作为衡量哈希表的查找效率的度量。

查找过程中需和给定值进行比较的关键字的个数取决于下列三个因素：哈希函数、冲突处理方法和哈希表的装填因子。

哈希表的装填因子α=表中填入的记录数/哈希表的长度。α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。哈希表的平均查找长度是α的函数，而不是记录总数n的函数。无论n多大，总可以找到一个合适的装填因子将平均查找长度限定在一个范围之内。

哈希表的插入

哈希表的插入即使用所采用的哈希函数和冲突处理方法构造哈希表。

哈希表的删除

文章合集：