algorithm - 哈希表如何解决桶歧义和探测问题？

Question

我正在阅读《C 语言的数据结构和算法与软件原理》，试图了解数据结构的一些内部原理，有两件事确实困扰着我:

(1) 如果桶中的所有项目都具有相同的哈希值，哈希表如何处理确定您要查找的项目？

例如

1. 获取键、值
2. 对键使用哈希算法来查找索引以尝试将值放入
3. 如果槽已被占用，但没有桶(单项)，则创建一个桶并将当前项放入桶中，然后将当前值放入其中。
4. 现在我有一个包含一堆值的存储桶和一个“丢失和找到的问题”，您无法分辨哪个值属于哪个键，因为所有键都映射到相同的哈希值并且存储桶中的项目没有key 按键搜索存储桶。

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

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

例如。

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

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

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

很抱歉提出了这个粗略的问题，但我只是不得不问。

提前致谢。

Answer 1

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

How do hash tables deal with deciding which item in the bucket is the item you are looking up if they all have the same hash?

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

散列的目的是减少查找索引的时间。它们的 key 经过哈希处理以找到正确的存储桶。然后，当项目从总数 N 减少到非常小的 n 时，您甚至可以执行线性搜索以从具有相同哈希的所有键中找到正确的项目。

How do hash tables tell if the value at an index is the correct value for the key, or if probing found a collision and put it elsewhere.

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