开地址法双散列函数处理碰撞

Question

采用开地址法中的双散列函数策略处理碰撞
h1（key）=（3key）%11
h2（key）=（7key）%10+1
试在0-10的散列地址空间中对关键字序列（22 41 53 46 30 13 01 67）构造哈希表（写出详细计算过程）

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

首先，创建一个11个大小的散列表，并将所有的散列地址初始化为-1。关键字序列为（22 41 53 46 30 13 01 67）。

1. 对每个关键字进行散列，使用双散列函数策略处理碰撞。

   • 对关键字22使用h1(key)：h1(22) = (3 * 22) % 11 = 8。散列地址为8，将22放入散列地址为8的位置。
   • 对关键字41使用h1(key)：h1(41) = (3 * 41) % 11 = 10。散列地址为10，将41放入散列地址为10的位置。
   • 对关键字53使用h1(key)：h1(53) = (3 * 53) % 11 = 10。由于散列地址为10的位置已经被占用，需要使用第二个散列函数。
     h2(53) = (7 * 53) % 10 + 1 = 9。散列地址为9，将53放入散列地址为9的位置。
   • 对关键字46使用h1(key)：h1(46) = (3 * 46) % 11 = 5。散列地址为5，将46放入散列地址为5的位置。
   • 对关键字30使用h1(key)：h1(30) = (3 * 30) % 11 = 8。由于散列地址为8的位置已经被占用，需要使用第二个散列函数。
     h2(30) = (7 * 30) % 10 + 1 = 4。散列地址为4，将30放入散列地址为4的位置。
   • 对关键字13使用h1(key)：h1(13) = (3 * 13) % 11 = 7。散列地址为7，将13放入散列地址为7的位置。
   • 对关键字01使用h1(key)：h1(01) = (3 * 01) % 11 = 3。散列地址为3，将01放入散列地址为3的位置。
   • 对关键字67使用h1(key)：h1(67) = (3 * 67) % 11 = 4。由于散列地址为4的位置已经被占用，需要使用第二个散列函数。
     h2(67) = (7 * 67) % 10 + 1 = 7。散列地址为7，将67放入散列地址为7的位置。

2. 散列表的最终结果如下：
   索引： 0 1 2 3 4 5 6 7 8 9 10
   关键字： -1 -1 -1 01 67 46 -1 13 22 53 41

因此，使用双散列函数策略处理碰撞后的散列表是（-1 -1 -1 01 67 46 -1 13 22 53 41）。
注意：这是一个简单的示例，实际操作中可能会使用更复杂的散列函数和冲突解决策略。