二次探测法

设哈希表长为11,哈希函数为Hash (key)=key%11。存在关键码{43,7,29,22,16,92,44,8,19},采用二次探测法处理冲突,建立的hash表为( )
二次探测法:采用开放定址法处理冲突中的二次探测再散列(也即是题目中的二元探测法),则哈希函数变为Hash(key) = (Hash(key) + d) % 11,其中d = 1^2, -1^2, 2^2, -2^2, 3^2,……,则开始计算。

对于43,代入公式为Hash(43) = 43 % 11 = 10, 则地址为10;

对于7,代入公式为Hash(7) = 7 % 11 = 7,则地址为7;

对于29,代入公式为Hash(29) = 29 % 11 = 7, 与7冲突,则采用二次探测进行消除冲突, 继续(7 + 1) % 11 = 8,没有冲突,则地址为8;

对于22,代入公式Hash(22) = 22 % 11 = 0, 则地址为0;

对于16,代入公式Hash(16) = 16 % 11 = 5, 则地址为5;

对于92,代入公式Hash(92) = 92 % 11 = 4,则地址为4;

对于44,代入公式Hash(44) = 44 % 11 = 0, 与22的地址冲突,则继续(0 + 1) % 11 = 1,没有冲突,则地址为1;

对于8, 代入公式Hash(8) = 8 % 11 = 8, 与29有冲突,则继续(8 + 1) % 11 = 9, 没有冲突,则地址为9;

对于19,代入公式Hash(19) = 19 % 11 = 8. 与 29有冲突,则继续(8 + 1) * 11 = 9, 与8有冲突,继续(8 - 1) % 11 = 7, 与7有冲突,则继续(8 + 4) % 11 = 1, 与44有冲突,则继续(8 - 4) % 11 = 4, 与92有冲突,则继续(8 + 9) % 11 = 6, 没有冲突,则地址为6.

所以最后得到的Hash表为下图所示:

0 1 2 3 4 5 6 7 8 9 10
22 44     92 16 19 7 29 8 43

 

 

原文地址:https://www.cnblogs.com/terryzh/p/15106588.html