哈希表的散列线性探测排序问题
哈希表的散列线性探测排序问题
题目：给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)
哈希函数为：H(key)=key % 13, 哈希表长为m=15，设每个记录的查找概率相等。
- 请画出按照线性探测再散列处理冲突得到的哈希表（给出求解过程），并计算查找成功和查找失败时的平均查找长度各是多少。
- 请画出按照链地址法处理冲突得到的哈希表，并计算查找成功和查找失败时的平均查找长度各是多少。
题目分析：
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
本题中所要求的线性探测排序值的是：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。
一、下图为本题的线性排序结果：
（最后构建成的哈希线性探测排序组合为图中黄色荧光笔画出部分）
二、计算线性探测平均查找次数
平均成功查找次数=每个关键词比较次数之和÷关键词的个数
平均不成功查找次数=每个位置不成功时的比较次数之和÷表长（所谓每个位置不成功时的比较次数就是在除余位置内，每个位置到第一个为空的比较次数）
ASL s=（1+1+2+1+3+4+1+1+2+1+1+2）/12=23/12
ASL u=（10+9+8+7+6+5+4+3+2+1+2+3+4）/13= 64/13
三、下图为链地址法处理冲突得到的哈希表：
四、计算链地址存储法平均查找次数
总查找次数: 1+1+2+3+4+1+1+2+1+1+2+1=20
成功时平均查找次数：（1X5+2X4+3X1+4X1）/12=5/3
失败时平均查找次数：（4+2+2+1+2+1）/11 =1
注意：链地址法成功时查找次数的分母是哈希表元素的个数，分子为纵向比较；
失败时，分母为哈希表的长度，分子为横向比较（几个）。
（如有错误，敬请指正）