Hash 總結
source:: 代码随想录
#clippings
哈希表總結篇如約而至
在關於哈希表，你該瞭解這些！ (opens new window)中，我們介紹了哈希表的基礎理論知識，不同於枯燥的講解，這裡介紹了都是對刷題有幫助的理論知識點。
一般來說哈希表都是用來快速判斷一個元素是否出現集合裡。
對於哈希表，要知道哈希函數和哈希碰撞在哈希表中的作用.
哈希函數是把傳入的key映射到符號表的索引上。
哈希碰撞處理有多個key映射到相同索引上時的情景，處理碰撞的普遍方式是拉鍊法和線性探測法。
接下來是常見的三種哈希結構：
- 數組
- set（集合）
- map（映射）
在C++語言中，set 和 map 都分別提供了三種數據結構，每種數據結構的底層實現和用途都有所不同，在關於哈希表，你該瞭解這些！ (opens new window)中我給出了詳細分析，這一知識點很重要！
例如什麼時候用std::set，什麼時候用std::multiset，什麼時候用std::unordered_set，都是很有考究的。
只有對這些數據結構的底層實現很熟悉，才能靈活使用，否則很容易寫出效率低下的程式。
數組作為哈希表
一些應用場景就是為數組量身定做的。
在242.有效的字母異位詞 (opens new window)中，我們提到了數組就是簡單的哈希表，但是數組的大小是受限的！
這道題目包含小寫字母，那麼使用數組來做哈希最合適不過。
在383.贖金信 (opens new window)中同樣要求只有小寫字母，那麼就給我們濃濃的暗示，用數組！
本題和242.有效的字母異位詞 (opens new window)很像，242.有效的字母異位詞 (opens new window)是求 字符串a 和 字符串b 是否可以相互組成，在383.贖金信 (opens new window)中是求字符串a能否組成字符串b，而不用管字符串b 能不能組成字符串a。
一些同學可能想，用數組幹啥，都用map不就完事了。
上面兩道題目用map確實可以，但使用map的空間消耗要比數組大一些，因為map要維護紅黑樹或者符號表，而且還要做哈希函數的運算。所以數組更加簡單直接有效！
set作為哈希表
在349. 兩個數組的交集 (opens new window)中我們給出了什麼時候用數組就不行了，需要用set。
這道題目沒有限製數值的大小，就無法使用數組來做哈希表了。
主要因為如下兩點：
- 數組的大小是有限的，受到系統棧空間（不是數據結構的棧）的限製。
- 如果數組空間夠大，但哈希值比較少、特別分散、跨度非常大，使用數組就造成空間的極大浪費。
所以此時一樣的做映射的話，就可以使用set了。
關於set，C++ 給提供了如下三種可用的數據結構：（詳情請看關於哈希表，你該瞭解這些！ (opens new window)）
- std::set
- std::multiset
- std::unordered_set
std::set和std::multiset底層實現都是紅黑樹，std::unordered_set的底層實現是哈希， 使用unordered_set 讀寫效率是最高的，本題並不需要對數據進行排序，而且還不要讓數據重複，所以選擇unordered_set。
在202.快樂數 (opens new window)中，我們再次使用了unordered_set來判斷一個數是否重複出現過。
map作為哈希表
在1.兩數之和 (opens new window)中map正式登場。
來說一說：使用數組和set來做哈希法的局限。
- 數組的大小是受限製的，而且如果元素很少，而哈希值太大會造成內存空間的浪費。
- set是一個集合，裡面放的元素只能是一個key，而兩數之和這道題目，不僅要判斷y是否存在而且還要記錄y的下標位置，因為要返回x 和 y的下標。所以set 也不能用。
map是一種<key, value>的結構，本題可以用key保存數值，用value在保存數值所在的下標。所以使用map最為合適。
C++提供如下三種map：：（詳情請看關於哈希表，你該瞭解這些！ (opens new window)）
- std::map
- std::multimap
- std::unordered_map
std::unordered_map 底層實現為哈希，std::map 和std::multimap 的底層實現是紅黑樹。
同理，std::map 和std::multimap 的key也是有序的（這個問題也經常作為面試題，考察對語言容器底層的理解），1.兩數之和 (opens new window)中並不需要key有序，選擇std::unordered_map 效率更高！
在454.四數相加 (opens new window)中我們提到了其實需要哈希的地方都能找到map的身影。
本題咋眼一看好像和18. 四數之和 (opens new window)，15.三數之和 (opens new window)差不多，其實差很多！
關鍵差別是本題為四個獨立的數組，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考慮重複問題，而18. 四數之和 (opens new window)，15.三數之和 (opens new window)是一個數組（集合）裡找到和為0的組合，可就難很多了！
用哈希法解決了兩數之和，很多同學會感覺用哈希法也可以解決三數之和，四數之和。
其實是可以解決，但是非常麻煩，需要去重導致代碼效率很低。
在15.三數之和 (opens new window)中我給出了哈希法和雙指針兩個解法，大家就可以體會到，使用哈希法還是比較麻煩的。
所以18. 四數之和，15.三數之和都推薦使用雙指針法！
對於哈希表的知識相信很多同學都知道，但是沒有成體系。
本篇我們從哈希表的理論基礎到數組、set和map的經典應用，把哈希表的整個全貌完整的呈現給大家。
同時也強調雖然map是萬能的，詳細介紹了什麼時候用數組，什麼時候用set。
相信通過這個總結篇，大家可以對哈希表有一個全面的瞭解。