關於C++ unordered_map和散列衝突的困惑

我讀過unordered_map在桶中放置相同散列的元素，這就是它處理散列衝突的方式。然而，當我檢查了insert function，它說：關於C++ unordered_map和散列衝突的困惑

每個元素的插入只有當它的關鍵是不等同於其他任何元素的鍵已在容器

這是否意味着我不能插入具有相同散列的元素？..我應該能夠插入帶有新散列的元素，因爲unordered_map結構可以處理衝突，對嗎？..我想我可能會錯過某些東西。

2015-04-22 Nu Nunu

2個不同的密鑰可以導致相同的散列，甚至2個不同的散列可以對應於同一個桶 – BoBTFish

肯定是可能對於那些語句要一致，一旦你意識到散列不一定是關鍵。

一組不同的密鑰可能會生成相同的哈希值，因此要存儲在同一個存儲桶中，但仍允許限制重複密鑰不被允許。

例如，假設您有一個使用名字作爲關鍵字的friends集合。散列函數是（一個相當簡單的）「使用名稱的第一個字母。

所以，雖然偉業，安德魯·亞當，比爾，本尼和Chloe六種不同鍵，他們只佔三種不同哈希值：

  A     B   C (buckets) 
    ______/|\_____  /\   | 
/  |  \  / \   | 
Albert Andrew Adam Bill Benny Chloe (keys)

2015-04-22 08:05:21 paxdiablo

值得一提的是2個不同的散列可以在同一個桶中結束，比那裏給出。將（幾乎肯定）比桶更可能有更多的散列。 – BoBTFish

@BoBTFish，這取決於你如何定義h灰，我想。如果你得到的32位「散列」進一步縮減爲8位桶ID，我傾向於不把32位值作爲散列值，而是中間值。真正的哈希將是桶ID。 – paxdiablo

對我來說，它是'hasher'的'result_type'。「bucket id」肯定與'bucket_count'或'max_bucket_count'返回的類型'size_type'相同。 – BoBTFish

回答