哈希表的查找（按照除留余数法设计一个哈希函数）

给定一组查找关键字(32,15,7,11,4,28,56,61,79)，哈希表长为m=12，请按照除留余数法设计一个哈希函数，设每个记录的查找概率相等。

（1）画出按照线性探测再散列处理冲突得到的哈希表（给出求解过程），并计算等概率情况下查找成功和查找失败时的平均查找长度各是多少。 （2）画出按照链地址法处理冲突得到的哈希表，并计算等概率情况下查找成功和查找失败时的平均查找长度各是多少。

设计哈希函数为： H（key）= key % 11

（1）按照线性探测再散列处理冲突 查找成功时平均查找长度： ASL = （1+1+1+1+2+1+1+3+1）/ 9 = 4/3

查找失败时平均查找长度： ASL = （4+3+2+1+6+5+4+3+2+1+2）/ 11 = 3

在这里计算时注意： 由于Hash函数为H（key）= key % 11，H（key）=0~10；因此查找失败可能对应的地址有11个，所以除以11。

（2）按照链地址法处理冲突 查找成功时平均查找长度

ASL = （7 * 1 + 2 * 2）/ 9 = 11/9

查找失败时平均查找长度

ASL = （0 * 5 + 1 * 5 + 2 * 2）/ 11 = 9/11 又叫装填因子

装填因子α = 表中记录数 / 散列表长度