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();