线性探测再散列方法:查找成功平均查找长度计算
线性探测再散列方法是一种解决冲突的方法,当发生冲突时,将关键字通过线性探测再散列的方式,依次往后查找空槽,直到找到一个空槽或者达到最大探测次数。
根据题目给出的关键字序列,我们可以通过线性探测再散列方法构建哈希表。首先,根据 H(K)=K%11,计算每个关键字的哈希地址。
关键字序列:(21, 40, 52, 45, 29, 12, 02, 66) 哈希地址序列:(10, 7, 8, 1, 7, 1, 2, 0)
然后,我们可以使用线性探测再散列方法处理冲突。当发生冲突时,依次往后查找空槽,直到找到一个空槽或者达到最大探测次数。假设最大探测次数为 M=10,即最多探测 10 个空槽。
关键字序列:(21, 40, 52, 45, 29, 12, 02, 66) 哈希地址序列:(10, 7, 8, 1, 7, 1, 2, 0)
探测过程: 21 -> 10 (0 次探测) 40 -> 7 (0 次探测) 52 -> 8 (0 次探测) 45 -> 1 (0 次探测) 29 -> 7 (1 次探测) 12 -> 1 (1 次探测) 02 -> 2 (0 次探测) 66 -> 0 (0 次探测)
最终的哈希地址序列:(10, 7, 8, 1, 9, 1, 2, 0)
计算平均查找长度 (ASL): ASL = (0 + 0 + 0 + 0 + 1 + 1 + 0 + 0) / 8 = 0.375
所以,等概率下查找成功的平均查找长度为 0.375。
原文地址: https://www.cveoy.top/t/topic/qf2R 著作权归作者所有。请勿转载和采集!