1. 和關(guān)聯(lián)式容器一樣，無(wú)序容器也使用鍵值對(duì)（pair 類型）的方式存儲(chǔ)數(shù)據(jù)。不過(guò)，本教程將二者分開(kāi)進(jìn)行講解，因?yàn)樗鼈冇斜举|(zhì)上的不同：
   關(guān)聯(lián)式容器的底層實(shí)現(xiàn)采用的樹(shù)存儲(chǔ)結(jié)構(gòu)，更確切的說(shuō)是紅黑樹(shù)結(jié)構(gòu)；
   無(wú)序容器的底層實(shí)現(xiàn)采用的是哈希表的存儲(chǔ)結(jié)構(gòu)。
2. C++ STL 底層采用哈希表實(shí)現(xiàn)無(wú)序容器時(shí)，會(huì)將所有數(shù)據(jù)存儲(chǔ)到一整塊連續(xù)的內(nèi)存空間中，并且當(dāng)數(shù)據(jù)存儲(chǔ)位置發(fā)生沖突時(shí)，解決方法選用的是“鏈地址法”（又稱“開(kāi)鏈法”）
3. 基于底層實(shí)現(xiàn)采用了不同的數(shù)據(jù)結(jié)構(gòu)，因此和關(guān)聯(lián)式容器相比，無(wú)序容器具有以下 2 個(gè)特點(diǎn)：
   a. 無(wú)序容器內(nèi)部存儲(chǔ)的鍵值對(duì)是無(wú)序的，各鍵值對(duì)的存儲(chǔ)位置取決于該鍵值對(duì)中的鍵，
   和關(guān)聯(lián)式容器相比，無(wú)序容器擅長(zhǎng)通過(guò)指定鍵查找對(duì)應(yīng)的值（平均時(shí)間復(fù)雜度為 O(1)）
   b. 但對(duì)于使用迭代器遍歷容器中存儲(chǔ)的元素，無(wú)序容器的執(zhí)行效率則不如關(guān)聯(lián)式容器。

unordered_map容器

模版

template 
< class Key,class T,class Hash = hash<Key>, //容器內(nèi)部存儲(chǔ)鍵值對(duì)所用的哈希函數(shù)class Alloc = allocator<pair<const Key, T>> //判斷各個(gè)鍵值對(duì)鍵相同的規(guī)則,默認(rèn)情況下，使用 STL 標(biāo)準(zhǔn)庫(kù)中提供的 equal_to<key> 規(guī)則，該規(guī)則僅支持可直接用 == 運(yùn)算符做比較的數(shù)據(jù)類型。
>

    std::unordered_map<std::string, std::string> umap;umap.emplace("Python教程","http://c.biancheng.net/python/");umap.emplace("Java教程", "http://c.biancheng.net/java/");umap.emplace("Linux教程", "http://c.biancheng.net/linux/");//遍歷for(auto it = umap.begin(); it != umap.end(); ++it) {std::cout << it->first << " " << it->second << std::endl;}/*Linux教程 http://c.biancheng.net/linux/Java教程 http://c.biancheng.net/java/Python教程 http://c.biancheng.net/python/*/

這些內(nèi)容都比較無(wú)聊，看點(diǎn)別的

STL無(wú)序容器底層實(shí)現(xiàn)原理（深度剖析）

1. C++ STL 標(biāo)準(zhǔn)庫(kù)中，不僅是 unordered_map 容器，所有無(wú)序容器的底層實(shí)現(xiàn)都采用的是哈希表存儲(chǔ)結(jié)構(gòu)。更準(zhǔn)確地說(shuō)，是用“鏈地址法”（又稱“開(kāi)鏈法”）解決數(shù)據(jù)存儲(chǔ)位置發(fā)生沖突的哈希表，整個(gè)存儲(chǔ)結(jié)構(gòu)如圖 ：

• 其中，Pi 表示存儲(chǔ)的各個(gè)鍵值對(duì)。
• 可以看到，當(dāng)使用無(wú)序容器存儲(chǔ)鍵值對(duì)時(shí)，會(huì)先申請(qǐng)一整塊連續(xù)的存儲(chǔ)空間，但此空間并不用來(lái)直接存儲(chǔ)鍵值對(duì)，而是存儲(chǔ)各個(gè)鏈表的頭指針，各鍵值對(duì)真正的存儲(chǔ)位置是各個(gè)鏈表的節(jié)點(diǎn)。
• TL 標(biāo)準(zhǔn)庫(kù)通常選用 vector 容器存儲(chǔ)各個(gè)鏈表的頭指針。有意思～
• 不僅如此，在 C++ STL 標(biāo)準(zhǔn)庫(kù)中，將圖 1 中的各個(gè)鏈表稱為桶（bucket），每個(gè)桶都有自己的編號(hào)（從 0 開(kāi)始）。當(dāng)有新鍵值對(duì)存儲(chǔ)到無(wú)序容器中時(shí)，整個(gè)存儲(chǔ)過(guò)程分為如下幾步：
• 將該鍵值對(duì)中鍵的值帶入設(shè)計(jì)好的哈希函數(shù)，會(huì)得到一個(gè)哈希值（一個(gè)整數(shù)，用 H 表示）；
• 將 H 和無(wú)序容器擁有桶的數(shù)量 n 做整除運(yùn)算（即 H % n），該結(jié)果即表示應(yīng)將此鍵值對(duì)存儲(chǔ)到的桶的編號(hào)；
• 建立一個(gè)新節(jié)點(diǎn)存儲(chǔ)此鍵值對(duì)，同時(shí)將該節(jié)點(diǎn)鏈接到相應(yīng)編號(hào)的桶上。

負(fù)載因子（load factor）

負(fù)載因子 = 容器存儲(chǔ)的總鍵值對(duì) / 桶數(shù)

1. 默認(rèn)情況下，無(wú)序容器的最大負(fù)載因子為 1.0。如果操作無(wú)序容器過(guò)程中，使得最大復(fù)雜因子超過(guò)了默認(rèn)值，則容器會(huì)自動(dòng)增加桶數(shù)，并重新進(jìn)行哈希，以此來(lái)減小負(fù)載因子的值。
2. 需要注意的是，此過(guò)程會(huì)導(dǎo)致容器迭代器失效，但指向單個(gè)鍵值對(duì)的引用或者指針仍然有效。
3. 這也就解釋了，為什么我們?cè)诓僮鳠o(wú)序容器過(guò)程中，鍵值對(duì)的存儲(chǔ)順序有時(shí)會(huì)“莫名”的發(fā)生變動(dòng)。

成員方法 功能

bucket_count() 返回當(dāng)前容器底層存儲(chǔ)鍵值對(duì)時(shí)，使用桶的數(shù)量。
max_bucket_count() 返回當(dāng)前系統(tǒng)中，unordered_map 容器底層最多可以使用多少個(gè)桶。
bucket_size(n) 返回第 n 個(gè)桶中存儲(chǔ)鍵值對(duì)的數(shù)量。
bucket(key) 返回以 key 為鍵的鍵值對(duì)所在桶的編號(hào)。
load_factor() 返回 unordered_map 容器中當(dāng)前的負(fù)載因子。
max_load_factor() 返回或者設(shè)置當(dāng)前 unordered_map 容器的最大負(fù)載因子。
rehash(n) 嘗試重新調(diào)整桶的數(shù)量為等于或大于 n 的值。如果 n 大于當(dāng)前容器使用的桶數(shù)，則該方法會(huì)是容器重新哈希，該容器新的桶數(shù)將等于或大于 n。反之，如果 n 的值小于當(dāng)前容器使用的桶數(shù)，則調(diào)用此方法可能沒(méi)有任何作用。
reserve(n) 將容器使用的桶數(shù)（bucket_count() 方法的返回值）設(shè)置為最適合存儲(chǔ) n 個(gè)元素的桶數(shù)。
hash_function() 返回當(dāng)前容器使用的哈希函數(shù)對(duì)象。

//創(chuàng)建空的umap1std::unordered_map<std::string, std::string> umap1;std::cout << "umap初始捅數(shù) ：" << umap1.bucket_count()<<std::endl;std::cout << "umap初始負(fù)載因子 ：" << umap1.load_factor() << std::endl;std::cout << "umap 最大負(fù)載因子 ： " << umap1.max_load_factor() << std::endl;/*umap初始捅數(shù) ：0umap初始負(fù)載因子 ：0umap 最大負(fù)載因子 ： 1*///設(shè)置 umap 使用最適合存儲(chǔ) 9 個(gè)鍵值對(duì)的桶數(shù)umap1.reserve(9);std::cout << "umap新捅數(shù) ：" << umap1.bucket_count()<<std::endl;std::cout << "umap新負(fù)載因子 ：" << umap1.load_factor() << std::endl;/*umap新捅數(shù) ：11umap新負(fù)載因子 ：0*/umap1["Python教程"]   = "http://c.biancheng.net/python/";umap1["Java教程"]     = "http://c.biancheng.net/java/";umap1["Linux教程"]    = "http://c.biancheng.net/linux/";std::cout << "umap新捅數(shù) ：" << umap1.bucket_count()<<std::endl;std::cout << "umap新負(fù)載因子 ：" << umap1.load_factor() << std::endl;//調(diào)用 bucket() 獲取指定鍵值對(duì)位于桶的編號(hào)std::cout <<  "以\"Python教程\"為鍵的鍵值對(duì)，位于桶的編號(hào)為:" << umap1.bucket("Python教程") << std::endl;//自行計(jì)算某鍵值對(duì)位于哪個(gè)桶auto fn = umap1.hash_function();std::cout << "計(jì)算以\"Python教程\"為鍵的鍵值對(duì)，位于桶的編號(hào)為：" << fn("Python教程") % (umap1.bucket_count()) << std::endl;

關(guān)于哈希表

1. 常用的哈希函數(shù)的構(gòu)造方法有 6 種：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法和隨機(jī)數(shù)法。
2. 直接定址法

H（key）= key 或者 H（key）=a * key + b

3. 數(shù)字分析法: 果關(guān)鍵字由多位字符或者數(shù)字組成，就可以考慮抽取其中的 2 位或者多位作為該關(guān)鍵字對(duì)應(yīng)的哈希地址，在取法上盡量選擇變化較多的位，避免沖突發(fā)生。
   

4. 平方取中法是對(duì)關(guān)鍵字做平方操作，取中間得幾位作為哈希地址。此方法也是比較常用的構(gòu)造哈希函數(shù)的方法。

例如關(guān)鍵字序列為{421，423，436}，對(duì)各個(gè)關(guān)鍵字進(jìn)行平方后的結(jié)果為{177241，178929，190096}，則可以取中間的兩位{72，89，00}作為其哈希地址。

5. 折疊法 是將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址。此方法適合關(guān)鍵字位數(shù)較多的情況。

6. 除留余數(shù)法：若已知整個(gè)哈希表的最大長(zhǎng)度 m，可以取一個(gè)不大于 m 的數(shù) p，然后對(duì)該關(guān)鍵字 key 做取余運(yùn)算，即：

H（key）= key % p。

處理沖突的方法

1. 開(kāi)放定址法

H（key）=（H（key）+ d）MOD m（其中 m 為哈希表的表長(zhǎng)，d 為一個(gè)增量）

2. 當(dāng)?shù)贸龅墓５刂樊a(chǎn)生沖突時(shí)，選取以下 3 種方法中的一種獲取 d 的值，然后繼續(xù)計(jì)算，直到計(jì)算出的哈希地址不在沖突為止，這 3 種方法為：

• 線性探測(cè)法：d=1，2，3，…，m-1
• 二次探測(cè)法：d=12，-12，22，-22，32，…
• 偽隨機(jī)數(shù)探測(cè)法：d=偽隨機(jī)數(shù)

2. 再哈希法
   當(dāng)通過(guò)哈希函數(shù)求得的哈希地址同其他關(guān)鍵字產(chǎn)生沖突時(shí)，使用另一個(gè)哈希函數(shù)計(jì)算，直到?jīng)_突不再發(fā)生。

3. 鏈地址法
   將所有產(chǎn)生沖突的關(guān)鍵字所對(duì)應(yīng)的數(shù)據(jù)全部存儲(chǔ)在同一個(gè)線性鏈表中。例如有一組關(guān)鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函數(shù)為：H(key)=key MOD 13，使用鏈地址法所構(gòu)建的哈希表如圖 3 所示：