哈希表篇

文章目錄

哈希表篇
- 1.哈希表簡述
- 1.1哈希表
- 1.2哈希函數
- - 1.3哈希沖突
  - 1.3.1開放位址法
  - 1.3.2鍊位址法
  - 1.3.3常見的三種哈希結構
- 2. 242.有效的字母異位詞
- 3. 349. 兩個數組的交集
- 3. 202題. 快樂數
- 4.1002. 查找常用字元
- 5. 1.兩數之和
- 6.第454題.四數相加II **
- 7.383. 贖金信
- 8.第15題. 三數之和 ***
- 總結

1.哈希表簡述

1.1哈希表

哈希表（Hash Table），也會有書本将其翻譯成散清單。

根據關鍵字和值進行通路的資料結構。可以通過關鍵字Key和一盒映射函數Hash(Key)計算出對應的value,然後将鍵值對映射到表中的一個位置來進行通路。

哈希表的關鍵思想是使用哈希函數，将Key和值value映射到對應表的某個區塊。

直白的來說數組就是一張哈希表，哈希表的關鍵字key就是數組下标，然後通過下标通路數組中的元素

哈希表（Hash table）篇哈希表篇

1.2哈希函數

哈希函數：将哈希表中元素的關鍵值映射為元素存儲位置的函數

哈希函數應該易于計算，并且盡量使計算出來的索引值均勻分布，這能減少哈希沖突

哈希函數計算得到的哈希值是一個固定長度的輸出值

如果 Hash(key1) 不等于 Hash(key2)，那麼 key1、key2 一定不相等

如果 Hash(key1) 等于 Hash(key2)，那麼 key1、key2 可能相等，也可能不相等（會發生哈希碰撞）

在哈希表的實際應用中，關鍵字的類型除了數字類型，字元串類型、浮點數類型、大整數類型，甚至還有可能是幾種類型的組合。一般會将各種類型的關鍵字先轉換為整數類型，再通過哈希函數，将其映射到哈希表中。

在常用的哈希函數中常用的是除法哈希函數

f ( k ) = k m o d D f(k)=k mod D f(k)=kmodD

k為關鍵字，D為哈希表的長度（哈希表的每一個位置叫做桶bucket）

1.3哈希沖突

哈希沖突：不同關鍵字通過哈希函數有可能得到相同的哈希位址，即當key1!=key2時，hash(key1)=hash(key2),這種現象被稱為哈希沖突

1.3.1開放位址法

将哈希表的空位址在處理沖突時開放，當哈希表未滿時，處理沖突順着目前的哈希位址向後找尋空位址，直到找到空位址

哈希表（Hash table）篇哈希表篇

如上圖所示，此哈希表有7個桶，按照除法哈希函數所示

7mod7=0, 9mod7=2;假設當16mod7=2時，16将往下順延。

哈希表（Hash table）篇哈希表篇

1.3.2鍊位址法

将具有相同哈希位址的元素都存儲在同一個線性連結清單中。鍊位址法是一種更常用的哈希沖突解決方法。假設哈希函數産生的位址區間為[0,m-1],哈希表的表長為m，則可以将哈希表定義為一個有 m 個頭節點組成的連結清單指針數組 T。

哈希表（Hash table）篇哈希表篇

上圖的bucket為13。

1.3.3常見的三種哈希結構

1.數組 2.set（集合） 3.map(映射)

在C++中，set和map分别提供以下幾種資料結構

集合	底層實作	是否有序	數值是否可以重複	能否更改數值	查詢效率
std::set	紅黑樹	有序	否	否	O(logn)
std::multiset	紅黑樹	有序	是	否	O(logn)
std::unordered_set	哈希表	無序	否	否	O(1)
std::unordered_multiset	哈希表	無序	是	否	O(1)

紅黑樹是一種平衡二叉搜尋樹，是以key值有序，但key不可以被修改，改動key值會使整棵樹錯位，隻能增加和删除。

映射	底層實作	是否有序	數值是否可以重複	能否更改數值	查詢效率
std::map	紅黑樹	key有序	key不可重複	key不可修改	O(logn)
std::multimap	紅黑樹	key有序	key可重複	key不可修改	O(logn)
std::unordered_map	哈希表	key無序	key不可重複	key不可修改	O(1)
std::unordered_multimap	哈希表	key無序	key可重複	key不可修改	O(1)

map中對key值有限制，對value沒有限制。當解決問題時要注意當需要集合有序那樣優先使用unordered_map和unordered_set,他的效率更高，當資料可以重複時使用multiset和multimap。

2. 242.有效的字母異位詞

https://leetcode-cn.com/problems/valid-anagram/

給定兩個字元串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。

示例 1:

輸入: s = “anagram”, t = “nagaram”

輸出: true

示例 2:

輸入: s = “rat”, t = “car”

輸出: false

說明:

你可以假設字元串隻包含小寫字母。

此題符合哈希表（數組）做法的特征：記錄有限個值出現的次數。上題的字母為有限個26，可以用數組表示哈希表，将數組下标作為key，字母出現次數作為value

class Solution {
public:
bool isAnagram(string s, string t) {
int a[26]={0};
for(auto i:s)
    a[i-'a']++;
for(auto j:t)
	a[j-'a']--;
for(int k=0;k<26;k++)
{
    if(a[k]!=0)
    	 return false;
}
return true;
}
};

3. 349. 兩個數組的交集

https://leetcode-cn.com/problems/intersection-of-two-arrays/

題意：給定兩個數組，編寫一個函數來計算它們的交集。

哈希表（Hash table）篇哈希表篇

**說明：**輸出結果中的每個元素一定是唯一的。我們可以不考慮輸出結果的順序。

如果哈希值比較少、特别分散、跨度非常大，使用數組就造成空間的極大浪費
使用set 不僅占用空間比數組大，而且速度要比數組慢，set把數值映射到key上都要做hash計算。不要小瞧這個耗時，在資料量大的情況，差距是很明顯的。但是此題不容易使用數組，使用set。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//傳回交集，數組元素唯一，因為0 <= nums1[i], nums2[i] <= 1000，若使用數組記錄，并沒有一個确切數字說明是交集
//不可重複
unordered_set<int> set;
for(auto a:nums1)
{
    for(auto b:nums2)
    {
        if(a==b)
            set.emplace(b);//隻利用了set資料不能重複特點
    }
}
return {set.begin(),set.end()};
    }
};

3. 202題. 快樂數

https://leetcode-cn.com/problems/happy-number/

編寫一個算法來判斷一個數 n 是不是快樂數。

「快樂數」定義為：對于一個正整數，每一次将該數替換為它每個位置上的數字的平方和，然後重複這個過程直到這個數變為 1，也可能是無限循環但始終變不到 1。如果可以變為 1，那麼這個數就是快樂數。

如果 n 是快樂數就傳回 True ；不是，則傳回 False 。

示例：

輸入：19

輸出：true

解釋：

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

題幹中有着關鍵字眼，即在求和過程中，平方和可能會無限循環,當出現了判斷一個數值是否出現在一個集合中時，此時就要考慮使用哈希法了

class Solution {
public:
//傳回每一次位置上的平方和
    int single(int n)
    { int single=0;
     while(n)
        {
        single+=(n%10)*(n%10);//得到最後一位的數字
        n=n/10;
        }
        return single;
    }
    //注意為無限循環，即将每一次的平方和放入集合set中，若查找能夠找到的話，即進入了無限循環，傳回false
    bool isHappy(int n) {
        unordered_set<int> set;
        while(n!=1)
        {
            n=single(n);

            if(set.find(n)!=set.end())
                return false;
            set.emplace(n);
        }
return true;
    }
};

4.1002. 查找常用字元

https://leetcode-cn.com/problems/find-common-characters/

給定僅有小寫字母組成的字元串數組 A，傳回清單中的每個字元串中都顯示的全部字元（包括重複字元）組成的清單。例如，如果一個字元在每個字元串中出現 3 次，但不是 4 次，則需要在最終答案中包含該字元 3 次。

你可以按任意順序傳回答案。

【示例一】

輸入：[“bella”,“label”,“roller”]

輸出：[“e”,“l”,“l”]

【示例二】

輸入：[“cool”,“lock”,“cook”]

輸出：[“c”,“o”]

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
int a[26]={0};
int b[26]={0};
vector<string> v;
    for(int j=0;j<words[0].size();j++)
        a[words[0][j]-'a']++;//記錄下第一個的字母出現情況
    for(int i=1;i<words.size();i++)
    {
       memset(b,0,sizeof(b));
        for(int k=0;k<words[i].size();k++)//一個單詞結束
            b[words[i][k]-'a']++;
        for(int z=0;z<26;z++)
         a[z]=min(a[z],b[z]);
    }

    for(int x=0;x<26;x++)
    {
        while(a[x]>0)
        {
        string s(1,'a'+x);
        v.push_back(s);
        a[x]--;
        }
    }
return v;
    }
};

5. 1.兩數之和

https://leetcode-cn.com/problems/two-sum/

給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那兩個整數，并傳回他們的數組下标。

你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素不能使用兩遍。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

是以傳回 [0, 1]

本題中使用了key

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++)
        {
            auto it=map.find(target-nums[i]);
            if(it!=map.end())
                return {i,it->second};
            map.emplace(make_pair(nums[i],i));
        }
        return {};
}
};

6.第454題.四數相加II **

https://leetcode-cn.com/problems/4sum-ii/

給定四個包含整數的數組清單 A , B , C , D ,計算有多少個元組 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

為了使問題簡單化，所有的 A, B, C, D 具有相同的長度 N，且 0 ≤ N ≤ 500 。所有整數的範圍在 -2^28 到 2^28 - 1 之間，最終結果不會超過 2^31 - 1 。

例如:

輸入:

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

輸出:

解釋:

兩個元組如下:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

//此題一開始想用set容器寫,但是題中用到了三重循環，時間複雜度過高。想到了利用Map容器，key存放值，value存放出現次數
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) 
{   
    int count=0;
    unordered_multiset<int> set;
    //nums1和nums2與nums3，nums4相反
    for(auto i : nums1)
        for(auto j : nums2)
            set.emplace(i+j);//i和j的和插入
    for(auto k:nums3)
    {   
        for(auto l:nums4)
        {
            for(auto a:set)
            {
                if(a==-(k+l))
                    count++;
            }
        }
    }
    return count;
}
};

class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) 
{   
    int count=0;
   unordered_map<int,int> map={};
    //nums1和nums2與nums3，nums4相反
    for(auto i : nums1)
        for(auto j : nums2)
            map[i+j]++;//i和j的和插入
    for(auto k:nums3)
    {   
        for(auto l:nums4)
        {
            auto it=map.find(-(k+l));
            if(it!=map.end())
            count+=it->second;
        }
    }
    return count;
}
};

7.383. 贖金信

https://leetcode-cn.com/problems/ransom-note/

給定一個贖金信 (ransom) 字元串和一個雜志(magazine)字元串，判斷第一個字元串 ransom 能不能由第二個字元串 magazines 裡面的字元構成。如果可以構成，傳回 true ；否則傳回 false。

(題目說明：為了不暴露贖金信字迹，要從雜志上搜尋各個需要的字母，組成單詞來表達意思。雜志字元串中的每個字元隻能在贖金信字元串中使用一次。)

注意：

你可以假設兩個字元串均隻含有小寫字母。

canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”) -> true

//此題比較簡單，如若a字元串能夠讓b字元串組成，那樣a的所有字元都會與b相等或是更少。
//1.可以用數組做，英文字母為有限個
//2.可以用Map映射做，key存放英文字母，value存放出現次數做差
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
    //     int a[26]={0};//數組存放
    //     for(int i=0;i!=magazine.size();i++)
    //        a[magazine[i]-'a']++;
    //     for(int j=0;j!=ransomNote.size();j++)
    //         a[ransomNote[j]-'a']--;
    //     for(int k=0;k!=26;k++)
    //     {
    //         if(a[k]<0)
    //         return false;
    //     }   
    // return true;

//利用map
unordered_map<int,int> map1;

for(auto it=magazine.begin();it!=magazine.end();it++)
  map1[*it-'a']++;
for(auto it1=ransomNote.begin();it1!=ransomNote.end();it1++)
    map1[*it1-'a']--;
for(auto it2=map1.begin();it2!=map1.end();it2++)
    if(it2->second<0)
     return false;
return true;
    }
};

8.第15題. 三數之和 ***

https://leetcode-cn.com/problems/3sum/

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重複的三元組。

注意：答案中不可以包含重複的三元組。

示例：

給定數組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：[ [-1, 0, 1], [-1, -1, 2] ]

//此題運用雙指針法，若使用哈希法會有很多邊界問題
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> v;
        sort(nums.begin(),nums.end());//升序排序
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]>0)
             return v;
            if(i>0 && nums[i]==nums[i-1])//a去重
                continue;
            //不等
            int left = i+1 ;
            int right=nums.size()-1;
            while(right>left)
            {
                if(nums[i]+nums[left]+nums[right]>0)
                    right--;
                else if(nums[i]+nums[left]+nums[right]<0)
                    left++;
                else{
                    v.push_back({nums[i],nums[left],nums[right]});
                while(left<right && nums[left]== nums[left+1])
                    left++;
                while(right>left && nums[right]==nums[right-1])
                    right--;
                left++;
                }
            }
        }
        return v;
    //哈希法
    }
};

哈希表（Hash table）篇哈希表篇

1.首先将數組排序，這很關鍵，i從下标為0處開始，left從i的後一個數開始，right從數組最後一個數開始
2.假設nums[i]+nums[left]+nums[right]>0,此時數組為從小到大排序，是以整體數字太大，可以将right數向前移動，若nums[i]+nums[left]+nums[right]<0，移動Left位置。
四數之和也是相同做法。

總結

首先，一般來說用到set容器的時候，可能是單純判斷資料是否重複出現的問題。當使用map容器時，大多都是有記錄資料出現的次數的問題，此類問題有時也可以用數組形式的哈希表完成。

最後的三數之和與之前的四數相加解法不同的主要原因在于此題需要寫出元組的數值，而四數相加隻需要記錄次數就行。并且對于雙指針法來說，首先将資料進行排序非常重要。

哈希表（Hash table）篇哈希表篇

哈希表篇

文章目錄

1.哈希表簡述

1.1哈希表

1.2哈希函數

1.3哈希沖突

1.3.1開放位址法

1.3.2鍊位址法

1.3.3常見的三種哈希結構

2. 242.有效的字母異位詞

3. 349. 兩個數組的交集

3. 202題. 快樂數

4.1002. 查找常用字元

5. 1.兩數之和

6.第454題.四數相加II **

7.383. 贖金信

8.第15題. 三數之和 ***

總結

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器