如果散列值是唯一的，但哈希表中的散列％大小相同，会发生什么情况？

Question

最近我学哈希表，并理解的基础，是

1. 创建一个数组，例如

   hashtable ht[4];

2. 哈希关键

   int hash = hash_key(key);

3. 获得索引

   int index = hash % 4

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

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

他们只是比较，如果键等于

Answer 1

如果两个对象的关键字散列到同一桶，这并不重要，如果是因为它们具有相同的哈希值，或因为他们有不同的散列但他们都地图（通过模数）到同一个桶。如您所注意到的，由于这些情况而发生的碰撞通常通过将两个对象放置在特定于桶的列表中来处理。

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

因此，与不同的散列两个对象的情况，但映射到同一个桶适用于同样的原因，用相同的哈希两个对象的工作原理：我们只用水桶找到候选人比赛，并依靠自己来确定一个真正的匹配。