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

Question

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

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

例如

1. 获取键、值
2. 对key使用Hash算法找到索引尝试放入value
3. 如果slot被占用，但是没有bucket(单项)，创建一个bucket，将当前item放入bucket中，然后将当前值放入bucket中。
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.

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