Landy Blog
0%

資料結構- Hash Table - Insert Method

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

Insert Method 在幹嘛?

將愈加入的新的 node 的 key 值，經過 hash 之後，得知這個 node 要被塞入 Hash Table 的哪一個 bucket 裡，並將其塞入，完成在 Hash Table 新增新 node 的效果。

實作 Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// ...

HashTable.prototype.insert = function(key, value) {
  const index = this.hash(key);
  if(!this.buckets[index]) {
    this.buckets[index] = new HahsNode(key, value);
  }
  else {
    let currentNode = this.buckets[index];
    while(currentNode.next) {
      currentNode = currentNode.next;
    }
    currentNode.next = new HashNode(key, value);
  }
}

const myHT = new HashTable(30);
myHT.insert('Dean', 'dean@gmail.com');
myHT.insert('Megan', 'megan@gmail.com');
myHT.insert('Dane', 'dane@gmail.com');
console.log(myHT.buckets);
// [
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   {
//       "key": "Megan",
//       "value": "megan@gmail.com",
//       "next": null
//   },
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   {
//       "key": "Dean",
//       "value": "dean@gmail.com",
//       "next": {
//           "key": "Dane",
//           "value": "dane@gmail.com",
//           "next": null
//       }
//   },
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null,
//   null
// ]

以下來解析一下 insert 裡面在幹嘛

1
2
3
4
5
6
7
8
9
10
11
HashTable.prototype.insert = function(key, value) {
  const index = this.hash(key); // 將欲加入元素的 key 值丟進 hash method 以得知此元素要被塞入哪一個 bucket 裡
  if(!this.buckets[index]) this.buckets[index] = new HashNode(key, value); // 如果這個 bucket 裡面還沒有任何元素，則創建一個新的 node，並塞入這個 bucket 裡
  else {
    let currentNode = this.buckets[index]; // 先取得 bucket 的第一個 node
    while(currentNode.next) { // 持續遍歷，直到當前被遍歷到的 node 的 next 為 null，則代表已經遍歷到此 bucket 的最後一個 node 了
      currentNode = currentNode.next; 
    }
    currentNode.next = new HashNode(key, value); // 此時 currentNode 是 bucket 的最後一個 node，接著，就將這個 node 的 next 指向新的 node，就完成將新 node 加入 bucket 的動作了
  }
}

Take away

  • 先透過取得欲加入元素的 hash 結果，來判斷此元素要被加入倒哪一個 bucket 裡，
    接著，再遍歷要被加入的 buckets 裡的 list ，並將新的元素塞入這個 list 的最後一個元素，就完成 insert 的功能。