當需要判斷一個元素是否在集合中時，就使用哈希法
?散列表（Hash table，也叫哈希表），是根據鍵（Key）而直接訪問在內存存儲位置的數據結構。
哈希表中關鍵碼就是數組的索引下標，然后通過下標直接訪問數組中的元素，復雜度O(1)
哈希表本質上是個數組，實現哈希表我們可以采用兩種方法：
1、數組+鏈表
2、數組+二叉樹
哈希函數
類似一個函數似的，給你一個值，經過某些加工得到另外一個值，就像這里的給你個人名，經過些許加工我們拿到首字母，那么這個函數或者是這個方法在哈希表中就叫做散列函數，其中規定的一些操作就叫做函數法則?
鍵值對，在jdk中就叫Entry
拉鏈法
剛剛小李和小王在索引1的位置發生了沖突，發生沖突的元素都被存儲在鏈表中。 這樣我們就可以通過索引找到小李和小王了
其實拉鏈法就是要選擇適當的哈希表的大小，這樣既不會因為數組空值而浪費大量內存，也不會因為鏈表太長而在查找上浪費太多時間。?
線性探測法
使用線性探測法，一定要保證tableSize大于dataSize。 我們需要依靠哈希表中的空位來解決碰撞問題。
例如沖突的位置，放了小李，那么就向下找一個空位放置小王的信息。
set
| 集合 | 底層實現 | 是否有序 | 數值是否可以重復 | 能否更改數值 | 查詢效率 | 增刪效率 |
|---|---|---|---|---|---|---|
| std::set | 紅黑樹 | 有序 | 否 | 否 | O(log n) | O(log n) |
| std::multiset | 紅黑樹 | 有序 | 是 | 否 | O(logn) | O(logn) |
| std::unordered_set | 哈希表 | 無序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底層實現為哈希表，std::set 和std::multiset 的底層實現是紅黑樹，紅黑樹是一種平衡二叉搜索樹，所以key值是有序的，但key不可以修改，改動key值會導致整棵樹的錯亂，所以只能刪除和增加。
set會自動將元素排序，默認升序排列。
set<int> s;s.insert(1);s.insert(0);s.insert(3);s.insert(3);s.insert(4);s.insert(7);for (int c : s) {cout << c << "";}for (set<int>::iterator it = s.begin(); it != s.end();it++) {cout << *it << endl;}for (set<int>::iterator it = --s.end(); it != --s.begin(); it--) {cout << *it << ' ';}//反向迭代器for (set<int>::reverse_iterator it = s.rbegin(); it != s.rend();it++) {cout << *it << endl;}map?
| 映射 | 底層實現 | 是否有序 | 數值是否可以重復 | 能否更改數值 | 查詢效率 | 增刪效率 |
|---|---|---|---|---|---|---|
| std::map | 紅黑樹 | key有序 | key不可重復 | key不可修改 | O(logn) | O(logn) |
| std::multimap | 紅黑樹 | key有序 | key可重復 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key無序 | key不可重復 | key不可修改 | O(1) | O(1) |
std::unordered_map 底層實現為哈希表，std::map 和std::multimap 的底層實現是紅黑樹。同理，std::map 和std::multimap 的key也是有序的
?紅黑樹(Red Black Tree)也叫RB樹
（1）為何map和set的插入刪除效率比用其他序列容器高？
大部分人說，很簡單，因為對于關聯容器來說，不需要做內存拷貝和內存移動。說對了，確實如此。set容器內所有元素都是以節點的方式來存儲，其節點結構和鏈表差不多，指向父節點和子節點。結構圖可能如下：
A
? / \
B C
/ \ / \
? D E F G
因此插入的時候只需要稍做變換，把節點的指針指向新的節點就可以了。刪除的時候類似，稍做變換后把指向刪除節點的指針指向其他節點也OK了。這里的一切操作就是指針換來換去，和內存移動沒有關系。
（2）為何每次insert之后，以前保存的iterator不會失效？
iterator這里就相當于指向節點的指針，內存沒有變，指向內存的指針怎么會失效呢(當然被刪除的那個元素本身已經失效了)。相對于vector來說，每一次刪除和插入，指針都有可能失效，調用push_back在尾部插入也是如此。因為為了保證內部數據的連續存放，iterator指向的那塊內存在刪除和插入過程中可能已經被其他內存覆蓋或者內存已經被釋放了。即使時push_back的時候，容器內部空間可能不夠，需要一塊新的更大的內存，只有把以前的內存釋放，申請新的更大的內存，復制已有的數據元素到新的內存，最后把需要插入的元素放到最后，那么以前的內存指針自然就不可用了。特別時在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。
（3）當數據元素增多時，set的插入和搜索速度變化如何？
如果你知道log2的關系你應該就徹底了解這個答案。在set中查找是使用二分查找，也就是說，如果有16個元素，最多需要比較4次就能找到結果，有32個元素，最多比較5次。那么有10000個呢？最多比較的次數為log10000，最多為14次，如果是20000個元素呢？最多不過15次。看見了吧，當數據量增大一倍的時候，搜索次數只不過多了1次，多了1/14的搜索時間而已。你明白這個道理后，就可以安心往里面放入元素了。
)
)
