哈希表
表: 存儲數(shù)據(jù) key –> value;

用表來存儲數(shù)據(jù)結(jié)構(gòu)的困難: 查找困難。一個一個key去比較去查找，效率不高。因此有了Hash算法加快查找; 

將字符串的key,轉(zhuǎn)成整數(shù),使用整數(shù)找到對應的value;Hash算法將字符串轉(zhuǎn)成整數(shù)，同樣的Hash值的 key:value會放到一個集合里面，由于Hash能使得不同的字符串盡量有不同的整數(shù)值(仍然有重復); 將海量的數(shù)據(jù)，按照HASH值分成不同的集合，先找集合，再找key–>value,大大提高效率;

  散列技術(shù)是在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應關(guān)系f，使得每個關(guān)鍵字key對應一個存儲位置f(key)，adr = f(key)。查找時，根據(jù)這個確定的對應關(guān)系找到給定值key的映射f(key)，若查找集合中存在這個記錄，則必定在f(key)的位置上。我們把這種對應關(guān)系f稱為散列函數(shù)，又稱為哈希函數(shù)（Hash）.按這個思想，采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表或哈希表（Hash table）。關(guān)鍵字對應的記錄存儲位置稱為散列地址。

除留余數(shù)法

為最常用的構(gòu)造散列函數(shù)的方法。對于散列表長為m的散列函數(shù)公式為：f(key) = key mod p(p≤m)

   這種方法不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中后再取模。**散列表長為m，通常p為小于或等于表長（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。

 鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中，這種鏈表叫做同義詞子表，使用除留余數(shù)法，就不存在沖突的問題了，只是在鏈表中增加一個結(jié)點。

一、Map
映射是指兩個集合之間的元素的相互對應關(guān)系。通俗地說，就是一個元素對應另外一個元素。比如一個姓名的集合 {“Tom”, “Jone”, “Marry”}，班級集合{1, 2}。姓名與班級之間可以有如下的映射關(guān)系： class(“Tom”) = 1 , class(“Jone”) = 2 , class(“Marry”) = 1
我們稱其中的姓名集合為 關(guān)鍵字集合(key) , 班級集合為值集合(value) 。 在 C++ 中我們常用的映射是 map。

map的特點是增加和刪除節(jié)點對迭代器的影響很小。對于迭代器來說，可以修改實值，而不能修改key。
1、構(gòu)造一個映射

在C++中，我們構(gòu)造一個 map 的語句為：

map<T1,T2> m;
這樣我們定義了一個名為 m 的從 T1 類型到 T2 類型的映射。初始的時候 m 是空映射。

2、插入映射

插入有三種方法：

采用創(chuàng)建pair的形式插入pair<string, string>("string", "字符串")
采用make_pair的形式進行插入make_pair("apple", "蘋果")
采用大括號的形式進行插入{ "left", "左邊" }
通過 insert( ) 方法向集合中插入一個新的映射，參數(shù)是一個 pair 類型的結(jié)構(gòu)。這里需要用到另外一個 STL 模板 -元組(pair)。

map<string, int> dict; // {}
dict.insert(pair<string, int>("Tom", 1)); // {"Tom"->1}
dict.insert(pair<string, int>("Jone", 2)); // {"Tom"->1, "Jone"->2}

dict.insert(pair<string, string>("string", "字符串"));//模板類型pair：構(gòu)造了一個匿名對象插入到map
dict.insert(make_pair("apple", "蘋果"));//模板函數(shù)make_pair：偷懶了，實際調(diào)的是pair
dict.insert({ "left", "左邊" });
dict.insert({ "left", "剩余" });//插入不進去了，因為key值已經(jīng)有了
3、訪問映射

訪問映射合，直接用 [] 就能訪問。比如 dict[“Tom”] 就可以獲取 “Tom” 的班級了。而這里有一個比較神奇的地方，如果沒有對 “Tom” 做過映射的話，此時你訪問 dict[“Tom”] ，系統(tǒng)將會自動為 “Tom” 生成一個映射，其 value 為對應類型的默認值。并且我們可以之后再給映射賦予新的值，比如 dict[“Tom”] = 3 ，這樣為我們提供了另一種方便的插入手段。

map<string, int> dict;  // {}
dict["Tom"] = 1; // {"Tom"->1}
dict["Mary"] = 1; // {"Tom"->1, "Mary"->1}

printf("Mary is in class %d\n", dict["Mary"]);

4、查找關(guān)鍵字

count( ) :

 在 C++ 中，如果你想知道某個關(guān)鍵字是否被映射過，你可以直接用 count( ) 方法。使用count，返回的是被查找元素的個數(shù)。如果有，返回1；否則，返回0。注意，map中不存在相同元素(Tom,Mary)，所以返回值只能是1或0。

find()函數(shù)：

 find函數(shù)，返回的是被查找元素的位置，沒有則返回map.end()。注意：map.end()不指向最后一個元素，而指向最后一個元素再+1，當find不到輸入的元素時候，返回迭代器就指向這個end() 。

int main(){
map<string,int> test;
test.insert(make_pair("test1",1)); //test["test1"]=1
test.insert(make_pair("test2",2)); //test["test2"]=2
map<string,int>::iterator it=test.find("test0");

if(it==test.end())
    cout<<"test0 not found"<<endl;
else
    cout<<it->second<<endl;

cout<<test.count("test1")<<endl;

it=test.find("test1");
if(it==test.end())
    cout<<"test1 not found"<<endl;
else
    cout<<it->second<<endl;

輸出： test0 not found 1 1

5、遍歷映射

通過迭代器可以訪問映射中的每個映射，每個迭代器的 first 值對應key，second值對應value。

for (map<string, int>::iterator it = dict.begin(); it != dict.end(); ++it)
cout << it->first << " is in class " << it->second << endl;
6、其他

erase 刪除關(guān)鍵字
size 獲取映射對個數(shù)
clear 清空std::map 就是以key來查找value而設(shè)計，根據(jù)key排序。
list=[5,14,34,22,39,5];

map<int, int> map1;
for (int i=0; i<list.size(); i++){
map1[i] = list[i];
}
for (map<int, int>::iterator i = map1.begin(); i != map1.end(); i++){
cout << i->first << ' ' << i->second << endl;
}
if (map1.find(3) != map1.end()) {
cout << "find key=" << map1.find(3)->first << ", value=" << map1.find(3)->second << endl;
}
if (map1.count(5) > 0) {
cout << "count 5: " << map1.count(5) << endl;
}
輸出：
0 5
1 14
2 34
3 22
4 39
5 5
find key=3, value=22
count 5: 1

二、unordered_map
std::unordered_map 就是以key來查找value而設(shè)計,不會根據(jù)key排序。其實現(xiàn)使用了哈希表。

unordered_map<int, int> map;
for (int i=0; i<list.size(); i++){
map[i] = list[i];
}
cout << map[0] << endl;
for (unordered_map<int, int>::iterator i = map.begin(); i != map.end(); i++){
cout << i->first << ' ' << i->second << endl;
}
if (map.find(3) != map.end()) {
cout << "find key=" << map.find(3)->first << ", value=" << map.find(3)->second << endl;
}
if (map.count(5) > 0) {
cout << "find 5: " << map.count(5) << endl;
}
輸出：

5
5 5
4 39
3 22
2 34
1 14
0 5
find key=3, value=22
find 5: 1

count()返回要查找的key在map的所有key中的出現(xiàn)次數(shù)。因為此容器不允許重復，故count()只可能返回 1 或 0，即可判斷此key是否存在。有返回1，無返回0。
unordered_map也有find方法，得到的對象是一個iterator，在unordered_map中，如果find()沒找到要找的key，就返回和end()一樣的iterator值。
對比：

unordered_map和map類似，都是存儲的key-value的值，可以通過key快速索引到value。不同的是unordered_map不會根據(jù)key的大小進行排序，存儲時是根據(jù)key的hash值判斷元素是否相同，即unordered_map內(nèi)部元素是無序的，而map中的元素是按照二叉搜索樹存儲，進行中序遍歷會得到有序遍歷。

unordered_map可類比于Python中的字典。其實現(xiàn)使用了哈希表，可以以O(shè)(1)的時間復雜度訪問到對應元素，但缺點是有較高的額外空間復雜度。與之對應，STL中的map對應的數(shù)據(jù)結(jié)構(gòu)是紅黑樹，紅黑樹內(nèi)的數(shù)據(jù)時有序的，在紅黑樹上查找的時間復雜度是O(logN)，相對于unordered_map的查詢速度有所下降，但額外空間開銷減小。

結(jié)論：如果需要內(nèi)部元素自動排序，使用map，不需要排序使用unordered_map

二、集合
set作為一個容器也是用來存儲同一數(shù)據(jù)類型的數(shù)據(jù)類型，并且能從一個數(shù)據(jù)集合中取出數(shù)據(jù)，在set中每個元素的值都唯一，而且系統(tǒng)能根據(jù)元素的值自動進行排序，set的元素不像map那樣可以同時擁有實值(value)和鍵值(key),set元素的鍵值就是實值。set不允許兩個元素有相同的鍵值。C++的標準庫中的集合支持高效的插入、刪除和查詢操作，這三個操作的時間復雜度都是 O(lgn)，其中n是當前集合中元素的個數(shù)。如果用數(shù)組，雖然插入的時間復雜度是 O(1)，但是刪除合查詢都是 O(n)，此時效率太低。在C++中我們常用的集合是set。std::set 是基于hash表的，因此并不是順序存儲。

我們構(gòu)造set集合的目的是為了快速的檢索，不可直接去修改鍵值?？梢韵葎h后插。
1、構(gòu)造一個集合

set<T> s;
這樣我們定義了一個名為s的、儲存T類型數(shù)據(jù)的集合，其中T是集合要儲存的數(shù)據(jù)類型。初始的時候s是空集合。

2、插入元素

用 insert( ) 方法向集合中插入一個新的元素。注意如果集合中已經(jīng)存在了某個元素，再次插入不會產(chǎn)生任何效果，集合中是不會出現(xiàn)重復元素的。

set<string> country; // {}
country.insert("China"); // {"China"}
country.insert("America"); // {"China", "America"}
3、刪除元素

country.erase("America"); // {"China"}
4、查找元素

想知道某個元素是否在集合中出現(xiàn)，你可以直接用 count( ) 方法--返回某個值元素的個數(shù)，如果集合中存在我們要查找的元素，返回 1 ，否則返回 0 。
另一種方法是：find()--返回一個指向被查找到元素的迭代器
set<int> set;
for (int i=0; i<list.size(); i++){
set.insert(list[i]);
}
for (auto i = set.begin(); i != set.end(); i++) {
cout << *i << endl;
}
輸出：5 14 22 34 39

cout << set.count(5) << endl;
if(set.find(5) != set.end())
cout << *set.find(5) << endl;
輸出： 1 5

5、遍歷集合

for (set<string>::iterator it = country.begin(); it != country.end(); ++it)
cout << (*it) << endl;
注意：在C++中遍歷set是從小到大進行的。

6、其他

方法 功能
begin()

返回set容器的第一個元素
erase 刪除一個元素
end() 　　　　 返回set容器的最后一個元素
size 獲取元素的個數(shù)
clear 清空
from：https://www.cnblogs.com/omelet/p/6627667.html

unordered_set
std::unordered_set 是基于hash表的，因此并不是順序存儲。

unordered_set<int> set;
for (int i=0; i<list.size(); i++){
set.insert(list[i]);
}
for (unordered_set<int>::iterator i = set.begin(); i != set.end(); i++) {
cout << *i << endl;
}
cout << " find 39: " << *set.find(39) << endl;
cout << "count 14:" << set.count(5) << endl;
輸出：
22
39
34
14
5
find 39: 39
count 14:1

三、總結(jié)：
unordered_map和map：

unordered_map存儲機制是哈希表。unordered_map不會根據(jù)key的大小進行排序，存儲時是根據(jù)key的hash值判斷元素是否相同，即unordered_map內(nèi)部元素是無序的。

map是紅黑樹，紅黑樹內(nèi)的數(shù)據(jù)時有序的，里面的元素可以根據(jù)鍵進行自動排序。map中的元素是按照二叉搜索樹存儲，進行中序遍歷會得到有序遍歷。

如果需要內(nèi)部元素自動排序，使用map，不需要排序使用unordered_map

unordered_set和set：

unordered_set基于哈希表，是無序的。
set實現(xiàn)了紅黑樹的平衡二叉檢索樹的數(shù)據(jù)結(jié)構(gòu)，插入元素時，它會自動調(diào)整二叉樹的排列，把元素放到適當?shù)奈恢?，以保證每個子樹根節(jié)點鍵值大于左子樹所有節(jié)點的鍵值，小于右子樹所有節(jié)點的鍵值；另外，還得保證根節(jié)點左子樹的高度與右子樹高度相等。平衡二叉檢索樹使用中序遍歷算法，檢索效率高于vector、deque和list等容器，另外使用中序遍歷可將鍵值按照從小到大遍歷出來。

set和map的區(qū)別：
1、set里面每個元素只存有一個key值，它支持高效的關(guān)鍵字查詢操作，比如檢查一個關(guān)鍵字是否在set中。如果這個key值之前存在的話就不插入。

set<int> s;
s.insert(2);
s.insert(1);
s.insert(4);
s.insert(5);
s.insert(3);
s.insert(5);
s.insert(5);
for (auto e : s)
cout << e << " ";
打印出來的值為1 2 3 4 5。set容器自動對以上數(shù)據(jù)進行了排序，并且實現(xiàn)了去重。但是不能對set里的值進行修改，

set容器中的find查找效率高，因為底層是一個二叉搜索樹，比要查找的值小就去左子樹查找，反之則去右子樹查找。

2、 map是一種key(鍵),value(值)的形式，用來保存鍵和值組成的集合，鍵必須是唯一的，但值可以不唯一。里面的元素可以根據(jù)鍵進行自動排序，由于map是key_value的形式，所以map里的所有元素都是pair類型。pair里面的first被稱為key(鍵），second被稱為value(值）。它可以通過關(guān)鍵字key查找映射關(guān)聯(lián)信息value，同時根據(jù)key值進行排序。

set和map都以RBTree作為底層容器
set：

所得元素的只有key沒有value，value就是key
不允許出現(xiàn)鍵值重復
所有的元素都會被自動排序
不能通過迭代器來改變set的值，因為set的值就是鍵
map：

map的值不作為鍵，鍵和值是分開的，所有元素都是鍵+值存在
不允許鍵重復
所有元素是通過鍵進行自動排序的
map的鍵是不能修改的，但是其鍵對應的值是可以修改的
————————————————
版權(quán)聲明：本文為CSDN博主「菜鳥知識搬運工」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/qq_30815237/article/details/91047041