本節目標

1.unordered系列關聯式容器

2.底層結構

3.模擬實現

4.哈希的應用

5.海量數據處理面試題

unordered系列關聯式容器

在c++98中，STL提供了底層為紅黑樹結構的一系列關聯式容器，在查詢時效率可以達到logN，即最差的情況下需要比較紅黑樹的高度次，當樹中的結點非常多時，查詢效率也不理想。最好的查詢是，進行很少的比較次數就能夠將元素找到，因此c++11中，STL又提供了4個unordered系列的關聯式容器，這四個容器與紅黑樹結構的關聯式容器使用方式基本類似，只是其底層結構不同。

unordered_map

unordered_map的介紹

無序映射（unordered_map）是一種關聯式容器，用于存儲由鍵值（key）和映射值（mapped value）組合而成的元素， 并支持基于鍵的快速元素檢索。

在unordered_map中： - 鍵值通常用于唯一標識元素 - 映射值是與該鍵關聯的內容對象 - 鍵和映射值的類型可以不同 其內部實現特點：

1. 元素不會按照鍵值或映射值的順序排列

2. 基于哈希值組織到桶（buckets）中

3. 通過鍵值直接訪問元素的平均時間復雜度為O(1)

性能特性：

- 無序映射在通過鍵訪問單個元素時比有序映射（map）更快

- 但在迭代訪問元素子集時效率通常較低

接口特性：

- 支持直接訪問操作符（operator[]），可通過鍵值直接訪問映射值

- 容器提供的迭代器至少為前向迭代器（forward iterators）

unordered_map的接口使用說明

這些是別名，也就是typedef過的，為了方便后續理解，可以自行把常見和常用的了解一下

構造函數

empty (1)	
explicit unordered_map ( size_type n = /* see below */,                                const hasher& hf = hasher(),                                   const key_equal& eql = key_equal(),                           const allocator_type& alloc = allocator_type() );
explicit unordered_map ( const allocator_type& alloc );
range (2)	
template <class InputIterator>  
unordered_map ( InputIterator first, InputIterator last,   size_type n = /* see below */,const hasher& hf = hasher(),const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );
copy (3)	
unordered_map ( const unordered_map& ump );
unordered_map ( const unordered_map& ump, const allocator_type& alloc );
move (4)	
unordered_map ( unordered_map&& ump );
unordered_map ( unordered_map&& ump, const allocator_type& alloc );
initializer list (5)	
unordered_map ( initializer_list<value_type> il, size_type n = /* see below */,   const hasher& hf = hasher(),    const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() );

?總結：第一個就是構造一個空的非排序map?

? ? ? ? ? ? 第四個就是拷貝構造

? ? ? ? ? ? 第五個是迭代器構造

基本上知道第一個和第四個就行了，其他可以自行了解

capacity函數?

iterator函數

?

元素訪問函數

?

只要知道[]就可以了

modifier函數

?

學習insert erase clear swap即可

桶操作（具體可以等學習完hash后在了解）

?

unordered_set?

unordered_set的介紹和使用這里就不多加說明了，就是和set差不多，就是底層結構不一樣，我們重點學習底層結構

map/set和unordered_map/unordered_set有什么區別和聯系？

1.都可以實現key和key-value的搜索場景，并且功能和使用基本一樣

2.map/set的底層是用紅黑樹實現的，遍歷出來是有序的，增刪查改的時間復雜度為logN

3.unordered_map和unordered_set的底層是用哈希表實現的，遍歷出來的是無序的，增刪查改的時間復雜度為O(1)

4.map和set是雙向迭代器，unordered_map和unordered_set是單向的（僅支持++）

底層結構

請移步我的數據結構篇章中關于哈希表的講解（包括海量數據的處理都在那一篇章講解）