在平時的工作或面試中，經常需要考慮容器的選擇問題，其中“map和hash_map的差異點”出現的機率最高。那麼，我們從底層原理上看看具體都有哪些區別和聯絡。
目錄
為了方便大家閱讀文章，我們先介紹一下文章結構，大家可以直接跳到感興趣的位置進行閱讀。
先簡單介紹map和hash_map的底層原理，hash_map會從c++和java兩個語言進行描述。
透過表格形式對比介紹map和hash_map的特點。
透過程式碼分析hash_map的原理。
展示c++的hash_map儲存資料的效果圖
文章總結，快速進行map和hash_map選型的方法。
測試程式碼原始碼。
map底層結構原理
使用紅黑樹進行資料儲存。
紅黑樹有四個原則，遵守這四個原則就可以構建紅黑樹：
（1）根節點為黑色；
（2）葉子結點為空值的黑色結點；
（3）紅色結點的兩個子節點必須為黑色；
（4）所有葉子結點到根結點的路徑中，黑色結點個數要一樣；
紅黑樹儲存資料示意圖
c++的hash_map/unordered_map底層結構原理
備註：unordered_map和hash_map基本一樣，只是
unordered_map已經加到C++11標準，
而hash_map未加入在C++11標準中。
使用雜湊表進行資料儲存，主要涉及如下幾點，
①雜湊表：
使用陣列（bucket陣列，實際使用的vector）+連結串列等結構一起構成了雜湊表。
②雜湊函式：
雜湊函式指將雜湊表中元素的關鍵鍵值對映為元素儲存位置的函式。
雜湊表中雜湊函式的實現步驟大概如下：
✓生成 key 的雜湊值（必須是整數），
✓再讓 key 的雜湊值跟陣列的大小進行相關運算，生成一個索引值。
③map的key ：
常見種類有整數、浮點數、字串、自定義物件。
不同種類的 key，雜湊值的生成方式不一樣，但目標是一致的
✓ 儘量讓每個 key 的雜湊值是唯一的
✓ 儘量讓 key 的所有資訊參與運算
④bucket陣列的擴容機制
擴容時需要滿足兩個條件：存放新值的時候當前hash_map所有元素的個數大於等於閾值；存放新值的時候當前存放資料發生hash碰撞。
STL會預設指定初始桶大小為16，
負載因子是0。75
，因此閾值就是16*0。75 = 12，所以當新插入元素時，當前的元素個數超過12，並且發生了衝突，就會擴容hash桶。
擴容的大小是之前的陣列翻倍。
在hashmap陣列擴容之後，最消耗效能的點就出現了：原陣列中的資料必須重新計算其在新陣列中的位置，並放進去，這就是resize。 所以如果已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效地提高hashmap的效能，例如最多有1000個元素，則建立時：new HashMap（2048）（1024是不夠的，要考慮負載因子：1024*0。75 = 768）。
另外桶的大小為2的冪次方時，hash_map的效率最高。這是因為：正常的取index方法為hash%length，但是由於位運算比取餘快，所以程式碼中實現為index = hash & （length - 1），所以只有length大小為2的次冪時：hash % length == hash & （length - 1）。
c++雜湊表儲存資料示意圖
思考：
我們可以發現，這個桶陣列的效率，高不高，完全取決於我們的雜湊表的長度取得是否恰當，如果桶陣列太短，那麼連結串列就會累積的很長，如果桶陣列太長，又會造成很大的空間浪費，所以，這也是雜湊表的缺點不足之一，為了儘量避免，雜湊表的長度，一般取為質數。
java的hash_map底層結構原理
在jdk8中，使用連結串列和紅黑樹兩種方式對接雜湊表的桶，我們都知道，連結串列構建很簡單，而紅黑樹，一個結點就會多4個區域，也存在空間的浪費，但是查詢效率會高很多，所以為了達到最好的效果，設定了一個閾值控制桶下的結點數，如果超過了這個值，那麼就會轉為為紅黑樹存放。
java雜湊表儲存資料示意圖
map和hash_map的特點
（1）共同點：
都是map的實現類，都是鍵值對集合；
裡邊的元素都跟新增順序無關；
（2）差異點：
型別
特點
優點
缺點
應用場景
map
底層是用
紅黑樹
實現的，查詢時間複雜度是O（log（n））；
因使用紅黑樹實現，所以資料是
有序儲存的，
因此map的key需要
過載
operator<
；
鍵物件在集合中是唯一的，可以透過鍵來直接查詢值；
有序儲存
，元素可以自動按照鍵值排序。
記憶體佔用比
hash_map少。
l 查詢速度比
hash_map
慢，
map的查詢速度是log（n）級別。
適用於有順序要求的問題，使用map會更高效一些；
如果對記憶體使用特別嚴格，需要程式儘可能少消耗記憶體，那麼應該使用map，因為hash_map佔用記憶體較多。
hash_map
底層是用
hash表
儲存的，查詢時間複雜度是O（1）；
基於hash
無序儲存
的，因此
需要過載
operator==
；
使用雜湊演算法對鍵去重複，效率高，但無序；
HashMap是Map介面的主要實現類；
查詢的時間複雜度幾乎是常數時間O（1）。
備註：hash_map的查詢不一定是o（1），在有雜湊衝突進行桶內資料查詢時，需要遍歷連結串列。
無自動排序功能；
佔用比較多的記憶體
；
擴容會自動擴大使用記憶體：
如果在元素達到一定數量級時同時要考慮效率，但是不考慮記憶體消耗，此時應該使用hash_map。
透過程式碼分析hash_map的原理
1.輸入資料：
我們順序輸入以下
增序資料
進行測試，{5，“5”}，{10，“10”}，{15，“15”}，{20，“20”}，{25，“25”}，{30，“30”}，{35，“35”}，{40，“40”}，{45，“45”}，{50，“50”}，{55，“55”}，{60，“60”}，{65，“65”}，{70，“70”}，{75，“75”}，{80，“80”}，{85，“85”}，{90，“90”}，{95，“95”}，{100，“100 ”}，{101，“101 ”}，{102，“102 ”}，{103，“103 ”}，{104，“104 ”}，{105，“105 ”}，{106，“106 ”}，{107，“107 ”}，{108，“108 ”}，{109，“109 ”}，{200，“200 ”}。
2.根據輸出日誌分析原理：
資料結構內部儲存資料的順序並不是完全按照輸入順序或數值大小進行排序的；
雜湊表中單鏈表儲存的資料，先輸入的資料在連結串列的最後面，後輸入的資料在連結串列的最前面；
重置bucket大小
後（重置的bucket大小大於原bucket大小），
哈表表要重建表格
，會打亂桶（vector）和連結串列（單鏈表）節點的儲存和位置定位。
擴充後的bucket大小，擴容的大小是之前的陣列翻倍
（直到能涵蓋住重置大小的數值）。
重置bucket時重建表格的原理：
hash_map示意圖
因為我使用的hash_map演示工具暫時只能設定12個桶，所以下面展示的示意圖和上面的測試程式碼的實際效果不一樣。但是大家一樣可以透過這個示意圖看出來雜湊表的特點：
資料結構內部儲存資料的順序並不是完全按照輸入順序或數值大小進行排序的；
雜湊表中單鏈表儲存的資料，先輸入的資料在連結串列的最後面，後輸入的資料在連結串列的最前面；
hash_map示意圖
總結
需要無序容器，快速查詢刪除，不擔心略高的記憶體時用unordered_map；
有序容器穩定查詢刪除效率，記憶體很在意時候用map。
示例程式碼
#include
#include
using namespace std；
void fun_unordered_map_test（）
{
//構造資料
unordered_map
{5，“5”}，{10，“10”}，{15，“15”}，{20，“20”}，{25，“25”}，{30，“30”}，{35，“35”}，
{40，“40”}，{45，“45”}，{50，“50”}，{55，“55”}，{60，“60”}，{65，“65”}，{70，“70”}，
{75，“75”}，{80，“80”}，{85，“85”}，{90，“90”}，{95，“95”}，{100，“100 ”}，
{101，“101 ”}，{102，“102 ”}，{103，“103 ”}，{104，“104 ”}，{105，“105 ”}，
{106，“106 ”}，{107，“107 ”}，{108，“108 ”}，{109，“109 ”}，{200，“200 ”}
}；
//列印資料
cout << endl；
size_t bucket_count = hash_map_obj。bucket_count（）；
cout << “ unordered_map bucket的總數bucket_count：” << bucket_count << “ 桶數量最大值max_bucket_count：” << hash_map_obj。max_bucket_count（） << endl；
cout << “ unordered_map 實際元素個數：” << hash_map_obj。size（） << “ 遍歷迭代器列印儲存的資料：” << endl；
unordered_map
for （； iter_print ！= hash_map_obj。end（）； ++iter_print）
{
cout << “ 鍵：” << （*iter_print）。first << “ 值：‘” << （*iter_print）。second << “’ is in bucket #” << hash_map_obj。bucket（（*iter_print）。first） << endl；
}
//bucket操作
cout << endl；
cout << “ unordered_map 按照bucket列印儲存的資料：” << endl；
//bucket_size（） 返回第i個bucket桶子裡有幾個元素，注意：函式不會判斷n是否在count範圍內
for （size_t i = 0； i < bucket_count； ++i）
{
cout << “ bucket #” << i << “‘s size：” << hash_map_obj。bucket_size（i） << “ contains： ”；
//輸出每個list節點
for （auto it = hash_map_obj。begin（i）； it ！= hash_map_obj。end（i）； ++it）
{
cout << “ ［鍵：” << it->first << “ 值：’” << it->second << “‘］ ”；
}
cout << endl；
}
cout << endl；
cout << “ unordered_map 調整bucket_size為100” << endl；
hash_map_obj。reserve（100）；//調整bucket_size為100
cout << “ unordered_map bucket_count：” << hash_map_obj。bucket_count（） << “ max_bucket_count：” << hash_map_obj。max_bucket_count（） << endl；
iter_print = hash_map_obj。begin（）；
for （； iter_print ！= hash_map_obj。end（）； ++iter_print）
{
cout << “ 鍵：” << （*iter_print）。first << “ 值：’” << （*iter_print）。second << “‘ is in bucket #” << hash_map_obj。bucket（（*iter_print）。first） << endl；
}
}
int main（）
{
fun_unordered_map_test（）；
return 0；
}
原創不易，歡迎點贊、收藏、關注！
