c - 如果散列是唯一的，但散列表中的散列％大小相同，会发生什么？

Question

最近在研究哈希表，了解其基础是

1. 例如创建一个数组

   哈希表 ht[4];

2. 对 key 进行哈希处理

   int hash = hash_key(key);

3. 获取索引

   int索引=哈希%4

4. 设置为哈希表

   ht[index] = insert_or_update(value)

而且我知道存在哈希冲突问题，如果key1和key2具有相同的哈希，它们会转到相同的ht[index]，所以单独的链接可以解决这个问题。

具有相同哈希值的 key 会进入同一个存储桶，这些 key 将存储在一个链表中。

我的问题是，如果哈希值不同，但模数相同会发生什么？

例如，

hash(key1): 3
hash(key2): 7
hash(key3): 11
hash(key4): 15

所以索引是3，这些具有不同散列和不同键的键进入同一个存储桶

我在谷歌上搜索了一些哈希表实现，似乎他们不处理这种情况。我是不是想多了？有什么问题吗？

例如，这些实现:

https://gist.github.com/tonious/1377667#file-hash-c-L139

http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html?highlight=%28CategoryAlgorithmNotes%29#CA-552d62422da2c22f8793edef9212910aa5fe0701_156

redis: https://github.com/antirez/redis/blob/unstable/src/dict.c#L488

nginx: https://github.com/nginx/nginx/blob/master/src/core/ngx_hash.c#L34

他们只是比较 key 是否相等

Answer 1

如果两个对象的键散列到同一个存储桶，那么这是因为它们具有相同的散列，还是因为它们具有不同的散列，但它们都映射(通过取模)到同一个存储桶，这并不重要。正如您所注意到的，由于这两种情况之一而发生的冲突通常通过将两个对象放入特定于存储桶的列表中来处理。

当我们在哈希表中查找对象时，我们正在查找共享相同键的对象。散列/取模运算仅用于告诉我们应该在哪个存储桶中查看该对象是否存在。一旦我们找到了正确的存储桶，我们仍然需要直接比较任何找到的对象(即特定于存储桶的列表中的对象)的键，以确保我们找到了匹配项。

因此，两个具有不同哈希值但映射到同一存储桶的对象的情况与具有相同哈希值的两个对象的工作原理相同:我们仅使用存储桶来查找候选匹配，并依靠 key 本身来确定真正的匹配。