如何標準:: unordered_map從水桶

返回正確的值我有一個std::unordered_map<std::string, int> map;如何標準:: unordered_map從水桶

然後插入噸的元素融入到這一點，但字符串鍵都是唯一的。

是否可能出現以下情況，以及如何處理？

map[x] = 5; 
map[y] = 3;

讓我們假設x和y是不同的字符串，但它們產生的相同的散列，所以5和3被放置在同一個桶中。

當我們嘗試使用map[x]檢索值時，地圖如何返回正確的值5？哈希x將給桶與兩個元素5,3，但我不知道它是如何得到正確的值，沒有密鑰本身進行比較。

我錯過了什麼？

來源

2013-10-24 Barış Uşaklı

你曾經寫過一個哈希表實現嗎？ – WhozCraig

@WhozCraig不，我沒有。 –

當然，地圖必須將密鑰與值一起存儲，而不僅僅是散列值。如果只是因爲'map.begin（） - > first'必須返回密鑰。所以一旦進入合適的存儲桶，它就會在那裏進行常規搜索。 –

的unordered_map完整的聲明看起來像這樣：

template < 
    class Key, 
    class T, 
    class Hash  = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator<std::pair<Key const, T>> 
> class unordered_map;

觀察，它需要兩個哈希函數和密鑰類型的相等比較。

當使用特定鍵搜索元素時，容器將首先使用散列函數找到正確的桶，然後遍歷該桶中的元素，並使用相等比較器比較每個元素的鍵。

來源

2013-10-24 02:18:26

桶就是這樣一個桶。 unordered_map實際上是一個模板，其中包含一個鍵和值類型，以及一個用於檢查鍵是否相等的函數（默認爲std::equal_to<KeyType>）它使用相等比較來查找存儲桶中與您值相匹配的元素尋找。

散列表通常會退化爲線性或日誌時間，如果您完全是邪惡的併爲它們提供大量碰撞的鍵，實際上它們通常接近於O（1）。

來源

2013-10-24 02:18:38 Charlie

我想你會發現，如果你仔細想想，你的第一個陳述並不是真的。水桶不是真的*水桶。這只是一個比喻。 –

如何標準:: unordered_map從水桶

回答

相關問題