数据结构课件：第9章 查找4哈希表

1、第9章 查找查找的基本概念静态查找表动态查找表哈希表哈希表(Hash Tables)9.3 哈希表 也被称为散列表，是普通数组概念的推广。因为可以对数组进行直接寻址，故可以在O(1)时间内访问到数组的任意元素。哈希表(Hash Tables)9.3 哈希表 当关键字全域比较小的时候，利用数组(直接寻址表)是一种简单有效的技术。哈希表(Hash Tables)9.3 哈希表直接寻址技术存在的问题： 如果全域U很大，在计算机中存储大小为|U|的一张表T就有点不实际，甚至是不可能的。 实际的应用中，要存储的关键字集合K，相对U来说很小，因此分配给T的大部分空间会被浪费。哈希表(Hash Tables

2、)9.3 哈希表 给定关键字，期望通过计算，即利用哈希函数h(x)计算出关键字在表T中的位置。哈希表(Hash Tables)9.3 哈希表 在直接寻址方式下，具有关键字k的数据元素，存放在槽k中。 在哈希方式下，具有关键字k的数据元素，存放在槽h(k) 中。其中h(x)是散列函数。 碰撞(collision)Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dai 例如：对于如下 9 个关键字： 设哈希函数 f (key) = (Ord(关键字首字母) - Ord(A) + 1) / 2 问题: 若添加关键字 Zhou，会出现什么情况 ？ 0 1 2 3 4 5

3、 6 7 8 9 10 11 12 13 Dai Chen Zhao Qian Sun Li Wu Han Ye 从这个例子可见： 1) 哈希函数是一个映像，即：将关键字的集合映射到某个地址 集合上。它的设置很灵活，只要使得关键字的哈希函数值都 落在表长允许的范围之内即可； 2) 由于哈希函数是一个压缩映像，因此，在一般情况下，很容 易产生“冲突”现象，即：key1 key2，而 f (key1) = f (key2)。 这种具有相同函数值的关键字称为同义词。 Zhou Zhou 3) 很难找到一个不产生冲突的哈希函数。一般情况下，只能 选择恰当的哈希函数，使冲突尽可能少地产生。 因此：在构造

4、这种特殊的“查找表”时，除了需要选择一个“好”的哈希函数(其原则是尽可能地使任意一组关键字的哈希地址均匀地分布在整个地址空间中，即用任意关键字作为哈希函数的自变量其计算结果随机分布，以尽可能少产生冲突) ； 还需要找到一种“处理冲突”的方法。 哈希表(Hash Tables)9.3 哈希表哈希表的定义 根据设定的哈希函数H(key)和所选中的处理冲突的方法建立的查找表。其基本思想是：以记录的关键字为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容。 这一映像过程称为哈希造表或散列。 哈希表(Hash Tables)9.3 哈希表 当对记录进行查找时，再根据给定的关键字，用同一

5、个哈希函数计算出给定关键字对应的存储地址，随后进行访问。所以哈希表既是一种存储形式，又是一种查找方法，通常将这种查找方法称为哈希查找。 哈希函数的构造方法 9.3 哈希表对数字关键字可有下列构造方法： 对非数字关键字，常用字符串哈希函数有1. 直接定址法 3. 平方取中法 5. 除留余数法 4. 折叠法 6. 随机数法 2. 数字分析法 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等直接定址法 9.3 哈希表 取关键字或关键字的某个线性函数值为散列地址，即哈希函数为关键字的线性函数 H(key) = key 或者

6、 H(key) = a key + b (其中a、b为常数) 例：关键码集合为 100，300，500，700，800，900 ，选取哈希函数为 Hash(key)=key/100，画初存储结构(哈希表)0 1 2 3 4 5 6 7 8 9900800700500300100直接定址法 9.3 哈希表特点：地址集合的大小 = 关键字集合的大小。 优点：以关键码 key 的某个线性函数值为哈希地址， 不会产生冲突。缺点：要占用连续地址空间，空间效率低。 实际中能使用这种哈希函数的情况很少数字分析法9.3 哈希表选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同

7、。 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。 数字分析法9.3 哈希表3 4 7 0 5 2 4 3 4 9 1 4 8 73 4 8 2 6 9 63 4 8 5 2 7 03 4 8 6 3 0 53 4 9 8 0 5 83 4 7 9 6 7 13 4 7 3 9 1 9例：有一组（例如80个）关键码，其样式如下：讨论： 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号： 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低

8、两位作哈希地址。平方取中法（较常用） 9.3 哈希表构造：以关键字的平方值的中间几位作为哈希地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中 间各位又能受到整个关键字中各位的影响。 此方法适合于：关键字中的每一位都有某些数字重复出现频度很高的现象。例：2589的平方值为6702921，可以取中间的029为地址。 折叠法9.3 哈希表 构造：将关键字分割成位数相同的几部分，然后取这几部分 的叠加和（舍去进位）做哈希地址。 移位叠加：将分割后的几部分低位对齐相加。 间界叠加：从一端沿分割界来回折叠，然后对齐相加。 适于关键字位数很多，且每一位上数字分布大致均匀情况折叠法9.3 哈希表

9、例：关键字为：0442205864，哈希地址位数为 4。 5 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加例：元素42751896, 移位法： 42751896=1041 间界叠加法： 427 518 96 724+518+69=1311除留余数法(最常用)9.3 哈希表 构造：取关键字被某个不大于哈希表表长 m 的数 p 除后所得 余数作哈希地址，即 H(key) = key MOD p， p m。 特点：简单，可与上述几种方法结合使用。 p 的选取很重要；p 选得不好，容易产生

10、同义词。 p 应为不大于 m 的素数或不含 20 以下的质因子的合数。 除留余数法(最常用)9.3 哈希表331224391821012345678910给定一组关键字：12, 39, 18, 24, 33, 21，若取 p = 11, 则他们对应的哈希函数值将为除留余数法(最常用)9.3 哈希表181224012345678910给定一组关键字：12, 39, 18, 24, 33, 21，若取 p = 9, 则他们对应的哈希函数值将为393321 可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。 随机数法 9.3 哈希表

11、构造：取关键字的随机函数值作哈希地址，即： H(key) = Random(key)其中，Random是伪随机函数。 通常，当关键字长度不等时采用此法构造哈希函数较恰当哈希函数的构造方法 9.3 哈希表 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况（包括关键字的范围和形态），总的原则是使产生冲突的可能性降到尽可能地小。 选取哈希函数，考虑以下因素： 1）计算哈希函数所需时间 2）关键字长度 3）哈希表长度（哈希地址范围） 4）关键字分布情况 5）记录的查找频率处理冲突的方法 9.3 哈希表 “处理冲突” 的实际含义是：为产生冲突的地址寻找另一个哈希地址。1.开放地址法 (

12、1)线性探测法 (2)二次探测法 (3)伪随机探测法2.链地址法3.再哈希法4.建立一个公共溢出区开放地址法 9.3 哈希表(1)线性探测法 设散列函数H(K)=K mod m (m为表长)，若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为：Hi = ( H(K)+di ) mod m (di=1,2,m-1) 开放地址法 9.3 哈希表例：关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表：0 1 2 3 4 5 6 7 8 9 10477291

13、116922283开放地址法 9.3 哈希表线性探测法的优点：只要哈希表未被填满，保证能找到一 个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第 i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。可采用二次探测法或伪随机探测法，以改善“堆积”问题开放地址法 9.3 哈希表(2)二次探测法 二次探测法对应的探查地址序列的计算公式为：Hi = ( H(K)+di ) mod m 其中di =12,-12,22,-22, j2, -j2 ( jm/2)。开

14、放地址法 9.3 哈希表0 1 2 3 4 5 6 7 8 9 10112234792167298例：关键码集为 47，7，29，11，16，92，22，8，3，设：哈希表表长为m=11； 哈希函数为Hash(key)= key mod 11； 拟用二次探测法处理冲突。建哈希表如下：Hi = ( H(K)+di ) mod m 其中di =12, -12, 22,-22, j2, -j2 ( jm/2)。开放地址法 9.3 哈希表(3) 伪随机探测法 伪随机探测法对应的探查地址序列的计算公式为：Hi = ( H(K)+di ) mod m 其中di =伪随机序列例：表长为 11 的哈希表中已填

15、有关键字为 17，60，29 的记录， H(key)=key MOD 11，现有第 4 个记录，其关键字为 38， 按三种处理冲突的方法，将它填入表中。 0 1 2 3 4 5 6 7 8 9 1060 17 29 (1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突 38 (2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5-1) MOD 11=4 不冲突 38 (3) H(38)=38 MOD 11=5 冲突 设伪随机

16、数序列为 9，则： H1=(5+9) MOD 11=3 不冲突 38 链地址法9.3 哈希表优点：插入、删除方便。缺点：占用存储空间多。基本思想： 将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。例：已知一组关键字 (19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 哈希函数为：H(key)=key MOD 13，用链地址法处理冲突。 0 1 2 3 4 5 6 7 8 9 10 11 12 14 68 192023 11 1 55 8410 27 79 再哈希法9

17、.3 哈希表Hi= RHi(key) RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。 溢出区法 9.3 哈希表 除基本的存储区外(称为基本表)，另外建立一个公共溢出区(称为溢出表)，当发生冲突时，记录可以存入这个公共溢出区。 哈希表的应用 9.3 哈希表“冲突”是不是特别讨厌？答：不一定！正因为有冲突，使得文件加密后无法破译（不可逆，是单向散列函数，可用于数字签名）。利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。哈希表的应用 9.3 哈希表 哈希(Hash)函数在中文中有很多译名，有些人根据Hash

18、的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。 哈希表的应用 9.3 哈希表1、Hash算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定长度的数据，即哈希值。哈希值也称为输入数据的数字指纹（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函数具备以下的性质：2、给定输入数据，很容易计算出它的哈希值；3、反过来，给定哈希值，倒推出输入数据则很难，计算上不可行。这就是哈希函数的单向性，在技术上称为抗原像攻

19、击性； 4、给定哈希值，想要找出能够产生同样的哈希值的两个不同的输入数据，(这种情况称为碰撞，Collision)，这很难，计算上不可行，在技术上称为抗碰撞攻击性； 5、哈希值不表达任何关于输入数据的信息。哈希表的应用 9.3 哈希表 Hash算法在信息安全方面的应用主要体现在以下的3个方面： (1) 文件校验(2) 数字签名(3) 鉴权协议 哈希表的查找及其分析9.3 哈希表 散列表的目的主要是用于快速查找。 在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。哈希表的查找及其分析9.3 哈希表例：设有一组关键字 19, 01, 23, 14, 55

20、, 20, 84, 27, 68, 11, 10, 77 ，采用哈希函数为：H(k)= k mod 13。采用开放地址的线性探测法解决冲突，试在018的散列地址空间中，对该关键字序列构造哈希表。解：依题意 m=19，得到线性探测法对应的探查地址序列计算公式为：di=( H(k) + j ) mod 19; j=1,2,18H(19)=19 mod 13=6H(01)=01 mod 13=1H(23)=23 mod 13=10H(14)=14 mod 13=1 (冲突)H(14)=(1+1) mod 19=2H(55)=55 mod 13=3H(20)=20 mod 13=7H(84)=84 m

21、od 13=6 (冲突)H(84)=(6+1) mod 19=7 (冲突)H(84)=(6+2) mod 19=8H(27)=27 mod 13=1（冲突）H(27)=(1+1) mod 19=2 (冲突)H(27)=(1+2) mod 19=3 (冲突)H(27)=(1+3) mod 19=4012345678910111213141516171819 19,01,23,14,55,20,84,27,68,11,10,77 0123145520842777101168 哈希查找的性能分析9.3 哈希表 哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由

22、于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。哈希查找的性能分析9.3 哈希表1.线性探查法的性能分析 由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H(x)及装填因子的值和该处理方法有关。 这时的成功的平均查找长度为：ASL= (1+1/(1-)/2哈希查找的性能分析9.3 哈希表2.链地址法查找的性能分析 由于链地址法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。 平均查找长度：ASL=1+/2哈希查找的性能分析9.3 哈希表例：给定关键字序列11,78,10,1,

23、3,2,4,21，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、哈希查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种哈希查找的哈希表)，并求出每一种查找的成功平均查找长度。哈希函数H(k)=k mod 11。哈希查找的性能分析9.3 哈希表顺序查找的顺序表(一维数组)由图可得：顺序查找的成功平均查找长度为ASL=(1+2+3+4+5+6+7+8)/8=4.511,78,10,1,3,2,4,21117810132421012345678910哈希查找的性能分析9.3 哈希表折半查找的判定树二分查找的成功平均查找长度为ASL=(1*1+2*2+3*4+4*1)/8=2.62511,78,10,1,3,2,4,21178210211143哈希查找的性能分析9.3 哈希表11,78,10,1,3,2,4,21 二叉排序树 平衡二叉树111078123421311122147810ASL=(1+2*2+3*2+4+5*2)/8=3.125ASL=(1+2*2+3*3+4*2)/8=2.75哈希查找的性能分析9.3 哈希表11,78,10,1,3