hash_map ≈ unordered_map

最初的 C++ 標準庫中沒有類似 hash_map 的實現(xiàn)，但不同實現(xiàn)者自己提供了非標準的 hash_map。 因為這些實現(xiàn)不是遵循標準編寫的，所以它們在功能和性能保證方面都有細微差別。

從 C++ 11 開始，hash_map 實現(xiàn)已被添加到標準庫中。但為了防止與已開發(fā)的代碼存在沖突，決定使用替代名稱 unordered_map。這個名字其實更具描述性，因為它暗示了該類元素的無序性。

unordered_map 原理

hashtable + bucket
由于 unordered_map 內(nèi)部采用 hashtable 的數(shù)據(jù)結(jié)構(gòu)存儲，所以，每個特定的 key 會通過一些特定的哈希運算映射到一個特定的位置，我們知道，hashtable 是可能存在沖突的，在同一個位置的元素會按順序鏈在后面。所以把這個位置稱為一個 bucket 是十分形象的，每個哈希桶中可能沒有元素，也可能有多個元素。

其插入過程是：
1、得到 key；
2、通過 hash 函數(shù)得到 hash 值；
3、得到桶號（一般都為 hash 值對桶數(shù)求模）；
4、存放 key 和 value 在桶內(nèi)（發(fā)生沖突，用比較函數(shù)解決）。

其取值過程是：
1、得到 key
2、通過 hash 函數(shù)得到 hash 值
3、得到桶號（一般都為 hash 值對桶數(shù)求模）
4、比較桶的內(nèi)部元素是否與 key 相等，若都不相等，則沒有找到。
5、取出相等的記錄的 value。

總結(jié)其特點如下：

• 關(guān)聯(lián)性：通過 key 去檢索 value，而不是通過絕對地址（和順序容器不同）
• 無序性：使用 hash 表存儲，內(nèi)部無序
• Map : 每個值對應一個鍵值（unordered_map<Key, Value> 的元素類型是 std::pair<const Key, Value>。如果有某個元素的Value部分的地址，減去 offsetof(std::pair<const Key, Value>, second) 再加上 offsetof(std::pair<const Key, Value>, first) （雖然估計是 0，不加也沒事），就是對應的 Key 部分的地址）
• 鍵唯一性：不存在兩個元素的 key 一樣（unordered_multimap 可以存放相同相同 key）
• 動態(tài)內(nèi)存管理：使用內(nèi)存管理模型來動態(tài)管理所需要的內(nèi)存空間

unordered_map 實現(xiàn)

unordered_map 類的定義：

// 通常只用得到前兩個 <Key, Ty>
template <class Key,  
          class Ty,  
          class Hash = std::hash<Key>,  
          class Pred = std::equal_to<Key>,  
          class Alloc = std::allocator<std::pair<const Key, Ty>>>
class unordered_map;

unordered_map 使用

頭文件：

#include <unordered_map>

取得鍵和值：

unordered_map<Key,T>::iterator it;
it->first;               // same as (*it).first   (the key value)
it->second;              // same as (*it).second  (the mapped value) 

成員函數(shù)：
===================迭代器====================
begin | 返回指向容器起始位置的迭代器（iterator）
end | 返回指向容器末尾位置的迭代器
cbegin | 返回指向容器起始位置的常迭代器（const_iterator）
cend | 返回指向容器末尾位置的常迭代器
===================Capacity===================
size 返回有效元素個數(shù)
max_size 返回 unordered_map 支持的最大元素個數(shù)
empty 判斷是否為空
===================元素訪問===================
operator[] 訪問元素
at 訪問元素（如 m.at(5) = 3.33）
===================元素修改===================
insert 插入元素
erase 刪除元素
swap 交換內(nèi)容
clear 清空內(nèi)容
emplace 構(gòu)造及插入一個元素
emplace_hint 按提示構(gòu)造及插入一個元素
=====================操作=====================
find 通過給定主鍵查找元素
count 返回匹配給定主鍵的元素的個數(shù)
equal_range 返回值匹配給定搜索值的元素組成的范圍
===================Buckets====================
bucket_count 返回槽（Bucket）數(shù)
max_bucket_count 返回最大槽數(shù)
bucket_size 返回槽大小
bucket 返回元素所在槽的序號
load_factor 返回載入因子，即一個元素槽（Bucket）的最大元素數(shù)
max_load_factor 返回或設置最大載入因子
rehash 設置槽數(shù)
reserve 請求改變?nèi)萜魅萘?/p>