Last active
October 26, 2023 04:34
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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