Landy Blog
0%

資料結構-HashTable-Wrap Up

發表於 分類於 ，
為 Hash Table 做個總結

Hash Table 具有哪些方法?

insert(update 的功能也包含在裡面),
get,
retrieveAll

time complexity

insert - O(1)

get - O(1)

這邊要特別說明一下，
如果在執行 insert 或者 get 有發生 key Collision(i.e. 已經存在有相同 key 了) 的話，
上面兩個方法都會降成 O(n)，因為變成要去遍歷儲存在該 bucket 的 LinkedList。

不然的話，如果 hash function 做的好的話，是不會發生 key Collision 的狀況，
也就是說每個 node 都儲存在其對應的獨一無二的 bucket 裡，自然上面兩個方法都會是 O(1) 囉。

cons

一般的 HashTable 不會儲存 node 的參照，不會像 LinkedList 和 Binary Search Tree 那樣每一個 node 都有儲存它前面指向哪一個 node，後面指向哪一個 node，可以透過當前這個 node 很方便的移動到其他的 node。

但是，以上這個缺點也不是沒辦法修就看你要不要加入這種功能到你的 HashTable 裡。

完整的 Source 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
66
67
68
69
70
71
72
73
74
75
76
77
78
function HashTable(size) {
  this.buckets = Array(size);
  this.numBuckets = this.buckets.length;
}

function HashNode = function(key, value, next) {
  this.key = key;
  this.value = value;
  this.next = next || null;
}

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;
}

Hash.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;
    return;
  }
  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 HashNode(key, value);
  }
}

HashTable.prototype.get = function(key) {
  const index = this.hash(key);
  if(!this.buckets[index]) return this.buckets[index].value;
  else {
    let currentNode = this.buckets[index];
    while(currentNode) {
      if(currentNode.key === key) return currentNode.value;
      currentNode = currentNode.next;
    }
    return null;
  }
}

HashTable.prototype.retrieveAll = function() {
  const allNodes = [];
  for(let i = 0; i < this.numBuckets; i++) {
    let currentNode = this.buckets[i];
    while(currentNode) {
      allNodes.push(currentNode);
      currentNode = currentNode.next;
    }
  }

  return allNodes;
}

const myHT = new HashTable(5);
myHT.insert('Dean', 'dean@gmail.com');
myHT.insert('Megan', 'megan@gmail.com');
myHT.insert('Dane', 'dane@gmail.com');
myHT.insert('Dean', 'dean@yahoo.com');
myHT.insert('John', 'john@gmail.com');
myHT.insert('Roger', 'roger@gmail.com');
console.log(myHT.buckets);
console.log(myHT.get('Dean'));
console.log(myHT.get('Megan'));
console.log(myHT.get('Randy'));
console.log(myHT.retrieveAll());