C++ unordered_map及其基本結構和特性

unordered_map 包含的是有唯一鍵的鍵/值對元素。容器中的元素不是有序的。元素的位置由鍵的雜湊值確定，因而必須有一個適用於鍵型別的雜湊函數。如果用類物件作為鍵，需要為它定義一個實現了雜湊函數的函數物件。如果鍵是 STL 提供的型別，通過特例化 hash<T>，容器可以生成這種鍵對應的雜湊函數。

因為鍵可以不通過搜尋就存取無序 map 中的物件，所以可以很快檢索出無序 map 中的元素。疊代遍歷無序 map 中的元素序列的速度一般沒有有序 map 快，因此在某個應用中選擇何種容器取決於想如何存取容器中的元素。

unordered_map 容器中元素的組織方式和 map 有很大的不同，元素的內部組織方式取決於 C++ 實現。一般情況下，元素被儲存在雜湊表中，這個表中的條目被稱為格子，每個格子可以包含幾個元素。

一個給定的雜湊值會選擇特定的格子，因為雜湊值可能的個數幾乎可以肯定會大於格子的個數，兩個不同的雜湊值可能會對映到同一個格子上。因此，不同鍵會產生相同的雜湊值，會產生碰撞，而且兩個不同的雜湊值選擇相同的格子也會導致碰撞的產生。

下面的一些引數可以影響元素儲存的管理：

• 容器中格子的個數有一個預設值，但也可以定指定初始個數。
• 載入因子是每個格子平均儲存的元素的個數。這個值等於容器中元素個數除以格子的個數。

最大載入因子，預設是 1.0，但也可以修改。這是載入因子的上限。當容器達到最大載入因子時，容器會為格子分配更多的空間，這通常也會對容器中的元素重新進行雜湊。

任何時候都不要將單個格子中的最大元素個數和最大載入因子混淆。假設有一個容器，它有 8 個格子，前兩個格子中各有 3 個元素，剩下的格子都為空。那麼這時候的最大載入因子為 6/8，也就是 0.75，小於預設的最大載入因子 1.0，所以這沒有什麼問題。

圖 1 展示了 unordered_map 的基本結構圖。

---