深入了解unorder_map

一、概述

unorder_map 是 C++ STL 中的一種關聯容器，它允許存儲一組具有映射關係的數據。這些映射關係是由鍵和值組成的，每個鍵只能對應一個值。unorder_map 內部使用哈希表來實現數據的快速查找，因此可以在 O(1) 的時間複雜度內完成元素的查找、添加和刪除操作。

二、基本使用

要使用 unorder_map，通常需要包含頭文件 ，在代碼中定義一個對象，對象的類型應該是 unorder_map 的模板參數，該參數有兩個類型 T1 和 T2，代表鍵和值的類型，可以使用下面的代碼來定義一個 unorder_map 對象：

#include 
#include 

int main()
{
    std::unordered_map mymap;
    ...
}

在上面的代碼中，我們定義了一個字元串類型的鍵和一個整數類型的值，因為 unorder_map 內部使用哈希表，因此鍵可以是任何可以哈希的類型。插入元素可以使用以下語句：

mymap["hello"] = 1;
mymap["world"] = 2;
mymap.insert(std::make_pair("good", 3));

可以使用下面的方法來查找元素：

it = mymap.find("hello");
if (it != mymap.end())
    std::cout << "Value: " <second << std::endl;

其中，it 是一個迭代器，可以通過 it->first 和 it->second 來訪問鍵和值。

刪除元素可以使用以下語句：

mymap.erase("hello");

三、幾個需要注意的細節問題

雖然 unorder_map 實現了 O(1) 時間複雜度的元素查找、添加和刪除操作，但在使用時還需要注意一些細節問題，否則可能會出現一些難以察覺的問題。

1.哈希函數衝突問題

在哈希表內部，數據被分成一組桶，每個桶中存放了一些元素。哈希函數用於將元素映射到不同的桶內，但可能會出現多個元素映射到同一個桶的情況，這就叫做哈希衝突。當哈希表中的元素數量較少時，哈希衝突的影響並不顯著，但當元素數量增加時，哈希衝突的影響會越來越大，影響整個哈希表的性能。

為了解決哈希衝突問題，unorder_map 通常會使用鏈表來存儲每個桶內的元素，每個桶內的元素都按照添加的順序存儲，因此在查找元素時需要遍歷整個鏈表。鏈表太長會導致查找的複雜度從 O(1) 增加到O(n)，因此需要使用哈希函數來減少哈希衝突的可能，從而降低整個哈希表的查找複雜度。

2.對於自定義類型的元素，需要重載哈希函數和比較函數

當 unorder_map 存儲自定義類型的元素時，需要實現哈希函數和比較函數，以便 unorder_map 能夠正確地處理這些類型的元素。

下面是一個自定義類型的哈希函數和比較函數的示例：

struct MyStruct
{
    int x;
    int y;
};

struct MyStructHash
{
    size_t operator()(const MyStruct& mystruct) const
    {
        return std::hash()(mystruct.x) ^ std::hash()(mystruct.y);
    }
};

struct MyStructEqual
{
    bool operator()(const MyStruct& lhs, const MyStruct& rhs) const
    {
        return lhs.x == rhs.x && lhs.y == rhs.y;
    }
};

std::unordered_map mymap;

在上面的代碼中，MyStructHash 是哈希函數的實現，MyStructEqual 是比較函數的實現。mymap 對象的第三個和第四個參數分別是哈希函數和比較函數。注意，這些函數需要滿足特定的簽名，否則代碼無法編譯通過。

四、總結

unorder_map 是一個非常有用且性能出色的 C++ STL 容器，它允許存儲一組具有映射關係的數據，並在 O(1) 的時間複雜度內完成元素的查找、添加和刪除操作。使用 unorder_map 時，我們需要注意哈希衝突問題和自定義類型的哈希函數和比較函數的實現。