QUCwvkMX

1const sha256 = require('js-sha256');
2
3class KeyValuePair {
4  constructor(key, value) {
5    this.key = key;
6    this.value = value;
7    this.next = null;
8  }
9}
10class HashTable {
11  constructor(numBuckets = 4) {
12    this.count = 0;  //Number of elements in array
13    this.capacity = numBuckets; //How many items the table can hold
14    this.data = new Array(numBuckets) //Create array to hold values
15
16    //Fill array with null values
17    for(let i = 0; i < this.data.length; i++){
18      this.data[i] = null;
19    }
20  }
21
22  hash(key) {
23    let rawValue = sha256(key); //Generate sha256 hash for key
24    let firstEight = rawValue.slice(0,8) //Remove the first eight hex elements
25
26    let returnValue = parseInt(firstEight, 16); //Convert the hex elements into int
27    return returnValue; //Return int hash
28  }
29
30  hashMod(key) {
31    let returnValue = this.hash(key) % this.capacity; //Make sure the return index is in array
32    return returnValue;
33  }
34
35  insertNoCollisions(key, value) {
36    const index = this.hashMod(key); //Generate a key to place the value
37    let keyToAdd = new KeyValuePair(key,value);
38
39    //If the index already has an element, throw error, if not add it
40    if(this.data[index] !== null){
41      throw new Error("hash collision or same key/value pair already exists!")
42    }
43    else{
44      this.data[index] = keyToAdd;
45      this.count++;
46    }
47  }
48
49  insertWithHashCollisions(key, value) {
50    const index = this.hashMod(key);
51    let keyToAdd = new KeyValuePair(key, value);
52
53    //This time, if the index is occupied create a linked list
54    if(this.data[index] !== null){
55        this.head = this.data[index];
56        keyToAdd.next = this.head;
57        this.data[index] = keyToAdd;
58    }
59    else{
60      this.data[index] = keyToAdd;
61    }
62
63    this.count++;
64  }
65
66  insert(key, value) {
67    const index = this.hashMod(key); //Generate index for node
68
69    if(this.containsTargetKey(key)) { //Check for existence of key
70      //If the key exists, start at the head of list and iterate through to find it
71      let currentNode = this.data[index];
72
73      while (currentNode) {
74        if (currentNode.key === key) {
75          currentNode.value = value; // Update the value of the existing key
76          return;
77        }
78        currentNode = currentNode.next;
79      }
80    }
81    else {
82      let newNode = new KeyValuePair(key, value);
83
84      //Set the next pointer to the existing head at the index if there is one, null otherwise
85      newNode.next = this.data[index];
86      this.data[index] = newNode; //Add the new node
87      this.count++; //Increase count
88    }
89  }
90
91  //Check hashmap to see if any objects at the index have a matching key.
92  containsTargetKey(key) {
93    const index = this.hashMod(key); //The key should have the same index
94    let currentNode = this.data[index];
95
96    //Transverse linked list in case of collision to see if any of the keys match
97    while (currentNode) {
98      if (currentNode.key === key) {
99        return true;
100      }
101      currentNode = currentNode.next;
102    }
103    return false;
104  }
105
106  print() {
107    for (let i = 0; i < this.data.length; i++) {
108      let currentNode = this.data[i];
109      let bucketStr = `Bucket ${i}: `;
110
111      while (currentNode) {
112        bucketStr += `{ Key: ${currentNode.key}, Value: ${currentNode.value} } -> `;
113        currentNode = currentNode.next;
114      }
115
116      console.log(bucketStr + 'null');
117    }
118  }
119
120}
121
122let hashTable = new HashTable(2);
123hashTable.insert("key-1", "val-1");
124hashTable.insert("key-2", "val-2");
125//hashTable.insert("key-3", "val-3");
126hashTable.insert("key-1", "val-100000");
127hashTable.print();
128
129module.exports = HashTable;