Day9. 雜湊表(Hash Table)

15th鐵人賽

雜食性的貓

2023-09-24 20:15:05

249 瀏覽

分享至

資料結構

雜湊表，也有人會用音譯直接叫哈希表，Hash Map 也是在講同一個東西，主要用來儲存鍵與值(Key-Vale pair)，在 C# 中，我們一般使用 Dictionary<KeyType, ValeType> 這個型別來處理相關問題。

基本操作包含 Add()、Clear()、ContainsKey()、ContainsValue()、Remove() 跟直接用 Key 調出對應的 Value。
在 Dictionary 裡，所有 Key 皆不重複，如果要遍歷整個 Dictionary，可以這樣寫：

foreach(var key in dict.Keys()){
    Console.WriteLine(dict[key]);
    //Do what ever you want
}

透過 Keys 把全部的 Key 拿出後，一一遍歷，Key 就相當於陣列裡的索引，取值的寫法也是一樣。
Key 不能重複是硬性規定，如果該 Key 已經存在 Dictionary 中，仍執行 Add 操作，則會在執行到該行時噴出錯誤，說該鍵值已經在 Dictionary 中，Key 也不可為 Null。

Dictionary 的最大好處是在一般情況下，插入、刪除、使用鍵查找值的平均時間複雜度為 O(1) ，比如要記憶字串出現頻率，要用字串當鍵，出現頻率當值，Dictionary 就會是很合適的資料結構：每次只要輸入字串，就能有效率地獲得對應值。

相關演算法題目

##Valid Anagram
字母異位詞，這題很適合拿來做一個概念示範。
本身是個簡單的題目，給予兩個字串，要求判斷兩個字串是否由同樣數量的各個字母組成，無視位置差異。
陣列裡元素僅有小寫英文字母。
記住當要處理出現次數的時候，Dictionary 的(關鍵字，次數)的組合很合適。
比如我們做一個 dict，遍歷第一個字串，a 出現兩次，則總共變成 dict['a'] = 2，最後再遍歷另一個字串做字母數比對，就是答案。

那我們有其他的選擇嗎？
有 ─ 注意上面的粗體，當我們知道所有可能出現的元素的時候，且出現元素有機可循，陣列可以做到完全一樣的事情。
因為可能出現在字串中只有小寫英文字母，所以我們可以定義一個長度為 26 的陣列，index 0 的位置對應 a，index 25 的位置對應 z，在空間的使用上，相對 Dictionary 節省不少，可以用更輕量的方式來解決問題。
1.宣告一個長度為 26 的整數陣列
2.遍歷第一個字串，將該字母對應索引每次值加 1
3.遍歷第二個字串，將該字母對應索引每次值減 1
4.遍歷第一個整數陣列，任一數值不為零(兩個字串該字母出現次數不相等)，則回傳否，遍歷完沒有回傳否則回傳是

public class Solution {
    public bool IsAnagram(string s, string t) {
        var cnt = new int[26];
        foreach(var c in s){
            cnt[c-'a']++;
        }
        foreach(var c in t){
            cnt[c-'a']--;
        }
        foreach(var c in cnt){
            if(c != 0){
                return false;
            }
        }
        return true;
    }
}

這邊挑這題想要提醒的是，陣列其實某種意義上是和 Dict 相似的結構用法，只是索引值被限制在整數。在像這題索引值有明確連續可推斷關聯的時候，我們完全可以使用陣列來達到一樣的效果。

Two Sum

有在 Leetcode 上，想過要大量刷題的人，都會路過這個門口：Two Sum，Leetcode 上的編號 001。
題目是這樣的，給一個 int 陣列，以及一個 int 目標數，回傳兩個陣列中元素相加後正好為目標數的兩個索引，且陣列中只會剛好有一組元素滿足這件事，陣列中無重複元素。

最直覺的算法大概就是時間複雜度 O(n^2)，寫兩層迴圈遍歷陣列，直到兩個數相加為目標數，接著回傳索引。
那我們有沒有辦法用今天的算法來更有效率的解決這個問題呢？

有的，當我們造訪任意元素的時候，目標數減該元素即為我們預期找到的另一半(加起來等於目標數)，這時候，我們只要用 Dictionary 記住鍵為兩數相差，值為當前索引。往後遍歷的時候，每次先檢查當前的值有沒有在 Dictionary 內(這個操作是 O(1))，一旦找到值在 Dictionary 內，回傳當前的索引和當時記下的索引，就是答案了。
這樣一來我們透過空間多了一些資訊從而達到了降低時間複雜度的方法‧

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var dict = new Dictionary<int,int>();
        for(var i = 0; i < nums.Length; i++){
            if(dict.ContainsKey(nums[i])){
                return new int[]{
                    i, dict[nums[i]]
                };
            }
            if(!dict.ContainsKey((target - nums[i]))){
                dict.Add(target - nums[i],i);
            }
        }
        return null;
    }
}

4Sum II

看完 Two Sum，我們接著來看一題 4Sum，但不是本來的 4Sum。
題目是這樣的，給總共四個陣列，陣列長度都一樣為 n，回傳從四個陣列中各取一個數相加為零的組合數量(如取出 -1, 1, 0, 0 ，四數相加為 0)，陣列本身可能重複，但最後回傳的組合並不用處理重複的 Case，所以直接算就好。
暴力解就是四層迴圈遍歷做加總，然後數數看有幾組。
這邊用和 Two Sum 相似的辦法，我們可以降低時間複雜度到 O(n^2)。
步驟如下

把前兩個陣列做雙層迴圈的遍歷，用一個 dict 去存下(0 - 任意兩數相加, 出現次數)的(Key, Value) Pair
把後兩個陣列做雙層迴圈的遍歷，檢查取出兩數相加後的 Key 是否存在 dict 裡
存在則把最後回傳的 count 加上 Value 的值，也就是前面兩個陣列加總完數字的出現次數
回傳 count，結束

public class Solution {
    public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        var dict = new Dictionary<int,int>();
        var count = 0;
        var sum = 0;
        for(var i = 0; i < nums1.Length; i++){
            for(var j = 0; j < nums2.Length; j++){
                sum = nums1[i]+nums2[j];
                if(!dict.ContainsKey(sum)){
                    dict.Add(sum,0);
                }
                dict[sum]++;
            }
        }
        for(var i = 0; i < nums3.Length; i++){
            for(var j = 0; j < nums4.Length; j++){
                sum = 0-(nums3[i]+nums4[j]); 
                if(dict.ContainsKey(sum)){
                    count += dict[sum];
                }
            }
        }
        return count;
    }
}

可以看到在不用去除重複的情況下，用組合次數與組合的鍵值配對，能夠幫助我們極大程度的降低時間複雜度，算是一個組合加上 Dictionary 的運用，看過一次應該就會有印象的操作方式。

關於 Dictionary 的操作簡單挑了幾題，我想能把這個資料結構的操作概念大致傳達到了。基本上 Dictionary 做的事情就是用空間換取時間，當組合有限的時候，或是組合會重複出現的時候，Dictionary 能幫助我們記憶過往瀏覽過的組合，不用每次重新遍歷，節省遍歷的資源，組合 - 出現次數、組合 - 可能關聯組合，像這種鍵值配對，都可以想到 Dictionary 上頭。