哈希表查找

最近复习数据结构中的哈希表，发现在计算等概率情况下查找不成功的平均查找长度时不太理解，不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了，总结如下。

例题：

将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

（1）请画出所构造的散列表。

（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。

（1）首先明确一个概念：装载因子。装载因子是指所有关键子填充哈希表后饱和的程度，它等于 填入表中的关键字总数/哈希表的长度。

根据题意，我们可以确定哈希表的长度为 L = 7/0.7 = 10；因此此题需要构建的哈希表是下标为0~9的一维数组。

这里采用线性探测再散列法处理冲突，构造散列表。

       H(7) = (7x3) MOD 7 = 0，地址为0，因此放到散列表的数组下表为0的位置，这个位置上没有关键字，因此没有冲突可以直接填入；

       H(8) = (8x3) MOD 7 = 3，地址是3，因此放到散列表的数组下表为3的位置，这个位置上没有关键字，因此没有冲突可以直接填入；

       H(30) = (30x3) MOD 7 = 6，地址是6，因此放到散列表的数组下表为6的位置，这个位置上没有关键字，因此没有冲突可以直接填入；

       H(11) = (11x3) MOD 7 = 5，地址是5，因此放到散列表的数组下表为5的位置，这个位置上没有关键字，因此没有冲突可以直接填入；

       H(18) = (18x3) MOD 7 = 5，地址是5，因此放到散列表的数组下表为5的位置，但这个位置上已经有关键字11，遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探测下一个位置6，6这个位置上已经存在关键字30则继续增加1，因此现在的新地址应为7，位置7上没有关键字，放入即可，到此冲突已经解决；

       H(9) = (9x3) MOD 7 = 6，地址是6，因此放到散列表的数组下表为6的位置，但这个位置上已经有关键字30，遇到了冲突，探测下一个位置7，7这个位置上已经存在关键字18则继续增加1，因此现在的新地址应为8，位置8上没有关键字，放入即可；   

       H(14) = (14x3) MOD 7 = 0，地址是0，因此放到散列表的数组下表为0的位置，但这个位置上已经有关键字7，遇到了冲突，探测下一个位置1，位置1上没有关键字，放入即可；   

       到这一步所有关键字均已填入，散列表已经构造完成，如下表所示。

（2）等概率情况下查找成功平均查找长度：

        这一问可以根据第一问的构造过程求解：

        key7 一次就填入了表中，因此查找次数为1，同理8， 30， 11查找次数均为1；

        key18 进行了三次探测操作，探测位置分别是5，6，7 ，因此查找次数为3；

        key9 也是三次；

        key14 进行了两次探测，因此查找次数为2。次数如下表所示：

        所以ASLsuccess= （1+2+1+1+1+3+3）/ 7 = 12/7。  

        接下来讨论不成功的情况，计算查找不成功的次数就直接找关键字到下一个地址关键字为空的距离即可，但根据散列函数地址为MOD7，因此初始只可能在0~6的位置。

        等概率情况下，0~6位置查找失败的查找次数为：

        地址0，到第一个关键字为空的地址2的距离为3，因此查找不成功的次数为3；

        地址1，到第一个关键字为空的地址2的距离为2，因此查找不成功的次数为2；

        地址2，到第一个关键字为空的地址2的距离为1，因此查找不成功的次数为1；

        地址3，到第二个关键字为空的地址4的距离为2，因此查找不成功的次数为2；

        地址4，到第二个关键字为空的地址4的距离为1，因此查找不成功的次数为1；

        地址5，到第三个关键字为空的地址9的距离为5，因此查找不成功的次数为5；

        地址6，到第三个关键字为空的地址9的距离为4，因此查找不成功的次数为4；

        注意地址7、8、9不用看。

        因此查找不成功的次数表如下表所示：

       所以ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7。