5.3 散列（Hash）表及其查找

二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：设散列表长度为14 ，散列函数 ，其中i为健值中第一个字母在字母表中的序号，若健值的输入顺序为Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec，用拉链法处理冲突，要求：
　　（1）构造散列表。（2）求出在等概率情况下，查找成功或失败时的平均查找长度。
　　● 习题2：有一个文件F={53,17,12,61,98,70,87,25,63,46,14,59,67,75}，请为F组织散列表。散列函数以“除留余数法”求得，发生冲突时，以开放定地址法中的二次探测再散列解决，设可用于建表的地址空间为18个单元，起始地址的相对地址为零。请设计该表的成功查找的平均查找长度。
　　2．综合应用题答案与分析
　　习题1分析：
　　（1）按拉链法构造的散列表如图5-3所示。
　　（2）在等概率的情况下，链地址解决冲突的哈希表查找成功的平均查找长度由在各链表中进行顺序查找的比较次数组成。因此ASL_unsucc＝(7×1 + 3×2 + 2×3)/12=19/12。
　　在查找不成功时的比较次数是碰到空指针就算查找失败，在第4、6、9、11、12、13、14链表中各失败1次。在第2、3、8、10链表中各失败2次。在第1链表中失败3次。在第5、7链表中失败4次，因此ASL_unsucc＝(7×1 + 4×2 + 1×3 + 2×4)/14 = 26/14。

图5-3 按拉链法构造的散列表

　　习题2分析：
　　地址空间数m=18，因此应该选择最接近于m的一个素数17作为除数，即p=17，则H(k)=kmod17。

　　成功比较次数：
　　　　　　　　　H(53)=53 MOD 17=2 比较1次
　　　　　　　　　H(17)=17 MOD 17=0 比较1次
　　　　　　　　　H(12)=12 MOD 17=12 比较1次
　　　　　　　　　H(61)=61 MOD 17=10 比较1次
　　　　　　　　　H(98)=98 MOD 17=13 比较1次
　　　　　　　　　H(70)=70 MOD 17=2 冲突
　　　　　　　　　H(70)=(2+1²) MOD 18=3 比较2次
　　　　　　　　　H(87)=87 MOD 17=2 冲突
　　　　　　　　　H(87)=(2+1²) MOD 18=3 冲突
　　　　　　　　　H(87)=(2-1²) MOD 18=1 比较3次
　　　　　　　　　H(25)=25 MOD 17=8 比较1次
　　　　　　　　　H(63)=63 MOD 17=12 冲突
　　　　　　　　　H(63)=(12+1²) MOD 18=13 冲突
　　　　　　　　　H(63)=(12-1²) MOD 18=11 比较3次
　　　　　　　　　H(46)=46 MOD 17=12 冲突
　　　　　　　　　H(46)=(12+1²) MOD 18=13 冲突
　　　　　　　　　H(46)=(12-1²) MOD 18=11 冲突
　　　　　　　　　H(46)=(12+2²) MOD 18=16 比较4次
　　　　　　　　　H(14)=14 MOD 17=14 比较1次
　　　　　　　　　H(59)=59 MOD 17=8 冲突
　　　　　　　　　H(59)=(8+1²) MOD 18=9 比较2次
　　　　　　　　　H(67)=67 MOD 17=16 冲突
　　　　　　　　　H(67)=(16+1²) MOD 18=17 比较2次
　　　　　　　　　H(75)=75 MOD 17=7 比较1次
　　平均查找长度：　　　　　
　　
　　3．训练自测表（如表5-6所示）

表5-6 选择题练习自测表