refactor 的部分在幹嘛?
最主要就是判斷傳入 insert function 的 key 值是否已存在 Hash Table 裡，
若有，就將傳入的值覆蓋掉那個 key 值所對應的 node 的值。
若沒有，就新增一個 node 到其所對應的 bucket 裡。
refactor 程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| //...
HashTable.prototype.insert = function(key, value) {
const index = this.hash(key);
if(!this.buckets[index]) this.buckets[index] = new HashNode(key, value);
else if(this.buckets[index].key === key) this.buckets[index].value = value;
else {
let currentNode = this.buckets[index];
while(currentNode.next) {
if(currentNode.next.key === key) {
currentNode.next.value = value;
return;
}
currentNode = currentNode.next;
}
currentNode.next = new HashTable(key, value);
}
}
|
這邊解析一下上面的程式碼在幹嘛
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
| // ...
HashTable.prototype.insert = function(key, value) {
const index = this.hash(key);
if(!this.buckets[index]) this.buckets[index] = new HashNode(key, value);
// 最主要是加了以下這個部分
// 如果此 bucket 的第一個元素的 key 等同於傳入的 key，那就更新這個元素的 value。
// 會需要為第一個元素單獨寫一個判斷是因為，後面的 while(currentNode.next) 的判斷，
// 永遠都在判斷 next 指向的元素，那就會漏掉第一個元素，因為沒有任何元素的 next 會指向第一個元素，
// 所以，才需要特別為第一個元素做判斷。
else if (this.buckets[index].key === key) {
this.buckets[index].value = value;
} else {
let currentNode = this.buckets[index];
while (currentNode.next) {
// 如果當前遍歷到的 node 的 next 指向的元素的 key 等同於傳入的 key，
// 那就更新 next 指向的元素的 value，並在更新完後，直接 return 結束遍歷。
if (currentNode.next.key === key) {
currentNode.next.value = value;
return;
}
currentNode = currentNode.next;
}
currentNode.next = new HashNode(key, value);
}
}
|
Take away
- 在 update 的時候要特別先判斷該 bucket 的第一個元素的 key 是否就已經符合傳入的 key 了，因為
while(currentNode.next) 永遠只會遍歷到下一個 node，不會遍歷到第一個 node，所以，才需要對第一個元素做判斷。
Reference Link