凹逗工程師

成為一個更好的人

0%

『 資料結構 』字典和雜湊表 Dictionary and HashMap

發表於 更新於

前言

JavaScript 中的字典和雜湊表是非常有用的資料結構，可以用來快速查找鍵值對應的值。在 JavaScript 中，字典通常是用物件來實現，而雜湊表則可以使用 Map 來實現。這些資料結構非常常見，因此學習如何使用它們是很重要的。

順道提一下，集合(Set) [值：值]所關注的是值的本體，而字典(Dictionary)、雜湊表(HashMap) [鍵：值]關注的是兩者的 Mapping 關聯，這樣就可以簡單區分開來了。

在本篇文章中，我們將介紹如何在 JavaScript 中使用字典和雜湊表。我們將會討論它們的特性、如何使用它們來解決問題，以及它們的複雜度和效能。如果你對 JavaScript 的資料結構和算法感到興趣，這篇文章將會對你有所幫助。

字典 Dictionary

想必大家都已經知道，集合代表的是一組互不重複的元素。在字典中，儲存的是「鍵：值」，鍵名用來查詢特定元素。
也稱作映射。

方法

  • set(key, value): 添加新的元素。
  • remove(key): 移除對應鍵值的元素。
  • has(key): 如果該鍵值存在此字典中，則回傳 true; 反之，回傳 false。
  • get(key): 利用鍵值尋找特定數值並回傳。
  • clear(): 清空此字典的所有元素。
  • size(): 返回字典所含的元素數量。
  • keys(): 回傳一個陣列，包含所有鍵。
  • values(): 回傳一個陣列，包含所有值。

實作

這次實作的類別是以 ECMAScript 6 中的 Map 做基礎。會明顯的發現和 Set 類別雷同。

骨架

1
2
3
function Dictionary(){
  var items = {};
}

has, set

第一步先建立 has, set 方法，而這邊會要先做 has()，是因為它會被 set, remove 其他的方法呼叫。
而 set(key, value)，可以用來添加一個新的值，或是將原有的值做更新。

1
2
3
4
5
6
7
this.has = function(key){
  return key in items;
}

this.set = function(key, value){
  items[key] = value;
}

remove

1
2
3
4
5
6
7
this.remove = function(key){
  if (this.has(key)){
    delete items[key];
    return true;
  }
  return false;
}

get, values

如果想要在字典搜尋特定的一個元素，就可以使用 get 和 values。
values() 不能僅僅使用 for-in 遍歷整個 items 物件的屬性，還需要使用 has() 驗證是否包含該屬性。 因為物件的原型會含其它屬性在裡面( Js 基本的物件屬性是會被繼承的，並會存在當前的物件中 )

1
2
3
4
5
6
7
8
9
10
11
12
13
this.get = function(key){
  return this.has(key) ? items[key] : undefined;
}

this.values = function(){
  var values = [];
  for (let k in items){
    if(this.has(k)){
      values.push(k);
    }
  }
  return values;
}

clear, size, keys, getItems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
this.clear = function(){
  items = {};
}

this.size = function(){
  return Object.keys(items).length;
}

this.keys = function(){
  return Object.keys(items);
}

this.getItems = function(){
  return items;
}

使用 Dictionary 類別 (郵件通訊錄)

1
2
3
4
5
6
7
8
9
10
var dictionary = new Dictionary();
dictionary.set('Colin', 'colin1225@email.com')
dictionary.set('Jake', 'jake0305@email.com')
dictionary.set('Rick', 'rick1010@email.com')

console.log(dictionary.has('Colin')) // true
console.log(dictionary.size()) // 3
console.log(dictionary.keys()) // ["Colin", "Jake", "Rick"]
console.log(dictionary.values()) // ['colin1225@email.com', 'jake0305@email.com', 'rick1010@email.com']
console.log(dictionary.get('Rick')) // 'rick1010@email.com'

雜湊表 HashMap

HashTable 也稱作 HashMap，是 Dictionary 類別的一種實作方式。
使用雜湊演算法是為了更快更精準的在資料中找到一個值。以往我們要在資料結構中獲得一個值，要經過遍歷整個資料集。
雜湊讓我們利用函數就能得到資料的具體位置，因而達到快速檢索的效果。

HashMap

方法

  • 雜湊函數: 給定一個鍵值，返回值在表中的地址。
  • put(key, value): 向雜湊表增加一個新資料。
  • remove(key): 根據鍵值從表中移除值。
  • get(key): 根據鍵值檢索特定值，返回。

實作

雜湊函數

順序第一位為雜湊函式，是 HashTable 中一個私有的函數。
這邊使用一個最常見的 – 「雙輸」(lose lose)，將每一個鍵值中的每個字母的 ASCII 值相加。
在函式的最後常會使用 hash 值和任意數做除法的餘數(mod)。

1
2
3
4
5
6
7
var loseloseHashCode = function(key){
  var hash = 0;
  for (let i=0; i<key.length; i++){
    hash += key.charCodeAt(i);
  }
  return hash % 37;
}

put

1
2
3
4
5
this.put = function(key, value){
  var position = loseloseHashCode(key);
  console.log(position + '-' + key);
  table[position] = value;
}

get

使用雜湊函式求出 key 值所對應位置，並回傳 position。

1
2
3
this.get = function(key){
  return table[loseloseHashCode(key)];
}

remove

1
2
3
this.remove = function(key){
  table[loseloseHashCode(key)] = undefined;
}

使用 HashTable 類別

1
2
3
4
5
6
7
8
9
var hash = new HashTable()
hash.put('Colin', 'colin1225@email.com')
hash.put('Jake', 'jake0305@email.com')
hash.put('Rick', 'rick1010@email.com')
/* Output
  20 - Colin
  9 - Jake
  23 - Rick
*/

使用 get()

1
2
3
4
5
6
console.log(hash.get('Colin'));
console.log(hash.get('Eileen'));
/* Output
  colin1225@eamil.com
  undefined
*/

由於 Colin 是存在表中的鍵，所以會返回它的值。但 Eileen 並不在裡面，當我們試著取出值時，回傳將為 undefined（不存在）。
如果對 Colin 執行 remove()，那理所當然也會 return undefined。

1
2
3
4
5
hash.remove('Colin');
console.log(hash.get('Colin'));
/* Output
  undefined
*/

雜湊集合

接著，我們來說明一下『雜湊集合』這個專有名詞。
在某些程式語言中，你會發現有這樣的一個實作。我們可以從名稱中了解到這是由集合所構成，但是新增、插入、刪除，是使用雜湊函數。
與剛才我們的實作不同之處，不添加「鍵值對」，只插入值。例如存放水果種類，但不賦予它們定義。

雜湊表的衝突

有時候，會遇到有相同雜湊值的情況。不同的值在表中相同的位置，稱之為衝突。
在正常程式執行的情況下，最後添加的值將會佔據該位置，也就是會覆蓋掉。
當然，我們的目的就是要將所有的資料存放進來，這樣的話不就達不到初衷了嗎？

面對衝突的處理

在遇到衝突時，有兩個方法：

  1. Separate Chaining
  2. Linear Probing

Separate Chaining

  • 一個(Key)位置允許放入多個值
  • 每一個位置(Point)都指向一個 Linked List，以存放多個值
  • 如果一個位置沒有放置任一值，Pointer 會被視為 null

此圖片源自網路

Linear Probing

  • 如果該 key 對應的位置已經佔用（衝突），則會存入下一個 point(index+1)。
  • can provide high performance because of its good locality of reference
  • 需要注意的地方就是陣列的空間有機會被使用完。

來自wiki

歡迎關注我的其它發布渠道