Created
October 12, 2018 01:10
-
-
Save leandrosilva/e2a20ad0dcd05869799e326da1569ea2 to your computer and use it in GitHub Desktop.
A naive JS implementation of hashtable using Linear Probing to solve 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
let HashTable = function() { | |
let entries = []; | |
this.put = (key, value) => { | |
let hashKey = hashCode(key); | |
let entry = entries[hashKey]; | |
// Linear Probing | |
while (entry) { | |
if (entry && entry[0] === key) break; | |
hashKey++; | |
entry = entries[hashKey]; | |
} | |
entries[hashKey] = [key, value]; | |
}; | |
this.get = (key) => { | |
let hashKey = hashCode(key); | |
let entry = null; | |
// Linear Probing | |
while (!entry && hashKey < entries.length) { | |
entry = entries[hashKey]; | |
if (entry && entry[0] === key) return entry[1]; | |
entry = null; | |
hashKey++; | |
} | |
return null; | |
}; | |
this.delete = (key) => { | |
let hashKey = hashCode(key); | |
let entry = null; | |
// Linear Probing | |
while (!entry && hashKey < entries.length) { | |
entry = entries[hashKey]; | |
if (entry && entry[0] === key) entries[hashKey] = null; | |
entry = null; | |
hashKey++; | |
} | |
}; | |
this.keys = () => { | |
let entryKeys = []; | |
for (let i = 0; i < entries.length; i++) { | |
if (entries[i]) entryKeys.push(entries[i][0]); | |
} | |
return entryKeys; | |
}; | |
this.size = () => { | |
var count = 0; | |
for (let i = 0; i < entries.length; i++) { | |
if (entries[i]) count++; | |
} | |
return count; | |
}; | |
let hashCode = (s) => { | |
let hash = 0; | |
for (let i = 0; i < s.length; i++) { | |
hash = s.charCodeAt(i++) | 0; | |
} | |
let value = Math.round(hash / 2); | |
if (value === -0) value = 0; | |
else if (value < 0) value *= -1; | |
return value; | |
} | |
}; | |
let test = function () { | |
let contacts = new HashTable(); | |
contacts.put("Batman", "bat@man.com"); | |
contacts.put("Superman", "super@man.com"); | |
contacts.put("Spiderman", "spider@man.com"); | |
console.log(`1st test >> There has only ${contacts.size()} sups`); | |
console.log(`Batman <${contacts.get("Batman")}>`); | |
console.log(`Superman <${contacts.get("Superman")}>`); | |
console.log(`Spiderman <${contacts.get("Spiderman")}>`); | |
console.log(`Acquaman <${contacts.get("Acquaman")}>`); | |
contacts.put("Acquaman", "acqua@man.com"); | |
console.log(`\n2nd test >> There has ${contacts.size()} sups now`); | |
console.log(`Batman <${contacts.get("Batman")}>`); | |
console.log(`Superman <${contacts.get("Superman")}>`); | |
console.log(`Spiderman <${contacts.get("Spiderman")}>`); | |
console.log(`Acquaman <${contacts.get("Acquaman")}>`); | |
contacts.delete("Superman"); | |
console.log(`\n3rd test >> Now we have only ${contacts.size()} again`); | |
console.log(`Batman <${contacts.get("Batman")}>`); | |
console.log(`Superman <${contacts.get("Superman")}>`); | |
console.log(`Spiderman <${contacts.get("Spiderman")}>`); | |
console.log(`Acquaman <${contacts.get("Acquaman")}>`); | |
contacts.put("Batman", "bat@mail.com"); | |
console.log(`\n4nd test >> And then Bat chaged this email address 'cause Batman`); | |
console.log(`Batman <${contacts.get("Batman")}>`); | |
console.log(`Superman <${contacts.get("Superman")}>`); | |
console.log(`Spiderman <${contacts.get("Spiderman")}>`); | |
console.log(`Acquaman <${contacts.get("Acquaman")}>`); | |
} | |
test(); |
And btw this is meant for education purpose only. You shouldn't try it in prodution (LOL).
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
A sample output should look like this: