线性探测再散列查找成功和不成功的相关问题

《线性探测再散列查找成功和不成功的相关问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线性探测再散列法查找成功和查找不成功的平均查找长度Question1:将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(keyx3)MOD7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。(1)请画出所构造的散列表。(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。Ans：(1).首先明确一个概念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等于关键字总数/哈希表的长度。根据题意，我们可以确定哈希表的长度为L=7/0.7=10；因此此题需要构建的哈希表是

2、下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。H(Key)=(keyx3)MOD7,例如key=7时，H(7)=(7x3）%7=21%7=0，其他关键字同理。Key78301118914H(Key)0365560(表1)采用线性探测再散列法处理冲突，所构造的散列表为：地址0123456789关键字71481130189(表2)下面对散列表的构造方式加以说明，注意表1中的关键字7和14，30和9，11和18，这三组关键子的H(Key)值相同，这在构建散列表时就会产生冲突，因为他们的地址相同，所以要通过一定的冲突处理方法来解决这个问题。依题，采用线性探测再散列法处理冲突

3、。下面详细介绍如何构建散列表：第一个key7，它的地址是0，因此放到散列表的数组下表为0的位置，这个位置上没有关键字，因此没有冲突可以直接填入；第二个key8，它的地址是3，因此放到散列表的数组下表为3的位置，这个位置上没有关键字，因此没有冲突可以直接填入；第三个key30，它的地址是6，因此放到散列表的数组下表为6的位置，这个位置上没有关键字，因此没有冲突可以直接填入；第四个key11，它的地址是5，因此放到散列表的数组下表为5的位置，这个位置上没有关键字，因此没有冲突可以直接填入；第五个key18，它的地址是5，因此放到散列表的数组下表为5的位置，但这个位置上已经有关键字11，

4、遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探测下一个位置6,6这个位置上已经存在关键字30则继续增加步长1，因此现在的新地址应为7，位置7上没有关键字，放入即可，到此冲突已经解决；第六个key9，它的地址是6，因此放到散列表的数组下表为6的位置，但这个位置上已经有关键字30，遇到了冲突，探测下一个位置7,7这个位置上已经存在关键字18则继续增加步长1，因此现在的新地址应为8，位置8上没有关键字，放入即可；第七个key14，它的地址是0，因此放到散列表的数组下表为0的位置，但这个位置上已经有关键字7，遇到了冲突，探测下一个位置1,位置1上没有关键字，放入即可；到这一步所

5、有关键字均已填入，散列表已经构造完成，如表2所示。（2）等概率情况下查找成功平均查找长度：这一问可以根据第一问的构造过程求解：key7一次就填入了表中，因此查找次数为1，同理8，30，11查找次数均为1；key18进行了3次放入操作，探测位置分别是5，6，7，因此查找次数为3；key9也是3次；key14进行了两次探测，因此查找次数为2。次数表如表3所示Key78301118914Count1111332(表3)所以ASLsuccess=（1+1+1+1+3+3+2）/7=12/7。等概率情况下查找不成功的平均查找长度：接下来讨论不成功的情况,看表2，计算查找不成功的次数就直接找关

6、键字到第一个地址上关键字为空的距离即可，但根据哈希函数地址为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，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循

7、环回去)的距离为5，因此查找不成功的次数为5.地址6，到第一个关键为空的地址2(注意不是地址9，因为初始只可能在0~6之间，因此循环回去)的距离为4，因此查找不成功的次数为4.因此查找不成功的次数表如下表所示Key78301118914Count3212154(表4)所以ASLunsuccess=（3+2+1+2+1+5+4）/7=18/7。