Landy Blog
0%

資料結構- Hash Table - hash Method

發表於 更新於 分類於 ，
紀錄 Hash Table 的 Hash 方法功能與如何實作

Hash Method 在幹嘛?

這個單元在介紹 怎麼將傳入的 key 值透過 hash 方法，來產出一個 hash 結果，
這個結果會是一個數值，代表這個 node 被儲存在 Hash Table 的第幾個 buckets(i.e. 若 hash 的結果是 5 ，則代表它會被儲存在 buckets[5] 這個 bucket 裡)。

實作 Code

1
2
3
4
5
6
7
8
9
10
11
12
13
//...

HashTable.prototype.hash = function(key) {
  let total = 0;
  for(let i = 0; i < key.length; i++) {
    total += key.charCodeAt(i);
  }
  const bucketIndex = total % this.numBuckets;
  return bucketIndex;
}

const myHT = new HashTable(30);
console.log(myHT.hash('Becca')); // 12

這邊來解釋一下 hash 這個方法的裡面在幹些什麼 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
HashTable.prototype.hash = function(key) {
  let total = 0;
  for(let i = 0; i < key.length; i++) {
    // charCodeAt 會回傳以 UTF-16 編碼後的結果。
    // 並將每一次 charCodeAt 編碼後的結果疊加到 total。
    // 這樣疊加的方式，純粹就是這個範例決定以這種方式當作這個 Hash Table 的 hash 規則，有點像是加密的感覺，而 hash 的方式有 n 種，這個範例就選這種方式來 hash
    total += key.charCodeAt(i); 
  }
  // 要用 % 來對 numBuckets 取餘數的原因是，
  // 經過上面疊加過後的 total 結果要落在 0 - (this.buckets.length - 1) 區間內，
  // 不然，來個超出陣列的範圍是要怎麼存進去 🙃
  const bucketIndex = total % this.numBuckets;

  // 回傳取完餘數的結果，它就代表了當前這個 node 被儲存在 Hash Table 的第幾個 bucket 裡
  return bucketIndex;
}

Take away

  • 知道了 hash 的過程發生了哪些事，是怎麼做到 hash 並且如何決定 key 要對應到 buckets 陣列的哪一個 index。