認識 Hash Table

什麼是雜湊表 Hash Table

Hash Table 是一種儲存 {key: value} 的資料結構，如下圖所示，key 會被丟到 Hash Function 中計算，而計算結果 Hash Value 為 {key: value} 在 Hash table 中的 index 值。有了 key 就像擁有浪漫因子，馬上就能找到專屬於你的 value，但存取資料的速度快是利用空間換來的，也因此 Hash Table 較占用記憶體空間。

Array v.s. Hash Table

Array 是有順序性的，並可以利用 index 來找到 value，但 Hash Table 並沒有順序性，是利用 key 來找到 value。
這邊利用 leetcode 經典中的經典 Two Sum 來解釋 Array 和 Hash Table 的差異。假設一陣列 nums = [2, 7, 11, 15] , target = 9，要找出兩數字和等於 target，第一個最暴力解法就是用雙層迴圈來檢查是否有等於 target 的組合，程式碼如下 :

var twoSum = function(nums, target) {   
    for(i=0;i<nums.length;i++) {
        for(j=i+1;j<nums.length;j++) {
            if(nums[i] + nums[j] === target) {
                return [i,j]
            }
        }
    } 
};

雖然可以找到答案，但時間複雜度是很可憐的O(n)*O(n) = O(n²)，因此來試試看 Hash Table 的方法，程式碼如下 :

var twoSum = function(nums, target) {
    let map = {};
    for(let i=0; i<nums.length; i++){
        let num1 = nums[i];
        let num2 = target - num1;
        if(map[num2] >= 0)
            return [map[num2], i]
        map[num1] = i;
    }
};

當找到 7 時就能發現與 target 的差值已經存在 Hash Table 裡，便能回傳答案，這樣時間複雜度就是 O(n) 了，跟 Array 的 O(n²) 相比是快上許多。

時間複雜度

因為 hash function 的神秘力量，我們可以透過 key 很快地找到 value，不管有幾組 {key: value} ，在最佳狀況下只需要一次即可找到 value，其時間複雜度為 O(1)，但在最差狀況下則和 array 相同，需遍歷所有元素才能找到 value，因此時間複雜度為 O(n)。

Hash Table 應用

需要快速查詢資料的時候適用，下面找了兩題可以用 Hash Table 來解的 leetcode 題目 :

1. 1. Two Sum

var twoSum = function(nums, target) {
        let map = {};
        for(let i=0; i<nums.length; i++){
            let num1 = nums[i];
            let num2 = target — num1;
            if(map[num2] >= 0)
                return [map[num2], i]
            map[num1] = i;
        }
};

2. 287. Find the Duplicate Number

var findDuplicate = function(nums) {
    let map = {}
    for(let i=0; i<nums.length; i++){
        if(map[nums[i]])
            return nums[i];
        map[nums[i]] = 1; 
    }
};