Skip to content

Instantly share code, notes, and snippets.

@leandrosilva
Created October 12, 2018 01:10
Show Gist options
  • Select an option

  • Save leandrosilva/e2a20ad0dcd05869799e326da1569ea2 to your computer and use it in GitHub Desktop.

Select an option

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", "[email protected]");
contacts.put("Superman", "[email protected]");
contacts.put("Spiderman", "[email protected]");
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", "[email protected]");
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", "[email protected]");
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 <[email protected]>
Superman <[email protected]>
Spiderman <[email protected]>
Acquaman <null>

2nd test >> There has 4 sups now
Batman <[email protected]>
Superman <[email protected]>
Spiderman <[email protected]>
Acquaman <[email protected]>

3rd test >> Now we have only 3 again
Batman <[email protected]>
Superman <null>
Spiderman <[email protected]>
Acquaman <[email protected]>

4nd test >> And then Bat chaged this email address 'cause Batman
Batman <[email protected]>
Superman <null>
Spiderman <[email protected]>
Acquaman <[email protected]>

@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