Skip to content

Instantly share code, notes, and snippets.

@jinwolf
Created January 5, 2016 21:52
Show Gist options
  • Save jinwolf/1177e7e09a7ddae46a15 to your computer and use it in GitHub Desktop.
Save jinwolf/1177e7e09a7ddae46a15 to your computer and use it in GitHub Desktop.
(JavaScript) Hash map implementation
function Pair(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
function HashMap(size) {
size = size || 35;
var storage = new Array(35);
function getHash(key, size) {
// Try round robin
var hash = 0;
var chrCode;
if (key.length === 0) {
return hash;
}
for (var i = 0; i < key.length; i++) {
chrCode = key.charCodeAt(i);
hash = ((hash << 5) - hash) + chrCode;
//hash |= 0; // Convert to 32bit integer
}
return hash % size;
}
this.put = function (key, value) {
var index = getHash(key, size);
if (!storage[index]) {
storage[index] = new Pair(key, value);
} else {
storage[index].next = new Pair(key, value);
}
};
this.get = function (key) {
var index = getHash(key, size);
if (!storage[index]) {
return null;
}
var head = storage[index];
while (head) {
if (head.key === key) {
return head.value;
}
head = head.next;
}
return null;
}
this.contains = function (key) {
// How do you know if it's the same key or collision
return !!this.get(key);
}
}
var hashMap = new HashMap(3);
hashMap.put('a', 'Jin Lee');
hashMap.put('b', 'Roy');
hashMap.put('c', 'Max');
hashMap.put('d', 'Bob');
hashMap.put('e', 'Prasanna');
hashMap.put('e', 'George');
console.log(hashMap.contains('a'));
console.log(hashMap.get('a'));
console.log(hashMap.contains('b'));
console.log(hashMap.get('b'));
console.log(hashMap.get('e'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment