用 JavaScript 學習資料結構和演算法:字典(Dictionary)和雜湊表(Hash Table)篇


Posted by KD Chang on 2017-03-10

用 JavaScript 學習資料結構和演算法:字典(Dictionary)和雜湊表(Hash Table)篇

前言

在之前我們學習了一種不重複元素的集合,本文我們繼續討論另外一種不重複值的資料結構:字典(Dictionary)和雜湊表(Hash Table)。在集合中我們主要關心的是值本身 { 值(value): 值(value)},在字典(Dictionary)和雜湊表(Hash Table)則是有 { 鍵(key): 值(value)} 之間的 mapping 關係。

什麼是字典(Dictionary)?

用 JavaScript 學習資料結構和演算法:字典(Dictionary)和雜湊表(Hash Table)篇

  1. 建立字典類別
    與 Set 的情況類似,在 ES6 中也有原生的 Map 類別實作,因此本章我們也參考 ES6 的 Map 類別進行實作:

    function Dictionary() {
    let items = {};
    this.set = function(key, value) {};
    this.remove = function(key) {};
    this.has = function(key) {};
    this.get = function(key) {};
    this.clear = function() {};
    this.size = function() {};
    this.keys = function() {};
    this.values = function() {};
    }
    
    • has(key):判斷是 key 是否存在,這在 Dictionary 尤其重要
    this.has = function(key) {
    return key in items;
    // 也可以使用 return items.hasOwnProperty(key);
    }
    
    • set(key, value):新增一個鍵值
    this.set = function(key, value) {
    items[key] = value;
    };
    
    • remove():刪除一個鍵值
    this.remove = function() {
    if(this.has(key)) {
    delete items[key];
    return true;
    }
    return false;
    };
    
    • get():讀取一個值
    this.get = function() {
    // 先判斷是否存在鍵
    return this.has(key) ? items[key] : undefinded;
    };
    
    • values():回傳所有值
    this.values = function() {
    let values = {};
    for(let k in items) {
    if(this.has(k)) {
     values.push(items[k]);
    }
    }
    return values;
    };
    
    • clear():清除字典
    this.clear = function() {
    items = {};
    };
    
    • size():回傳字典長度
    1. 使用類似於 Linked List 的 length 變數計算法,當新增、刪除元素時順便增減長度
    this.size = function() {
    return length;
    }
    
    1. 使用 JavaScript 內建 Object 類別的內建函數 keys
    this.size = function() {
    return Object.keys(items).length;
    }
    
    1. 手動迭代判斷是否存在集合中並累加個數
    this.size = function() {
    let count = 0;
    // 特別注意在 JavaScript 中 for in 會一起把繼承於 Object 類別和物件自身的所有相關非相關資料結構的屬性一起迭代出來
    for(let prop in items) {
     // 判斷是否屬於 items 的屬性
     if(items.hasOwnProperty(prop)) {
      ++count;
     }
     return count;
    }
    }
    
    • keys():回傳字典擁有的鍵
    this.keys = function() {
    return Object.keys(items);
    }
    
    • getItems():回傳字典
    this.getItems() {
    return items;
    };
    
  2. 使用字典

    const dictionary = new Dictionary();
    // 新增鍵值
    dictionary.set('Mark', 'mark@gmail.com');
    dictionary.set('Ivy', 'ivy@gmail.com');
    dictionary.set('Mary', 'mary@gmail.com');
    
    console.log(dictionary.keys()); 
    console.log(dictionary.values()); 
    console.log(dictionary.get('Mark')); 
    dictionary.remove('Mark');
    console.log(dictionary.keys());
    

什麼是雜湊表(Hash Table)?

用 JavaScript 學習資料結構和演算法:字典(Dictionary)和雜湊表(Hash Table)篇

接下來我們將介紹 Hash Table,也可稱作 HashMap,是 Dictionary 類別中雜湊表的一種實作。實作的思路大概是:當要把資料放到雜湊表時,先給定一個 key 和存放的 value,並將 key 的每個字元轉換成 ASCII Code 或 Unicode Code 並相加,這個相加的值即是 hash 鍵值,在 table 陣列上對應到存放的 value。

  1. 建立雜湊表

    function HashTable() {
    let table = [];
    let getHashTableCode = function(key) {
    let hash = 0;
    for(let i = 0; i < key.length; i++) {
     // charCodeAt 會回傳指定字串內字元的 Unicode 編碼(可以包含中文字)
     hash += key.charCodeAt(i);
    }
    // 為了取到較小值,使用任意數做除法 mod 處理
    return hash % 37;
    }
    this.put = function(key, value) {
    // 根據 key 取出 Hash Function 產生的 position
    const position = getHashTableCode(key);
    // 對應 key 和 value
    table[position] = value;
    }
    this.get = function(key) {
    // 根據 key 取出 Hash Function 產生的 position
    const position = getHashTableCode(key);
    // 回傳值
    return table[position];
    }
    this.remove = function(key) {
    // 根據 key 取出 Hash Function 產生的 position
    const position = getHashTableCode(key);
    // 由於我們不能改變陣列長度(因為會影響到其它對應位置),所以將值給定 undefinded
    table[position] = undefinded;
    }
    }
    
  2. 使用雜湊表

    let hashTable = new HashTable();
    hashTable.put('Mark', 'mark@gmail.com');
    hashTable.put('Ivy', 'ivy@gmail.com');
    hashTable.put('Mary', 'mary@gmail.com');
    
    hashTable.get('Mark');
    hashTable.get('Jack');
    // 刪除鍵值為 Mark 資料
    hashTable.remove('Mark');
    hashTable.get('Mark');
    
  3. 處理雜湊表衝突

    在上面實作的過程中,聰明的讀者應該可以發現:雖然雜湊表方便好用,但有可能會有不同鍵值但有相同雜湊值的情況出現(例如:Jamie 和 Sue 的值 ASCII Code 相加就相同)。這種不同值卻在雜湊表對應相同位置的情況我們稱作衝突(collision),若不處理的話,後來的值會覆蓋掉之前的值。接下來我們會介紹三種方式來避免碰撞(collision)。

    • 分離鏈結:分離鏈結是在每一個 hash value 放置一個鏈結串列,當有 hash key 相同的值要放入時就新增進鏈結串列,是一個相對簡單的方式,但需要額外的鏈結串列空間。

    用 JavaScript 學習資料結構和演算法:字典(Dictionary)和雜湊表(Hash Table)篇

    更新過後的 HashTable:

    function LinkedList() {
    const Node = function(element) {
    this.element = element;
    this.next = null;
    }
    // 存放 LinkedList 長度
    let length = 0;
    // 第一個節點的指標
    let head = null;
    // 在尾部新增一個節點
    this.append = function(element) {};
    // 在特定位置新增一個元素節點
    this.insert = function(position, element) {};
    // 從串列中移除一個元素節點
    this.remove = function(element) {};
    // 從串列中移除一個特定的節點
    this.removeAt = function(position) {};
    // 回傳元素在串列的元素節點 index,若無則回傳 -1
    this.indexOf = function(element) {};
    // 判斷串列是否為空,是回傳 true,反之 false
    this.isEmpty = function() {};
    // 回傳串列元素個數
    this.size = function() {};
    // 由於 Node 是一個物件,所以運用 toString 方法將資料值輸出
    this.toString = function() {};
    // 列印出值
    this.print = function() {};
    }
    
    function HashTable() {
    let table = [];
    // 實作內部一個 ValuePair 類別,存原始 key、value
    let ValuePair = function(key, value) {
    this.key = key;
    this.value = value;
    }
    let getHashTableCode = function(key) {
    let hash = 0;
    for(let i = 0; i < key.length; i++) {
     // charCodeAt 會回傳指定字串內字元的 Unicode 編碼(可以包含中文字)
     hash += key.charCodeAt(i);
    }
    // 為了取到較小值,使用任意數做除法 mod 處理
    return hash % 37;   
    }
    this.put = function(key, value) {
    let position = getHashTableCode(key);
    // 若該位置沒有新增過元素,要先 init 一個 LinkedList 類別
    if(table[position] === undefinded) {
     table[position] = new LinkedList();
    }
    table[position].append(new ValuePair(key, value)); 
    } 
    this.get = function(key) {
    let position = getHashTableCode(key);
    if(table[position] !== undefinded) {
     let current = table[position].getHead();
     // 使用迴圈尋找在 LinkedList 中符合 key 的元素
     while(current.next) {
      if(current.element.key === key) {
       return current.element.value;
      } 
      current = current.next;
     }
     // 若是要找的是第一個或是最後一個節點的情況就不會進入 while 迴圈,要在這裡處理
     if(current.element.key === key) {
      return current.element.value;
     }
    } 
    return undefinded;
    }
    // 與一般雜湊表不同,我們要移除的是鏈結串列的元素
    this.remove = function(key) {
    let position = getHashTableCode(key);
    // 判斷該位置是否有元素
    if(table[position] !== undefinded) {
     let current = table[position].getHead();
     while(current.next) {
      // 當 key 相同時使用 LinkedList 的 remove 移除元素   
      if(current.element.key === key) {
       table[position].remove(current.element);
       // 若是整個位置的 LinkedList 為空則將該位置給定 undefinded
       if(table[position].isEmpty()) {
        table[position] = undefinded;
       }
       // 若成功移除則回傳 true
       return true;
      }
     }
     current = current.next;
    }
    // 若是要找的是第一個或是最後一個節點的情況就不會進入 while 迴圈,要在這裡處理
    if(current.element.key === key) {
     table[position].remove(current.element);
     if(table[position].isEmpty()) { 
      table[position] = undefinded;
     }
    }
    }
    return false;
    }
    
    • 線性探查:是另外一種解決雜湊表,若是欲加入 Hash Table 位置已經被佔據則往下一個 index + 1 去填,若還是被佔據則考慮 index + 2,以此類推。

    用 JavaScript 學習資料結構和演算法:字典(Dictionary)和雜湊表(Hash Table)篇

    更新過後的 HashTable:

    function HashTable() {
    let table = [];
    // 實作內部一個 ValuePair 類別,存原始 key、value  
    let ValuePair = function(key, value) {
    this.key = key;
    this.value = value;
    }
    let getHashTableCode = function(key) {
    let hash = 0;
    for(let i = 0; i < key.length; i++) {
     // charCodeAt 會回傳指定字串內字元的 Unicode 編碼(可以包含中文字)
     hash += key.charCodeAt(i);
    }
    // 為了取到較小值,使用任意數做除法 mod 處理
    return hash % 37;   
    }
    // 由於 JavaScript 陣列可動態增加長度,所以不用擔心長度不夠問題
    this.put = function(key, value) {
    let position = getHashTableCode(key);
    // 若是位置沒被佔據直接 new 一個 ValuePair,若有則考慮下一個 index
    if(table[position] === undefinded) {
     table[position] = new ValuePair(key, value);
    } else {
     let index = ++position;
     while(table[index] !== undefinded) {
      index++;
     }
     table[index] = new ValuePair(key, value);
    }
    }
    this.get = function(key) {
    let position = getHashTableCode(key);
    // 先確認鍵值是否存在
    if(table[position] !== undefinded) {
     // 開始比對,沒有就下一個
     if(table[position].key === key) {
      return table[position].value;
     } else {
      let index = ++position;
      while(table[index] === undefinded || table[index].key !== key) {
       index++;
      }
      if(table[index].key === key) {
       return table[index].value;
      }
     }
    }
    return undefinded;
    }
    this.remove = function(key) {
    let position = getHashTableCode(key);
    // 先確認鍵值是否存在
    if(table[position] !== undefinded) {
     // 開始比對,沒有就下一個
     if(table[position].key === key) {
      table[index] = undefinded;
     } else {
      let index = ++position;
      while(table[index] === undefinded || table[index].key !== key) {
       index++;
      }
      if(table[index].key === key) {
       table[index] = undefinded;
      }
     }
    }
    return undefinded;
    }
    }
    
    • 更好的雜湊表(Hash Function):俗話說預防勝於治療,若是能使用更好的 Hash Function 就能預先避免衝突(collision)的可能(擁有較低插入和檢索元素的時間、較低衝突的可能意味著更好的雜湊表)。
    // djb2HashCode 實作
    let djb2HashCode = function(key) {
    // 初始化 hash 值,大部分實作使用 5381
    let hash = 5381;
    for(let i = 0; i < key.length; i++) {
    // 根據經驗值給個魔術數字 33
    hash = hash * 33 + key.charCodeAt(i);
    }
    // 1013 為隨機質數
    return hash % 1013;
    }
    

總結

在這個單元中我們學到了:

  1. 什麼是字典(Dictionary)?如何使用?
  2. 什麼是雜湊表(Hash Table)?如何實作?
  3. 處理雜湊表衝突

延伸閱讀

  1. 字符编码笔记:ASCII,Unicode和UTF-8

(image via algolistmcgillmindcrackerinchwscecilsunkure

關於作者:
@kdchang 文藝型開發者,夢想是做出人們想用的產品和辦一所心目中理想的學校。A Starter & Maker. JavaScript, Python & Arduino/Android lover.:)


#javascript #ECMAScript2015 #ES6 #data structure #algorithm #Dictionary #Hash Table #資料結構 #演算法 #陣列 #雜湊表 #字典









Related Posts

[ 前端工具 ] - Webpack

[ 前端工具 ] - Webpack

網路的本質其實沒有你想的那麼難

網路的本質其實沒有你想的那麼難

Git 版本控制入門(2)- branch

Git 版本控制入門(2)- branch


Sponsored



Newsletter




Comments