Skip to content

Instantly share code, notes, and snippets.

@TheSaviourEking
Last active October 26, 2023 04:34
Show Gist options
  • Save TheSaviourEking/c6ea58f36e18958a1597f9faa3fb01e4 to your computer and use it in GitHub Desktop.
Save TheSaviourEking/c6ea58f36e18958a1597f9faa3fb01e4 to your computer and use it in GitHub Desktop.
still working on making my hashMap faster to pass the timing test for constant time lookup even when there's collisions
class KeyValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
}
class HashTable { // get O(1), set O(1), deleteKey O(1)
constructor(numBuckets = 8) {
// Initialize your buckets here
// Your code here
this.capacity = numBuckets;
this.count = 0;
this.data = new Array(this.capacity).fill(null);
}
hash(key) {
let hashValue = 0;
for (let i = 0; i < key.length; i++) {
hashValue += key.charCodeAt(i);
}
return hashValue;
}
hashMod(key) {
// Get index after hashing
return this.hash(key) % this.capacity;
}
/*-----------------------------------------------------------------------------------------------------*/
// here's the fastest i benchmarked, but it's still not fast enough
insert(key, value) {
// Your code here
// Get index
const index = this.hashMod(key);
let current = this.data[index];
while (current && !(current.key === key)) {
current = current.next;
}
if (current) {
current.value = value;
return;
}
else {
const keyValuePair = new KeyValuePair(key, value);
keyValuePair.next = this.data[index];
this.data[index] = keyValuePair;
this.count++;
}
}
// LOL, I've been working on implementing mine for 2 days as you see, I'm totally blocked right now confused AF
// -> HELP PLEASE!!
// insert(key, value) {
// // Your code here
// // Get index
// const index = this.hashMod(key);
// let current = this.data[index];
// while (current) {
// if (current.key === key) {
// current.value = value;
// return;
// }
// current = current.next;
// }
// // if (current) {
// // current.value = value;
// // return;
// // }
// // else {
// const keyValuePair = new KeyValuePair(key, value);
// keyValuePair.next = this.data[index];
// this.data[index] = keyValuePair;
// this.count++;
// // }
// }
// insert(key, value) {
// // Your code here
// const index = this.hashMod(key);
// const keyValuePair = new KeyValuePair(key, value);
// if (this.data[index]) {
// let current = this.data[index];
// while (current) {
// if (current.key === key) {
// current.value = value;
// return;
// }
// current = current.next;
// }
// keyValuePair.next = this.data[index];
// this.data[index] = keyValuePair;
// this.count++;
// } else {
// this.data[index] = keyValuePair;
// this.count++;
// }
// }
/*-------------------------------------------------------------------------------------------------------*/
read(key) {
// Your code here
let index = this.hashMod(key);
let current = this.data[index];
while (current && current.key !== key) {
current = current.next;
}
return current ? current.value : undefined;
}
resize() {
// Your code here
let oldData = this.data;
this.capacity = this.capacity * 2;
this.count = 0;
this.data = new Array(this.capacity).fill(null);
for (let i = 0; i < oldData.length; i++) {
if (oldData[i]) {
let current = oldData[i];
while (current) {
this.insert(current.key, current.value);
current = current.next;
}
}
}
}
delete(key) {
// Your code here
let index = this.hashMod(key);
if (this.keyValues.has(key)) {
let current = this.data[index];
let prev = null;
while (current && !(key === current.key)) {
prev = current;
current = current.next;
}
if (prev) {
prev.next = current.next
} else {
this.data[index] = current.next;
}
this.keyValues.delete(key);
this.count--;
} else {
return 'Key not found';
}
}
}
module.exports = HashTable;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment