Created
January 5, 2016 21:52
-
-
Save jinwolf/1177e7e09a7ddae46a15 to your computer and use it in GitHub Desktop.
(JavaScript) Hash map implementation
This file contains hidden or 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
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