當我們遇到了要快速判斷一個元素是否出現(xiàn)集合里的時候，就要考慮哈希法。
但是哈希法也是犧牲了空間換取了時間，因為我們要使用額外的數(shù)組，set或者是map來存放數(shù)據(jù)，才能實現(xiàn)快速的查找。
如果在做面試題目的時候遇到需要判斷一個元素是否出現(xiàn)過的場景也應(yīng)該第一時間想到哈希法！
如果hashCode得到的數(shù)值大于 哈希表的大小了，也就是大于tableSize，為了保證映射出來的索引數(shù)值都落在哈希表上，我們會在再次對數(shù)值做一個取模的操作，就要我們就保證了學(xué)生姓名一定可以映射到哈希表上了。
此時問題又來了，哈希表我們剛剛說過，就是一個數(shù)組。
如果學(xué)生的數(shù)量大于哈希表的大小怎么辦，此時就算哈希函數(shù)計算的再均勻，也避免不了會有幾位學(xué)生的名字同時映射到哈希表 同一個索引下標的位置。
接下來會用到哈希碰撞
哈希碰撞
如圖所示，小李和小王都映射到了索引下標 1 的位置，這一現(xiàn)象叫做哈希碰撞。
?哈希碰撞有兩解決辦法：拉鏈法和探測法。
1.拉鏈法；
剛剛小李和小王在索引1的位置發(fā)生了沖突，發(fā)生沖突的元素都被存儲在鏈表中。 這樣我們就可以通過索引找到小李和小王了。（數(shù)據(jù)規(guī)模是dataSize， 哈希表的大小為tableSize）
拉鏈法就是要選擇適當?shù)墓１淼拇笮。@樣既不會因為數(shù)組空值而浪費大量內(nèi)存，也不會因為鏈表太長而在查找上浪費太多時間。
?2.線性探測法
使用線性探測法，一定要保證tableSize大于dataSize。 我們需要依靠哈希表中的空位來解決碰撞問題。
例如沖突的位置，放了小李，那么就向下找一個空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就沒有空置的位置來存放 沖突的數(shù)據(jù)了。
?常見的三種哈希結(jié)構(gòu)：
1.數(shù)組
2.set（集合）
紅黑樹是一種平衡二叉搜索樹，所以key值是有序的，但key不可以修改，改動key值會導(dǎo)致整棵樹的錯亂，所以只能刪除和增加。
使用集合來解決哈希問題的時候，優(yōu)先使用unordered_set，因為它的查詢和增刪效率是最優(yōu)的，如果需要集合是有序的，那么就用set，如果要求不僅有序還要有重復(fù)數(shù)據(jù)的話，那么就用multiset。
3.map（映射）
?在map 是一個key value 的數(shù)據(jù)結(jié)構(gòu)，map中，對key是有限制，對value沒有限制的，因為key的存儲方式使用紅黑樹實現(xiàn)的。
雖然std::set、std::multiset 的底層實現(xiàn)是紅黑樹，不是哈希表，std::set、std::multiset 使用紅黑樹來索引和存儲，不過給我們的使用方式，還是哈希法的使用方式，即key和value。所以使用這些數(shù)據(jù)結(jié)構(gòu)來解決映射問題的方法，我們依然稱之為哈希法。 map也是一樣的道理。
LeetCode242.有效字母異位詞
題目鏈接：242. 有效的字母異位詞 - 力扣（LeetCode）??????
思路：
暴力解法:雙層for循環(huán)，同時記錄字符重復(fù)出現(xiàn)，時間復(fù)雜度為O(n*n)
哈希表解法：
定義一個數(shù)組叫做record（長度為26）用來上記錄字符串s里字符出現(xiàn)的次數(shù)。
需要把字符映射到數(shù)組也就是哈希表的索引下標上，因為字符a到字符z的ASCII是26個連續(xù)的數(shù)值，所以字符a映射為下標0，相應(yīng)的字符z映射為下標25。
再遍歷 字符串s的時候，只需要將 s[i] - ‘a(chǎn)’ 所在的元素做+1 操作即可，并不需要記住字符a的ASCII，只要求出一個相對數(shù)值就可以了。?這樣就將字符串s中字符出現(xiàn)的次數(shù)，統(tǒng)計出來了。
那看一下如何檢查字符串t中是否出現(xiàn)了這些字符，同樣在遍歷字符串t的時候，對t中出現(xiàn)的字符映射哈希表索引上的數(shù)值再做-1的操作。
那么最后檢查一下，record數(shù)組如果有的元素不為零0，說明字符串s和t一定是誰多了字符或者誰少了字符，return false。
最后如果record數(shù)組所有元素都為零0，說明字符串s和t是字母異位詞，return true。
時間復(fù)雜度為O(n)，空間上因為定義是的一個常量大小的輔助數(shù)組，所以空間復(fù)雜度為O(1)。
class Solution {
public:
bool isAnagram(string s, string t) {
int hash[26] = {0};
for(int i = 0;i < s.size();i++) {
hash[s[i]-'a']++;
}
for(int i = 0;i < t.size();i++) {
hash[t[i]-'a']--;
}
for(int i = 0;i < 26;i++) {
if(hash[i] != 0) return false;
}
return true;
}
};LeetCode349. 兩個數(shù)組的交集
題目鏈接：349. 兩個數(shù)組的交集 - 力扣（LeetCode）
思路：
這道題目，主要要學(xué)會使用一種哈希數(shù)據(jù)結(jié)構(gòu)：unordered_set，這個數(shù)據(jù)結(jié)構(gòu)可以解決很多類似的問題。
注意題目特意說明：輸出結(jié)果中的每個元素一定是唯一的，也就是說輸出的結(jié)果的去重的， 同時可以不考慮輸出結(jié)果的順序.
這道題用暴力的解法時間復(fù)雜度是O(n^2)，那來看看使用哈希法進一步優(yōu)化。
注意:使用數(shù)組來做哈希的題目，是因為題目都限制了數(shù)值的大小。
而這道題目沒有限制數(shù)值的大小，就無法使用數(shù)組來做哈希表了。
而且如果哈希值比較少、特別分散、跨度非常大，使用數(shù)組就造成空間的極大浪費。
unorder_set做法：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(),nums1.end());
for(int num:nums2) {
if(nums_set.find(num)!=nums_set.end()) {
result_set.insert(num);
}
}
return vector<int> (result_set.begin(),result_set.end());
}
};數(shù)組做法：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
int hash[1005] = {0};
for(int i = 0;i < nums1.size();i++) {
hash[nums1[i]] = 1;
}
for(int i = 0 ;i < nums2.size();i++) {
if(hash[nums2[i]] == 1) {
result_set.insert(nums2[i]);//往創(chuàng)建的unordered_set（result_set)添加數(shù)據(jù)
}
}
return vector<int> (result_set.begin(),result_set.end());//返回result_set
}
};LeetCode 202.快樂數(shù)
題目鏈接：202. 快樂數(shù) - 力扣（LeetCode）
思路：
題目中說了會?無限循環(huán)，那么也就是說求和的過程中，sum會重復(fù)出現(xiàn)，這對解題很重要！
當我們遇到了要快速判斷一個元素是否出現(xiàn)集合里的時候，就要考慮哈希法了。
所以這道題目使用哈希法，來判斷這個sum是否重復(fù)出現(xiàn)，如果重復(fù)了就是return false， 否則一直找到sum為1為止。
判斷sum是否重復(fù)出現(xiàn)就可以使用unordered_set。
還有一個難點就是求和的過程，如果對取數(shù)值各個位上的單數(shù)操作不熟悉的話，做這道題也會比較艱難。
class Solution {
public:
//找出每個位的數(shù)字
int getsum(int n) {
int sum = 0;
while(n != 0) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(true) {
int a = getsum(n);
//等于1時是快樂數(shù)
if(a == 1) return true;
//如果不是1的話繼續(xù)無限循環(huán)
//如果每次遍歷時在set找到了任意一個sum重復(fù)出現(xiàn)，就是無限循環(huán)
if(set.find(a) != set.end()) {
return false;
}
//如果沒找到，將該sum添加set
else set.insert(a);
//每次循環(huán)前將sum值賦值給a
n = a;
}
}
};LeetCode1.兩數(shù)之和
題目鏈接：1. 兩數(shù)之和 - 力扣（LeetCode）
思路：
首先我在強調(diào)一下?什么時候使用哈希法，當我們需要查詢一個元素是否出現(xiàn)過，或者一個元素是否在集合里的時候，就要第一時間想到哈希法。
本題呢，我就需要一個集合來存放我們遍歷過的元素，然后在遍歷數(shù)組的時候去詢問這個集合，某元素是否遍歷過，也就是 是否出現(xiàn)在這個集合，也應(yīng)該用哈希法。
因為本題，我們不僅要知道元素有沒有遍歷過，還要知道這個元素對應(yīng)的下標，需要使用 key value結(jié)構(gòu)來存放，key來存元素，value來存下標，那么使用map正合適。
再來看一下使用數(shù)組和set來做哈希法的局限。
- 數(shù)組的大小是受限制的，而且如果元素很少，而哈希值太大會造成內(nèi)存空間的浪費。
- set是一個集合，里面放的元素只能是一個key，而兩數(shù)之和這道題目，不僅要判斷y是否存在而且還要記錄y的下標位置，因為要返回x 和 y的下標。所以set 也不能用。
此時就要選擇另一種數(shù)據(jù)結(jié)構(gòu)：map ，map是一種key value的存儲結(jié)構(gòu)，可以用key保存數(shù)值，用value在保存數(shù)值所在的下標。
- map用來做什么
- map中key和value分別表示什么
map目的用來存放我們訪問過的元素，因為遍歷數(shù)組的時候，需要記錄我們之前遍歷過哪些元素和對應(yīng)的下標，這樣才能找到與當前元素相匹配的（也就是相加等于target）
接下來是map中key和value分別表示什么。
這道題 我們需要 給出一個元素，判斷這個元素是否出現(xiàn)過，如果出現(xiàn)過，返回這個元素的下標。
那么判斷元素是否出現(xiàn)，這個元素就要作為key，所以數(shù)組中的元素作為key，有key對應(yīng)的就是value，value用來存下標。
所以 map中的存儲結(jié)構(gòu)為 {key：數(shù)據(jù)元素，value：數(shù)組元素對應(yīng)的下標}。文章來源：http://www.zghlxwxcb.cn/news/detail-497800.html
在遍歷數(shù)組的時候，只需要向map去查詢是否有和目前遍歷元素匹配的數(shù)值，如果有，就找到的匹配對，如果沒有，就把目前遍歷的元素放進map中，因為map存放的就是我們訪問過的元素。文章來源地址http://www.zghlxwxcb.cn/news/detail-497800.html
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> map;
for(int i = 0; i < nums.size();i++) {
//遍歷當前元素，并在map中尋找匹配的key
auto iter = map.find(target - nums[i]);
//當map最后一個數(shù)不等于iter時，返回第i個元素的值
if(iter != map.end()) {
return {iter->second,i};
}
//插入數(shù)組的數(shù)字和序列到map做key和value
map.insert(pair<int,int>(nums[i],i));
}
return {};
}
};到了這里，關(guān)于代碼隨想錄第6天| 哈希表理論基礎(chǔ) ,LeetCode242.有效的字母異位詞，LeetCode349. 兩個數(shù)組的交集，LeetCode202. 快樂數(shù)，LeetCode1. 兩數(shù)之和的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
