Skip to content

Instantly share code, notes, and snippets.

@leandrosilva
Created October 12, 2018 01:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save leandrosilva/e2a20ad0dcd05869799e326da1569ea2 to your computer and use it in GitHub Desktop.
Save leandrosilva/e2a20ad0dcd05869799e326da1569ea2 to your computer and use it in GitHub Desktop.
A naive JS implementation of hashtable using Linear Probing to solve collisions
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();
@leandrosilva
Copy link
Author

A sample output should look like this:

$ node hashtable.js
1st test >> There has only 3 sups
Batman <bat@man.com>
Superman <super@man.com>
Spiderman <spider@man.com>
Acquaman <null>

2nd test >> There has 4 sups now
Batman <bat@man.com>
Superman <super@man.com>
Spiderman <spider@man.com>
Acquaman <acqua@man.com>

3rd test >> Now we have only 3 again
Batman <bat@man.com>
Superman <null>
Spiderman <spider@man.com>
Acquaman <acqua@man.com>

4nd test >> And then Bat chaged this email address 'cause Batman
Batman <bat@mail.com>
Superman <null>
Spiderman <spider@man.com>
Acquaman <acqua@man.com>

@leandrosilva
Copy link
Author

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