爲什麼地圖比unordered_map快得多？

我實現了一個搜索緩存結果，它包含State類型的鍵（有7個短整數的類）和Socre類型的值（一個3雙的類）。使用unordered_map的速度至少比map快20倍。爲什麼？爲什麼地圖比unordered_map快得多？

編輯：收藏！我的哈希函數是

namespace std { 
    size_t hash<State>::operator()(State const& s) const { 
     size_t retval = hash<short>()(s.s[0]); 
     for (int i = 1; i < R; i += 2) { // 1 3 5 
      int x = (static_cast<int>(s.s[i + 1]) << 16) 
       + (static_cast<int>(s.s[i])); 
      hash_combine(retval, x); 
     } 
    } 
}

我忘了return retval，所以它都是碰撞！我希望unordered_map有一個可以報告平均碰撞次數的hash_function_quality（）函數。

來源

2011-01-31 Neil G

什麼是您的訪問模式？ – 2011-01-31 01:09:05

什麼平臺/編譯器？ – ThomasMcLeod 2011-01-31 01:10:30

英特爾i5，海灣合作委員會，60萬插入和查找 – 2011-01-31 01:12:22

unordered_map的速度與您的散列函數的速度成正比。這從來都不是直接的關係。典型的例子，如果你用最簡單的散列函數：

std::size_t myHash(MyObjectType _object){ return 1; }

那麼你就會有最終是表現得像一個列表，而不是一個散列容器的集合。所有的物品都會映射到一個桶，你必須穿過整個桶，直到你到達你想要的物品（可能需要O（N）時間。）

你需要做的是看有兩件事：

你使用的是什麼散列函數？這會花費大量的時間來處理嗎？
它產生多少次碰撞？也就是說，有多少獨特的元素被映射到相同的散列值？

這些都是他們自己能夠而且會殺死的表現。

來源

2011-01-31 01:25:27 wheaties

std::unordered_map由於散列函數對少數元素通常很慢。它需要固定的時間，但可能需要很長時間。

std::map另一方面比std::unordered_map簡單。訪問元素所花費的時間取決於元素的數量，但隨着元素數量的增長而越來越少。與std::unordered_map相比，std :: map的大哦因子c通常也很小。

一般而言，除非您有特定的理由使用std::unordered_map，否則更喜歡使用std::map而不是std::unordered_map。如果你沒有大量元素，這尤其適用。

來源

2011-01-31 01:16:36 wilhelmtell

unordered_map在引擎蓋下使用了一個哈希表，所以哈希性能差的原因最明顯的原因是因爲碰撞太多。您可以考慮使用不同的非默認哈希函數，以便爲您的鍵類型提供更好的結果。

來源

2011-01-31 01:24:55

對於

我希望unordered_map有 hash_function_quality（）函數報告的衝突的平均數。

我覺得下面的函數可能會有所幫助。

unordered_map::load_factor 
    float load_factor() const; 
The member function returns the average number of elements per bucket.

降低load_factor，更好的是散列函數。

來源

2011-01-31 03:38:26 Arun

爲什麼地圖比unordered_map快得多？

回答

相關問題