如果散列是唯一的但散列 % 大小在散列 table 中相同，会发生什么情况？

What happens if hash is unique but hash % size is same in hash table?

最近在研究散列table，了解基础是

  1. 创建数组，例如

    hashtable ht[4];

  2. 散列密钥

    int hash = hash_key(key);

  3. 获取索引

    int index = hash % 4

  4. 设置为散列table

    ht[index] = insert_or_update(value)

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

具有相同散列的键进入同一个桶，这些键将存储在链表中。

我的问题是，如果哈希值不同但模数相同会怎样？

例如，

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

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

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

例如，这些实现：

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

他们只是比较键是否相等

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

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

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