HashMap in Javascript

Question

I began working on a Javascript project, and the first fundamental building block is a data structure that mimics Java's java.util.HashMap, since Javascript {} works for only string keys, as far as I know. Without further ado, here is my code:

function HashMapNode(key, value) {
 this.key = key;
 this.value = value;
 this.prev = null;
 this.next = null;
}
function HashMap(keyEquals, keyHashCode) {
 this.storageArray = new Array(8);
 this.size = 0;
 this.keyEquals = keyEquals;
 this.keyHashCode = keyHashCode;
}
HashMap.prototype.insert = function(node, storageArray) {
 var storageArrayIndex = this.keyHashCode(node.key) & (storageArray.length - 1);
 node.prev = null;
 node.next = storageArray[storageArrayIndex];
 if (storageArray[storageArrayIndex]) {
 storageArray[storageArrayIndex].prev = node;
 }
 storageArray[storageArrayIndex] = node;
};
HashMap.prototype.expand = function() {
 var newStorageArray = new Array(2 * this.storageArray.length);
 for (var i = 0; i < this.storageArray.length; ++i) {
 while (this.storageArray[i]) {
 var node = this.storageArray[i];
 this.storageArray[i] = this.storageArray[i].next;
 this.insert(node, newStorageArray);
 }
 }
 this.storageArray = newStorageArray;
};
HashMap.prototype.put = function(key, value) {
 if (this.size === this.storageArray.length) {
 this.expand();
 }
 var storageArrayIndex = this.keyHashCode(key) & (this.storageArray.length - 1);
 var currentNode = this.storageArray[storageArrayIndex];
 while (currentNode) {
 if (this.keyEquals(currentNode.key, key)) {
 var oldValue = currentNode.value;
 currentNode.value = value;
 return oldValue;
 }
 currentNode = currentNode.next;
 }
 // Once here, the 'key' has no mapping in this hash map.
 var newNode = new HashMapNode(key, value);
 this.insert(newNode, this.storageArray);
 this.size++;
 return null;
};
HashMap.prototype.getNodeByKey = function(key) {
 var storageArrayIndex = this.keyHashCode(key) & (this.storageArray.length - 1);
 var currentNode = this.storageArray[storageArrayIndex];
 while (currentNode) {
 if (this.keyEquals(currentNode.key, key)) {
 return currentNode;
 }
 currentNode = currentNode.next;
 }
 return null;
};
HashMap.prototype.get = function(key) {
 var node = this.getNodeByKey(key);
 return node ? node.value : null;
};
HashMap.prototype.containsKey = function(key) {
 return this.getNodeByKey(key) !== null;
};
HashMap.prototype.unlink = function(node, storageArrayIndex) {
 if (node.prev) {
 node.prev.next = node.next;
 } else {
 this.storageArray[storageArrayIndex] = node.next;
 if (this.storageArray[storageArrayIndex]) {
 this.storageArray[storageArrayIndex].prev = null;
 }
 }
 if (node.next) {
 node.next.prev = node.prev;
 }
};
HashMap.prototype.remove = function(key) {
 var storageArrayIndex = this.keyHashCode(key) & (this.storageArray.length - 1);
 var currentNode = this.storageArray[storageArrayIndex];
 while (currentNode) {
 if (this.keyEquals(currentNode.key, key)) {
 this.unlink(currentNode, storageArrayIndex);
 this.size--;
 return currentNode.value;
 }
 currentNode = currentNode.next;
 }
 return null;
};
HashMap.prototype.getSize = function() {
 return this.size;
};
function Point(x, y) {
 this.x = x;
 this.y = y;
}
function pointEquals(p1, p2) {
 return p1.x === p2.x && p1.y === p2.y;
}
function pointHashCode(p) {
 return p.x ^ p.y;
}
function assert(test) {
 if (!test) {
 console.log("Test failure!");
 }
}
function test() {
 var map = new HashMap(pointEquals, pointHashCode);
 var p1 = new Point(0, 0);
 var p2 = new Point(0, 0);
 map.put(p1, "value");
 assert(map.get(p1) === "value");
 assert(map.get(p2) === "value");
 p2.x = 1;
 assert(!map.containsKey(p2));
 map.put(p1, "second value");
 assert(map.get(p1) === "second value");
 map.remove(p1);
 assert(map.get(p1) === null);
 assert(map.containsKey(p1) === false);
 for (var i = 0; i < 100; ++i) {
 assert(map.getSize() === i);
 var p = new Point(0, i);
 map.put(p, "" + i);
 assert(map.getSize() === i + 1);
 }
 for (var i = 99; i >= 0; --i) {
 var p = new Point(0, i);
 assert(map.get(p) === "" + i);
 }
 for (var i = 0; i < 100; ++i) {
 assert(map.getSize() === 100 - i);
 var p = new Point(0, i);
 assert(map.remove(p) === "" + i);
 assert(map.getSize() === 99 - i);
 }
}
test();

Any critique is much appreciated.

• Joseph: Map and WeakMap exist in JS.
• coderodde: @Joseph Added the reinventing-the-wheel tag.
• coderodde: @Joseph Wait. Does it say that it uses a linear search to match a key?
• woxxom: @Iwrestledabearonce., internally those are coerced into strings. Object keys are strings or symbols.
• woxxom: You can fool Chrome into displaying it as an array: define a splice property that is a function, and length that is a number.

Answer 1

Encapsulation

Many of the methods are implementation details and should not be accessible by users of the hash map, such as insert and expand. It's possible to hide these methods using a closure, something of the form:

function HashMap(equals, hashCode) {
 var storageArray = new Array(8); // size must be power of 2
 var size = 0;
 var insert = function(node, storageArray) {
 // ...
 };
 // ...
 return {
 put: function(key, value) {
 // ...
 },
 // ...
 };
}

Similarly, HashMapNode should be hidden inside HashMap.

Expanding storage too early

The put method expands the storage immediately when the size is at capacity. But if the key exists in the map, then we don't need to extend the storage yet, because we will overwrite an existing value. So it would be better to move the call to expand further down in the function, to expand only when we know for certain that it's necessary.

Duplicated logic

The computation of the storage index is repeated at 3 places. It would be better to move that to a helper function.

Unnecessary condition

The conditional inside the else is the same as the last conditional, so you can simply remove the one inside the else:

if (node.prev) {
 node.prev.next = node.next;
} else {
 this.storageArray[storageArrayIndex] = node.next;
 if (this.storageArray[storageArrayIndex]) {
 this.storageArray[storageArrayIndex].prev = null;
 }
}
if (node.next) {
 node.next.prev = node.prev;
}

Scope in JavaScript

The second var i here is an error, because by that time the variable i is already declared:

for (var i = 99; i >= 0; --i) {
 // ...
}
for (var i = 0; i < 100; ++i) {
 // ...
}

This is worse than incorrect, because it dangerously misleads into believing that i is only visible inside the loop, which is not the case.

If possible, it would be better to use let instead of var (requires adding "use strict"). If that's not possible, then move var i to the beginning of the function.

Fragile storage array indexing

var storageArrayIndex = this.keyHashCode(key) & (this.storageArray.length - 1);

This calculation of the storage index is a bit fragile, because it relies on this.storageArray.length being a power of 2. This crucial detail should be documented.