雜湊表，我需要那個酷東西

在線性資料結構中，若要找一個資料，花費的時間複雜度為O(n)，或是可以選擇節省時間，但是耗費記憶體容量。若是兩者都不想選，那就需要Hash Table這種資料結構，下面會來探討，到底什麼是雜湊表？

Hash Table

Hash這個詞在電腦科學中很常見，他是一種加密技術。例如密碼，當你創建密碼時，他會被加密過後才會存入後端資料庫，以免密碼被洩漏。不過今天我們先不談加密，而是談談Hash在做些什麼。簡單的說，Hash是將一組值轉換成另一組，那為什麼要怎麼做呢？最主要的是要保護資料，不過此處會著重在解釋如何轉換值。

圖片中可以看到，圈圈的部分是原本的值，透過Hash Function後存入到Hash Table中，假設每個圈圈都有一組屬於他們的ID，ID在Hash過後有可能兩組資料（兩個圈圈）被放入到Hash Table同一個位置中，此時產生的情況稱為Collision。

Hash Function

上面提到產生的衝突，不論使用何種的Hash Function都有可能會遇到，下列兩種是常見的使用方式：

1. Division Method
2. Multiplication Method

這兩種方法各有優缺點，可以根據需求來選擇。

Division Method

• 優點：速度非常快
• 缺點：要注意不能使用2的次方進行運算，非常容易出現衝突
• 公式：Index = Key mod m
  • Index為要放入Hash表的哪個位置
  • m為長度
  • key為元素

Multiplication Method

• 公式：Index = [m(keyA % 1)]
  • A是一個無理數
  • mod1時將整數去掉，就會得到0<P<1
  • P*m
  • math.floor()

#Python
x = hash("a")
print(x) #963309178111316638
y = hash(8823748)
print(y) #8823748
z = hash(str([1,2,3]))
print(z) #6529461775645613167

JavaScript的程式碼引用自上過課程老師分享的程式碼：

資料來源：Udemy-資料結構與演算法 (JavaScript)

class HashTable {
    // m = hashtable size
    constructor(size){
        this.size = size;
        this.table = [];
        for(let i = 0; i < this.size; i++){
            this.table.push([]);
        }
    }


    //division method
    //把一個值換成另一個值
    hash1(key){
        return key % this.size;
    }

    //mutiplication method
    hash2(key){
        let A = (Math.sqrt(5) - 1) / 2;
        return Math.floor(this.size * ((key * A) % 1));
    }

    set(key, value){
        let index = this.hash2(key);
        //this.table是一個array，才能做push
        this.table[index].push({key, value});
    }

    get(key){
        let index = this.hash2(key);
        for (let i = 0; i < this.table[index].length;i++){
            if (this.table[index][i].key == key){
                return this.table[index][i];
            }
        }
        // 找不到就回傳null
        return null;
    }

    printAll(){
        console.log(this.table);
    }
}

// m = 6
let myHashTable = new HashTable(6);
myHashTable.set(11424,"Mike");
myHashTable.set(62545,"James");
myHashTable.set(4171,"Drake");
myHashTable.set(554,"Keven");

// myHashTable.printAll();

// 尋找
console.log(myHashTable.get(4171));

Hash是一種不使用明文傳輸，減少資料被竊取的技術，延伸閱讀可參考密碼學，推薦Udemy的課程

https://www.udemy.com/course/cryptography-python/