? ? ? ?自 C++11 開始，STL 引入了基于 hash table 的?unordered_set、unordered_map 等容器，正如其名它們是無序容器。一定數量（據說有測試數據是10000000）元素時無序容器的性能要比對應的有序容器優。

一、容器數據結構

????????unordered_set、unordered_map 等容器的 Hash Table（哈希表/散列表）結構通常是：桶(bucket) + 線性表，bucket 一般用 vector 實現，線性表通常采用鏈表。當插入元素時通過哈希函數計算其哈希值，以哈希值作為 vector 的下標索引，取得元素要插入的鏈表頭，把元素插入進去。也就是說通過 鏈地址法(Separate Chaining)? 解決哈希沖突。

二、哈希函數

? ? ? ? 哈希函數是這些容器的核心，也是保證它們高性能的關鍵。C++11 為基本類型：int、float、double、char、string 提供了哈希函數。?但是要在這些容器中添加自定義類型的元素就必須提供特定的哈希函數。

無自定義類的哈希函數

無論是 clang++、還是 g++ 都無法正確如下代碼，原因就是：缺失計算 Person?哈希值的函數

#include <string>
#include <unordered_set>class Person {
public:Person(const std::string &name, int age) : _name(name), _age(age) {}private:std::string _name;int         _age;
};int main(int argc, char *argv[]) {std::unordered_set<Person> persons;
}

為自定義類添加哈希函數

查看?unordered_set 的聲明、?g++ 的 /usr/include/c++/9/bits/functional_hash.h 可知：

• unordered_set 的模板參數 Hash 默認設置為 std::hash<Key>，std::hash 是一個類模板；
• 通過特化 std::hash，支持了諸如 int、double 基本類型的哈希函數；
• 每個特化版本中重載了函數調用運算符

template<class Key,class Hash = std::hash<Key>,class KeyEqual = std::equal_to<Key>,class Allocator = std::allocator<Key>
> class unordered_set;/// Explicit specialization for int.
_Cxx_hashtable_define_trivial_hash(int)/// Explicit specialization for bool.
_Cxx_hashtable_define_trivial_hash(bool)/// Explicit specialization for char.
_Cxx_hashtable_define_trivial_hash(char)#define _Cxx_hashtable_define_trivial_hash(_Tp) 	\template<>						\struct hash<_Tp> : public __hash_base<size_t, _Tp>  \{                                                   \size_t                                            \operator()(_Tp __val) const noexcept              \{ return static_cast<size_t>(__val); }            \};

綜述為 Person 類定義函數對象類實現哈希函數功能

#include <string>
#include <unordered_set>struct Person {Person(const std::string &name, int age) : _name(name), _age(age) {}std::string _name;int         _age;
};struct PersonHash
{size_t operator()(const Person &person) const noexcept{return static_cast<size_t>(person._age + person._name.length());}
};int main(int argc, char *argv[]) {std::unordered_set<Person, PersonHash> persons;persons.insert({"yaoyuan", 30});}

為自定義類添加哈希函數

未完...