跳转至

無序關聯式容器

概述

自 C++11 標準起，四種基於 哈希 實現的無序關聯式容器正式納入了 C++ 的標準模板庫中，分別是：unordered_set，unordered_multiset，unordered_map，unordered_multimap。

編譯器不支持 C++11 的使用方法

在 C++11 之前，無序關聯式容器屬於 C++ 的 TR1 擴展。所以，如果編譯器不支持 C++11，在使用時需要在頭文件的名稱中加入 tr1/ 前綴，並且使用 std::tr1 命名空間。如 #include <unordered_map> 需要改成 #include <tr1/unordered_map>；std::unordered_map 需要改為 std::tr1::unordered_map（如果使用 using namespace std;，則為 tr1::unordered_map）。

它們與相應的關聯式容器在功能，函數等方面有諸多共同點，而最大的不同點則體現在普通的關聯式容器一般採用紅黑樹實現，內部元素按特定順序進行排序；而這幾種無序關聯式容器則採用哈希方式存儲元素，內部元素不以任何特定順序進行排序，所以訪問無序關聯式容器中的元素時，訪問順序也沒有任何保證。

採用哈希存儲的特點使得無序關聯式容器 在平均情況下 大多數操作（包括查找，插入，刪除）都能在常數時間複雜度內完成，相較於關聯式容器與容器大小成對數的時間複雜度更加優秀。

Warning

在最壞情況下，對無序關聯式容器進行插入、刪除、查找等操作的時間複雜度會 與容器大小成線性關係！這一情況往往在容器內出現大量哈希衝突時產生。

同時，由於無序關聯式容器的操作時通常存在較大的常數，其效率有時並不比普通的關聯式容器好太多。

因此應謹慎使用無序關聯式容器，儘量避免濫用（例如懶得離散化，直接將 unordered_map<int, int> 當作空間無限的普通數組使用）。

由於無序關聯式容器與相應的關聯式容器在用途和操作中有很多共同點，這裏不再介紹無序關聯式容器的各種操作，這些內容讀者可以參考 關聯式容器。

製造哈希衝突

上文中提到了，在最壞情況下，對無序關聯式容器進行一些操作的時間複雜度會與容器大小成線性關係。

在哈希函數確定的情況下，可以構造出數據使得容器內產生大量哈希衝突，導致複雜度達到上界。

在標準庫實現裏，每個元素的散列值是將值對一個質數取模得到的，更具體地説，是 這個列表 中的質數（g++ 6 及以前版本的編譯器，這個質數一般是 \(126271\)，g++ 7 及之後版本的編譯器，這個質數一般是 \(107897\)）。

因此可以通過向容器中插入這些模數的倍數來達到製造大量哈希衝突的目的。

自定義哈希函數

使用自定義哈希函數可以有效避免構造數據產生的大量哈希衝突。

要想使用自定義哈希函數，需要定義一個結構體，並在結構體中重載 () 運算符，像這樣：

1
2
3
struct my_hash {
  size_t operator()(int x) const { return x; }
};

當然，為了確保哈希函數不會被迅速破解（例如 Codeforces 中對使用無序關聯式容器的提交進行 hack），可以試着在哈希函數中加入一些隨機化函數（如時間）來增加破解的難度。

例如，在 這篇博客 中給出瞭如下哈希函數：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct my_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }

  // 針對 std::pair<int, int> 作為主鍵類型的哈希函數
  size_t operator()(pair<uint64_t, uint64_t> x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x.first + FIXED_RANDOM) ^
           (splitmix64(x.second + FIXED_RANDOM) >> 1);
  }
};

寫完自定義的哈希函數後，就可以通過 unordered_map<int, int, my_hash> my_map; 或者 unordered_map<pair<int, int>, int, my_hash> my_pair_map; 的定義方式將自定義的哈希函數傳入容器了。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用