如果散列是唯一的，但哈希%大小在哈希表中是相同的，则会发生什么？
最近我正在学习哈希表，并且理解的基础是
- 创建一个数组，例如
hashtable ht[4]; - 散列密钥
int hash = hash_key(key); - 得到索引
int index = hash % 4 - 设置为hashtable
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，这些具有不同哈希和不同键的键会转到同一个桶中。
我搜索谷歌的一些哈希表实现，似乎他们不处理这种情况。我是不是想得太多了？有什么不对劲吗？
例如，这些实现：
https://gist.github.com/tonious/1377667#file-hash-c-L139
156
redis：https://github.com/antirez/redis/blob/unstable/src/dict.c#L488
nginx：hash.c#L34
他们只是比较一下键是否相等
回答 1
Stack Overflow用户
发布于 2017-09-14 03:44:03
如果两个对象的键散列到同一个桶，那么是否因为它们具有相同的散列，或者因为它们有不同的散列，但它们都将(通过模块)映射到同一个桶，这并不重要。正如您注意到的，由于这两种情况中的任何一种情况而发生的冲突通常通过将两个对象放置在特定于桶的列表中来处理。
当我们在哈希表中寻找一个对象时，我们正在寻找一个共享相同密钥的对象。散列/模操作只是用来告诉我们应该在哪个桶中查看对象是否存在。一旦找到了正确的桶，我们仍然需要直接比较找到的任何对象(即特定于桶的列表中的对象)的键，以确保找到了匹配的对象。
因此，两个具有不同哈希但映射到同一个桶的对象的情况工作的原因是相同的，两个具有相同哈希的对象可以工作:我们只使用桶查找候选匹配，并依靠键本身来确定真正的匹配。
https://stackoverflow.com/questions/46209949
复制相似问题
腾讯云开发者
