0

在此处输入图像描述

任何人都知道如何开始这个问题？我的意思是，我了解哈希的作用，但我不知道这个问题在说什么。

关于如何解决这个问题的任何想法？

鉴于：

  • 哈希函数：h(x) = | 2x + 5 | 模式 M
  • 容量为 N 的桶数组
  • 一组带有键的对象：12、44、13、88、23、94、11、39、20、16、5（从左到右输入）

4.a * [5 pts]***** 编写哈希表，其中 M=N=11 并且使用单独的链接处理冲突。

4.b * [5 pts]***** 编写 M=N=11 的哈希表，并使用线性探测处理冲突。

4.c * [5 pts]***** 如果 M=11，你能找到一个 N 值，它不会产生散列这些键的冲突吗？

4

3 回答 3

1

使用等式 h(x) 找到每个键的哈希值。这是数组中存储值的位置。因为，这显然是家庭作业，我不会解释线性探测或分离链接或 4c。

M 是您将值放入的数组的大小。

N 是您要散列的对象数。

于 2012-12-07T23:35:55.193 回答
1
  • 你有一个函数，它给定一个数字 (x) 确定应该在表中的位置。
  • 该表具有给定的大小 N。对于本题的 a 和 b 部分，N 为 11。
  • 对于问题 a、b 和 c，M 为 11。M 只是一个插入给定公式的值h(x) = (2x + 5) mod M
  • 所以给定数字 12，h(12) = (2 * 12 + 5) mod 11=> 7。所以第一个结果进入存储桶 7。
  • 然后你依次处理其余的数字，计算出每个数字的 h(x) 是什么。
  • 但是，当您遇到冲突时（即数字应该进入的桶已经被之前的数字填充的场景），您需要为其选择不同的桶。您选择哪个反冲将取决于您的溢出策略。
  • 有问题 A 你的溢出策略是单独的链接
  • 在问题 B 中，您的溢出策略是线性探测
  • 如果您不熟悉这些方法，请观看：
  • 如果 C 被视为已读，我认为这意味着从列表的开头获取数字，直到您遇到第一次碰撞；但是，您的存储桶中已有的许多数字是 N 的值。
  • 但是，我认为 CI 认为问题是印刷错误。我认为它希望您为 M 找到一个值，该值将允许将给定的数字列表全部分配给一个唯一的存储桶（即没有冲突/没有溢出策略）。
于 2012-12-07T23:51:09.557 回答
0

首先计算每个键的哈希值。

于 2012-12-07T23:35:43.507 回答