《线性探测再散列查找成功和不成功的相关问题》由会员分享，可在线阅读，更多相关《线性探测再散列查找成功和不成功的相关问题（3页珍藏版）》请在金锄头文库上搜索。
1、线性探测再散列法查找成功和查找不成功的平均查找长度Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。 散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装 填(载)因子为0.7。(1) 请画出所构造的散列表。(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。Ans： (1).首先明确一个概念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等 于 关键字总数 / 哈希表的长度。 根据题意，我们可以确定哈希表的长度为 L = 7/0.7 =
2、 10 ； 因此此题需要构建的哈希表是下标为09 的一维数组。根据散列函数可以得到如下散列函数 值表。H(Key) = (keyx3) MOD 7, 例如 key=7 时， H(7) = (7x3)%7 = 21%7=0，其他关键字同理。 Key78301118914H(Key)0365560(表 1) 采用线性探测再散列法处理冲突，所构造的散列表为： 地址 012 34 5 6 789关键字 714 8 11 30 189(表 2)下面对散列表的构造方式加以说明，注意表 1 中的关键字 7 和 14，30和 9， 11和 18，这 三组关键子的H(Key)值相同，这在构建散列表时就会产生冲突
3、，因为他们的地址相同，所 以要通过一定的冲突处理方法来解决这个问题。依题，采用线性探测再散列法处理冲突。下 面详细介绍如何构建散列表：第一个key 7,它的地址是0因此放到散列表的数组下表为0的位置，这个位置上没有关 键字，因此没有冲突可以直接填入；第二个 key 8，它的地址是 3，因此放到散列表的数组下表为 3 的位置，这个位置上没有关 键字，因此没有冲突可以直接填入；第三个 key 30，它的地址是6，因此放到散列表的数组下表为6 的位置，这个位置上没有关 键字，因此没有冲突可以直接填入；第四个 key 11，它的地址是 5，因此放到散列表的数组下表为5 的位置，这个位置上没有关 键字，
4、因此没有冲突可以直接填入；第五个 key 18，它的地址是5，因此放到散列表的数组下表为5 的位置，但这个位置上已经 有关键字 11，遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探测下一个 位置 6, 6 这个位置上已经存在关键字 30则继续增加步长 1，因此现在的新地址应为7，位置 7 上没有关键字，放入即可，到此冲突已经解决；第六个 key 9，它的地址是 6，因此放到散列表的数组下表为 6 的位置，但这个位置上已经 有关键字 30，遇到了冲突，探测下一个位置7, 7 这个位置上已经存在关键字18 则继续增加 步长 1，因此现在的新地址应为 8，位置8 上没有关键字，放入即可；
5、第七个 key 14，它的地址是0，因此放到散列表的数组下表为0 的位置，但这个位置上已经 有关键字 7，遇到了冲突，探测下一个位置 1, 位置1 上没有关键字，放入即可； 到这一步所有关键字均已填入，散列表已经构造完成，如表 2 所示。（2）等概率情况下查找成功平均查找长度： 这一问可以根据第一问的构造过程求解： key7 一次就填入了表中，因此查找次数为 1，同理 8， 30， 11 查找次数均为 1； key18 进 行了 3次放入操作，探测位置分别是5, 6, 7，因此查找次数为3； key9也是3次；keyl4 进行了两次探测，因此查找次数为 2。次数表如表 3 所示Key 7830
6、lll89l4Count llll332（表3）所以 ASLsuccess= （l+l+l+l+3+3+2）/ 7 = l2/7。 等概率情况下查找不成功的平均查找长度： 接下来讨论不成功的情况, 看表 2，计算查找不成功的次数就直接找关键字到第一个地址上 关键字为空的距离即可，但根据哈希函数地址为M0D7,因此初始只可能在06的位置。 等概率情况下，查找 06 位置查找失败的查找次数为：看地址0，到第一个关键字为空的地址 2的距离为3，因此查找不成功的次数为 3.地址1， 到第一个关键为空的地址2的距离为2，因此查找不成功的次数为 2.地址2， 到第一个关键为空的地址2的距离为1，因此查找不
7、成功的次数为 1. 地址3，到第一个关键为空的地址 4的距离为2，因此查找不成功的次数为 2. 地址4，到第一个关键为空的地址 4的距离为1，因此查找不成功的次数为 1.地址 5，到第一个关键为空的地址 2（注意不是地址 9，因为初始只可能在06 之间，因此循 环回去）的距离为 5，因此查找不成功的次数为 5.地址 6，到第一个关键为空的地址 2（注意不是地址 9，因为初始只可能在06 之间，因此循 环回去）的距离为 4，因此查找不成功的次数为 4.因此查找不成功的次数表如下表所示Key 7 8 30 11 18 9 14Count 3 2 1 2 1 5 4（表 4）所以 ASLunsuccess= （3+2+1+2+1+5+4）/ 7 = 18/7 。
