iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 8

Day8: [資料結構]Hash Table - 雜湊表

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210908/201286046kIO7mJLHA.jpg
在理解hash table之前,先來理解hash(雜湊)吧!

雜湊的特色有以下幾點:

  1. 無論原本的內容長短,經過雜湊演算法處理過的值都會是固定長度
  2. 經由雜湊處理過的資料無法反推出原本的輸入為何
  3. 兩個輸入的內容即使只差一個字, 算出來的結果會會相差非常多
  4. 常用的雜湊演算法有MD5和SHA ,後者的安全性更高

生活中的例子

  1. 保存用戶密碼
    假如小明在A網站的登入密碼是12345 ,存在後端資料庫的密碼通常會經過雜湊處理,不會大喇喇地把明碼12345存進去,因此就算駭客侵入資料庫, 也無法推測出原本的密碼是多少,確保資料安全性,所以如果有天你在某個網站點了忘記密碼,就會把原密碼原封不動寄到信箱裡的話 ,那就要特別小心了,那個網站可能會有資安疑慮。

  2. 檔案驗證
    假如我們打開終端機輸入md5 檔名 ,就會發現生成一組雜湊值,可以用來驗證兩個檔案是否一樣
    https://ithelp.ithome.com.tw/upload/images/20210908/20128604IJPX6UxqRa.jpg

什麼?雜湊不等於加密嗎?

  • 加密需要有一把鑰匙, 透過鑰匙才能解密回推取得原本的內容 
  • 雜湊不需要鑰匙 ,無且無法回推原本的內容是甚麼

Hash Table

Hash table中文叫作雜湊表,又被稱為關聯式陣列,是根據key來查詢資料存在哪個記憶體位置的資料結構,而這個key是透過hash function(雜湊函數)計算出來的,搜尋速度為O(1)。

buckets是儲存資料的格子
https://ithelp.ithome.com.tw/upload/images/20210908/20128604AOWZ1bGswC.png
圖片來源:https://en.wikipedia.org/wiki/Hash_table

HashMap Collision

經過hash function 算出一個索引值,但可能會發生兩組資料算出來的索引值為重複的情形,這就是HashMap Collision(碰撞),假如真的發生碰撞的話,就把碰撞的值放到同一個陣列裡或者是用linked list解決碰撞的問題,以下圖為例, Danny和Ella的id經過hash funciton計算後的索引值都是4,就會發生碰撞,所以這個時候我們可以設計成每個儲存格都是一個陣列,這樣的話遇到碰撞的值還是可以存放在同一個索引值底下。

用js實作hash table

hash1的function為Division Method,公式為index = key mod size, 簡單來說就是key(id)取size(6)的餘數
hash2的function為Multiplication Method,公式為A =(√5–1)/2 , index = [m(keyA%1)],相信這邊應該已經蠻多人眼神死了,想要瞭解完整的公式解釋可以google Multiplication Method

在無法預先得知「Key的範圍」以及「在該範圍內Key的分佈情形」之下,使Multiplication Method會比較好,所以採取hash2來做雜湊處理

class HashTable {
    constructor(size) {
        this.size = size;
        this.table = [];
        for (let i = 0; i < this.size; i++) {
            this.table.push([]);
        }
    }
    hash1(key) {
        return key % this.size;
    }

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

    set(key, value) {
        let index = this.hash2(key);
        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) {
                return this.table[index][i];
            }
        }
    }
    printAll() {
        console.log(this.table);
    }
}

let myHashTable = new HashTable(6);
myHashTable.set("89893", "Hank");
myHashTable.set("12343", "Sally");
myHashTable.set("72324", "Danny");
myHashTable.set("28990", "Ella");
myHashTable.set("324323", "Wason");

myHashTable.printAll();

呼叫printAll 可以發現印出來的hash table雖然有發生碰撞的情況,但還是可以看到碰撞的兩個物件安然無恙的放在同一個索引值底下?

https://ithelp.ithome.com.tw/upload/images/20210908/20128604XdQqt9CzTE.png

參考資料:Hashing 基礎介紹


上一篇
Day7: [資料結構]Stack —堆疊和Queue— 佇列
下一篇
Day9:[資料結構] Linked-List - 鏈結串列
系列文
每日攝取一點資料結構和演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言