哈希表
1、哈希表是根據關鍵碼的值而直接進行通路的資料結構。
2、一般哈希表都是用來快速判斷一個元素是否出現集合裡。
例如要查詢一個名字是否在這所學校裡。
要枚舉的話時間複雜度是O(n)，但如果使用哈希表的話， 隻需要O(1) 就可以做到。
我們隻需要初始化把這所學校裡學生的名字都存在哈希表裡，在查詢的時候通過索引直接就可以知道這位同學在不在這所學校裡了。
将學生姓名映射到哈希表上就涉及到了「hash function ，也就是哈希函數」。
哈希函數
哈希函數，把學生的姓名直接映射為哈希表上的索引，然後就可以通過查詢索引下表快速知道這位同學是否在這所學校裡了。
哈希函數如下圖所示，通過hashCode把名字轉化為數值，一般hashcode是通過特定編碼方式，可以将其他資料格式轉化為不同的數值，這樣就把學生名字映射為哈希表上的索引數字了。
如果hashCode得到的數值大于 哈希表的大小了，也就是大于tableSize了，怎麼辦呢？
此時為了保證映射出來的索引數值都落在哈希表上，我們會再次對數值做一個取模的操作，這樣我們就保證了學生姓名一定可以映射到哈希表上了。
此時問題又來了，哈希表我們剛剛說過，就是一個數組。
如果學生的數量大于哈希表的大小怎麼辦，此時就算哈希函數計算的再均勻，也避免不了會有幾位學生的名字同時映射到哈希表 同一個索引下表的位置。
接下來「哈希碰撞」登場
哈希碰撞
一般哈希碰撞有兩種解決方法， 拉鍊法和線性探測法
拉鍊法
剛剛小李和小王在索引1的位置發生了沖突，發生沖突的元素都被存儲在連結清單中。這樣我們就可以通過索引找到小李和小王了
其實拉鍊法就是要選擇适當的哈希表的大小，這樣既不會因為數組空值而浪費大量記憶體，也不會因為連結清單太長而在查找上浪費太多時間。
線性探測法
使用線性探測法，一定要保證tableSize大于dataSize。我們需要依靠哈希表中的空位來解決碰撞問題。
例如沖突的位置，放了小李，那麼就向下找一個空位放置小王的資訊。是以要求tableSize一定要大于dataSize ，要不然哈希表上就沒有空置的位置來存放 沖突的資料了。如圖所示：
常見的三種哈希結構(&&&)
當我們想使用哈希法來解決問題的時候，我們一般會選擇如下三種資料結構。
數組
set （集合）
map(映射)
數組
set 、map
在C++語言中，set 和 map 分别提供了以下三種資料結構，其底層實作以及優劣如下表所示：
std::unordered_set底層實作為哈希表，std::set 和std::multiset 的底層實作是紅黑樹，紅黑樹是一種平衡二叉搜尋樹，是以key值是有序的，但key不可以修改，改動key值會導緻整棵樹的錯亂，是以隻能删除和增加。
std::unordered_map 底層實作為哈希表，std::map 和std::multimap 的底層實作是紅黑樹。同理，std::map 和std::multimap 的key也是有序的（這個問題也經常作為面試題，考察對語言容器底層的了解）。
當我們要使用集合來解決哈希問題的時候，優先使用unordered_set，因為它的查詢和增删效率是最優的，如果需要集合是有序的，那麼就用set，如果要求不僅有序還要有重複資料的話，那麼就用multiset。
那麼再來看一下map ，在map 是一個key value 的資料結構，map中，對key是有限制，對value沒有限制的，因為key的存儲方式使用紅黑樹實作的。
其他語言例如：java裡的 HashMap ，TreeMap 都是一樣的原理。可以靈活貫通。
雖然set、multiset 的底層實作是紅黑樹，不是哈希表，但是set、multiset 依然使用哈希函數來做映射，隻不過底層的符号表使用了紅黑樹來存儲資料，是以使用這些資料結構來解決映射問題的方法，我們依然稱之為哈希法。map也是一樣的道理。
總結
當我們遇到了要快速判斷一個元素是否出現集合裡的時候，就要考慮哈希法。
但是哈希法也是犧牲了空間換取了時間，因為我們要使用額外的數組，set或者是map來存放資料，才能實作快速的查找。