Skip to content

Instantly share code, notes, and snippets.

@moritzWa
Created March 17, 2020 08:54
Show Gist options
  • Save moritzWa/d264780c2083c13aee984972db7769f3 to your computer and use it in GitHub Desktop.
Save moritzWa/d264780c2083c13aee984972db7769f3 to your computer and use it in GitHub Desktop.
JavaScript Hashtable Implementation
function hashStringToInt(s, tableSize) {
let hash = 17
for (let i = 0; i < s.length; i++) {
hash = (13 * hash * s.charCodeAt(i)) % tableSize
}
return hash
}
class HashTable {
table = new Array(3)
numItems = 0
resize = () => {
//create new arr double the size with newTable.length
const newTable = new Array(this.table.length * 2)
this.table.forEach(item => {
if (item) {
item.forEach(([key, value]) => {
const idx = hashStringToInt(key, newTable.length)
if (newTable[idx]) {
newTable[idx].push([key, value])
} else {
newTable[idx] = [[key, value]]
}
})
}
})
this.table = newTable
}
setItem = (key, value) => {
//keep track of table leagth
this.numItems++
//monitor loadfactor and rezize table if over 80%
const loadFactor = this.numItems / this.table.length
if (loadFactor > 0.8) {
this.resize()
}
//if index exists push in to combined array
const idx = hashStringToInt(key, this.table.length)
if (this.table[idx]) {
this.table[idx].push([key, value])
} else {
this.table[idx] = [[key, value]]
}
}
getItem = key => {
const idx = hashStringToInt(key, this.table.length)
if (!this.table[idx]) {
return null
}
// O(n)
return this.table[idx].find(x => x[0] === key)[1]
}
}
const myTable = new HashTable()
myTable.setItem("firstName", "bob")
myTable.setItem("lastName", "tim")
console.log(myTable.table.length) //3
myTable.setItem("age", 5)
myTable.setItem("dob", "1/2/3")
console.log(myTable.table.length) //6
console.log(myTable.getItem("firstName")) //bob
console.log(myTable.getItem("lastName")) //tim
console.log(myTable.getItem("age")) //5
console.log(myTable.getItem("dob")) //1/2/3
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment