如果散列值是唯一的，但哈希表中的散列％大小相同，會發生什麼情況？

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

如果兩個對象的關鍵字散列到同一桶，這並不重要，如果是因爲它們具有相同的哈希值，或因爲他們有不同的散列但他們都地圖（通過模數）到同一個桶。如您所注意到的，由於這些情況而發生的碰撞通常通過將兩個對象放置在特定於桶的列表中來處理。

當我們尋找一個哈希表的對象，我們正在尋找共享同一個密鑰的對象。散列/模運算僅用於告訴我們在哪個桶中，我們應該看看以查看對象是否存在。一旦我們找到合適的桶，我們仍然需要比較任何找到的對象的鍵（即，特定於桶的列表中的對象）直接確保我們找到了匹配項。

因此，與不同的散列兩個對象的情況，但映射到同一個桶適用於同樣的原因，用相同的哈希兩個對象的工作原理：我們只用水桶找到候選人比賽，並依靠自己來確定一個真正的匹配。