2

我正在阅读 C 语言中的数据结构、算法和软件原理，以试图了解数据结构的一些内部结构，有两件事让我非常困扰：

(1) 哈希表如何处理决定桶中的哪个项目是你正在查找的项目，如果它们都具有相同的哈希？

例如

  1. 获取键、值
  2. 在键上使用哈希算法找到索引以尝试将值放入
  3. 如果槽被占用，但没有桶（单个条目），则创建一个桶并将当前项目放入桶中，然后将当前值放入其中。
  4. 现在我有一个带有一堆值的桶和一个“失物招领问题”，您无法分辨哪个值属于哪个键，因为所有键都映射到同一个哈希，并且桶中的项目没有要搜索的键桶的关键。

如果存储桶保存每个条目的键和值，这将起作用，但我很困惑，因为我找不到确认哈希表保存键及其条目的值的站点。

(2) 哈希表如何判断索引处的值是否是键的正确值，或者探测是否发现冲突并将其放在其他地方。

例如。

  1. 获取键、值
  2. 哈希键查找索引（0）
  3. 获取索引，使用简单的探测算法执行线性搜索，直到找到插槽（插槽 1 为空）。
  4. 现在我搜索我的键并找到索引 0。哈希如何知道索引 0 不是该键的正确项，但它已被探测到插槽 1？

同样，如果表保存了条目的键和值，这对我来说是有意义的，但我不确定哈希是否将键与条目的值一起保存，或者是否有另一种方法来确保哈希索引处的项目或存储桶索引是正确的项目，或者如果我误解了它。

为了澄清这个问题：哈希表是否保存键和值来消除桶和探测序列的歧义，或者他们是否使用其他东西来避免哈希的歧义？

很抱歉这个粗略的问题，但我不得不问。

提前谢谢。

4

1 回答 1

2

哈希表保存条目。条目由键和值组成。

如果哈希表都具有相同的哈希值，那么哈希表如何决定存储桶中的哪个项目是您要查找的项目？

因为查询是通过传递密钥来完成的。

散列的目的是减少查找索引的时间。他们的密钥被散列以找到正确的存储桶。然后，当项目从总 N 减少到非常小的 n 时，您甚至可以执行线性搜索以从具有相同散列的所有键中找到正确的项目。

哈希表如何判断索引处的值是否是键的正确值，或者探测是否发现冲突并将其放在其他地方。

同样，这是因为哈希表会保存条目而不仅仅是值。如果在发生冲突的情况下，哈希表发现在这个桶中找到的键不是被查询的键，则哈希表知道冲突发生得更早，并且键可能在下一个桶中。请注意，在这种情况下，存储桶存储单个条目，这与第一个答案的情况不同，其中存储桶可能存储 LinkedList 或条目树。

于 2016-07-16T00:01:25.657 回答