W10D1_chainmap.js

var HashMap = function() {
    this.length = 0;
    this._slots = [];
    this._capacity = 8;
    this._secret = (Math.random() * 65536) | 0;
};
HashMap.MAX_LOAD_RATIO = 0.9;
HashMap.SIZE_RATIO = 3;

HashMap._hashString = function(string) {
    var hash = 5381;
    for (var i=0; i<string.length; i++) {
        hash = (hash << 5) + hash + string.charCodeAt(i);
        hash = hash & hash;
    }
    //Reduce the chance of collisions by incorporating the string length,
    //and randomize the hashes to prevent malicious collisions.
    return hash ^ string.length ^ this._secret;
};

HashMap.prototype.get = function(key) {
    var slot = this._findSlot(key, true)
    if (slot.deleted) throw new Error('Key error');
    return slot.value;
};

HashMap.prototype.set = function(key, value) {
    var loadRatio = (this.length + this._deleted + 1) / this._capacity;
    if (loadRatio > HashMap.MAX_LOAD_RATIO) {
        this._resize(this._capacity * HashMap.SIZE_RATIO);
    }

    var slot = this._findSlot(key);
    //Increment the length only if we're not replacing an
    //existing value. (Note that the example in the course
    //doesn't bother with this check, for simplicity; with
    //it, overwriting will errantly increase length.)
    if (slot.deleted !== false) this.length++;
    slot.value = value;
    slot.deleted = false;
};

HashMap.prototype.remove = function(key) {
    var slot = this._findSlot(key, true);
    if (slot.deleted) throw new Error('Key error');
    slot.deleted = true;
    this.length--;
    this._deleted++;
};

//In 'retrieve' mode, will not mutate the hash at all.
//Otherwise, will return a slot object with the key set.
//This can cause suboptimal performance when attempting
//to repeatedly remove keys that do not exist, but keeps
//the code simple.
HashMap.prototype._findSlot = function(key, retrieve) {
    var hash = HashMap._hashString(key);
    var index = hash % this._capacity;
    var slot = this._slots[index];
    //Fast path - no chain to follow.
    if (!slot) {
        if (retrieve) throw new Error('Key error');
        return this._slots[index] = {key: key};
    }
    if (slot.key == key) return slot;
    //Slow path - follow the chain.
    while (slot.next) {
        slot = slot.next;
        if (slot.key == key) return slot;
    }
    //We reached the end of the chain without finding the key.
    //Error out, or create a new slot at the end of the chain.
    if (retrieve) throw new Error('Key error');
    return slot.next = {key: key};
};

HashMap.prototype._resize = function(size) {
    var oldSlots = this._slots;
    this._capacity = size;
    this._deleted = 0;
    this.length = 0; //Thanks to Sierra, Alex, and Robby for catching that!
    this._slots = [];
    for (var i=0; i<oldSlots.length; i++)
        for (var slot = oldSlots[i]; slot; slot = slot.next)
            if (!slot.deleted)
                this.set(slot.key, slot.value);
};

//Enumerate all valid keys in the map
HashMap.prototype.keys = function() {
    var ret = [];
    for (var i = 0; i < this._slots.length; ++i)
        for (var slot = this._slots[i]; slot; slot = slot.next)
            if (!slot.deleted)
                ret.push(slot.key);
    return ret;
}

function main() {
    var map = new HashMap();
    map.set("foo", "demo");
    map.set("bar", "other demo");
    map.set("quux", "yet another");
    console.log("foo:", map.get("foo"));
    map.set("bar", "spam");
    console.log("There are now", map.length, "elements in the map.");
    console.log("bar:", map.get("bar"));
    console.log("Keys:", map.keys());
}

main();