Modified HashMap

var HashMap = function HashMap( map ) {
this.data = [];
this.curKey = 0;
this._size = 0;

if (arguments.length == 1) {
// copy map to data
}

this.put = function put( key, value ) {
var rv;
if (typeof key == "object") {
if(!key._HashMap_key){
key._HashMap_key = "_HashMapKey_" + this.curKey++;
}
rv = this.data[key._HashMap_key];
this.data[key._HashMap_key] = value;
} else {
rv = this.data[typeof key + key];
this.data[typeof key + key] = value;
}
this._size = rv ? this._size : this._size + 1;
return rv;
}

this.get = function get( key ) {
if (typeof key == "object") {
return this.data[key._HashMap_key];
}
return this.data[typeof key + key];
}
}

Original HashMap

HashMap = function(){
  this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
  if(typeof key == "object"){
    if(!key.hasOwnProperty._id){
      key.hasOwnProperty = function(key){
        return Object.prototype.hasOwnProperty.call(this, key);
      }
      key.hasOwnProperty._id = this._shared.id++;
    }
    this._dict[key.hasOwnProperty._id] = value;
  }else{
    this._dict[key] = value;
  }
  return this; // for chaining
}
HashMap.prototype.get = function get(key){
  if(typeof key == "object"){
    return this._dict[key.hasOwnProperty._id];
  }
  return this._dict[key];
}

Map Implementation

// linking the key-value-pairs is optional
// if no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
    this.current = undefined;
    this.size = 0;

    if(linkItems === false)
        this.disableLinking();
}

Map.noop = function() {
    return this;
};

Map.illegal = function() {
    throw new Error("illegal operation for maps without linking");
};

// map initialisation from existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
    var map = new Map;

    for(var prop in obj) {
        if(foreignKeys || obj.hasOwnProperty(prop))
            map.put(prop, obj[prop]);
    }

    return map;
};

Map.prototype.disableLinking = function() {
    this.link = Map.noop;
    this.unlink = Map.noop;
    this.disableLinking = Map.noop;
    this.next = Map.illegal;
    this.key = Map.illegal;
    this.value = Map.illegal;
    this.removeAll = Map.illegal;

    return this;
};

// overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
    return (typeof value) + ' ' + (value instanceof Object ?
        (value.__hash || (value.__hash = ++arguments.callee.current)) :
        value.toString());
};

Map.prototype.hash.current = 0;

// --- mapping functions

Map.prototype.get = function(key) {
    var item = this[this.hash(key)];
    return item === undefined ? undefined : item.value;
};

Map.prototype.put = function(key, value) {
    var hash = this.hash(key);

    if(this[hash] === undefined) {
        var item = { key : key, value : value };
        this[hash] = item;

        this.link(item);
        ++this.size;
    }
    else this[hash].value = value;

    return this;
};

Map.prototype.remove = function(key) {
    var hash = this.hash(key);
    var item = this[hash];

    if(item !== undefined) {
        --this.size;
        this.unlink(item);

        delete this[hash];
    }

    return this;
};

// only works if linked
Map.prototype.removeAll = function() {
    while(this.size)
        this.remove(this.key());

    return this;
};

// --- linked list helper functions

Map.prototype.link = function(item) {
    if(this.size == 0) {
        item.prev = item;
        item.next = item;
        this.current = item;
    }
    else {
        item.prev = this.current.prev;
        item.prev.next = item;
        item.next = this.current;
        this.current.prev = item;
    }
};

Map.prototype.unlink = function(item) {
    if(this.size == 0)
        this.current = undefined;
    else {
        item.prev.next = item.next;
        item.next.prev = item.prev;
        if(item === this.current)
            this.current = item.next;
    }
};

// --- iterator functions - only work if map is linked

Map.prototype.next = function() {
    this.current = this.current.next;
};

Map.prototype.key = function() {
    return this.current.key;
};

Map.prototype.value = function() {
    return this.current.value;
};

Road to Coding HashMap

For the 0.2 Release for the processing.js project, I decided I should code some more supportive classes to expand the processing.js library. I picked HashMap, because this class is missing and I still remember coding a C++ HashTable for an assignment in my previous course DSA555.

I start by reading the specifications in the processing.js references, the original processing implementation, and the Java API, to get a sense of what HashMap is supposed to do. The general idea of HashMap is very similar to HashTable, but I want to know the exact differences between them. So I did a search on Google and found this website. HashMap is actually just a new version of HashTable that accepts null keys; plus a name change. I guess I can start coding it.

Of course, I will not waste my time to come up with original codes if there's is a HashMap existed in the web. Therefore, I did a search on Google again to search for HashMap implementation on Javascript. I found this, and it's great, because the first thing I see is a Map implementation. That means I can probably take the code and do little work to use it. But it turns out that the Map class is more complicated than I thought, plus where is the missing Hash part?

I continue scrolling down and see HashMap implementation. As soon as I start tracing the codes, I realize there's no Hash anywhere in the code. Isn't it weird? Then one Javascript feature on array reappears to me: I don't even need to set a size for array in Javascript!! That means there's no need to hash the given key and insert into a limited size HashMap!! So why do I even need to write a HashMap for the processing.js library? The built-in Javascript array can do the exact same job already. That means all the above researches is wasted?

I decide that I shall code a HashMap anyways, since it is a class listed under processing.js reference. So I continue to trace the HashMap implementation. I don't really have a full understand on the usage for a few lines of codes. So I guess I can just modify some codes so that I understand the code better and see if it works the same way before I change those lines. Original version vs. Modified version.

It did, so the next will be inserting this chunk of code into processing.js. To do this, I decide to look at ArrayList, which has already been coded by someone else. Amazingly, I see uses of the keyword this, and I got freaked out since Dave have said something about it being different than what Java's keyword this. Then Dave sent me a link to show me how to use the troublesome keyword.

So, I coded this HashMap and pushed into the GitHub repository. I know it is not good codes, but I tried my best. It doesn't have codes to copy from another implementation of Map, either. But with the tests I throw to the code, it does what it is expected. I will refine the code so that it does more HashMap functions.

0.1 Release

For my 0.1 Release for a project on Processing.js, I have coded the following functions for Processing.js:

split(str, delim), trim(str), arrayCopy(arg1, arg2, arg3, arg4, arg5), match(str, regexp), append(array, element), splitToken(str, tokens) and online().

I have tested all of the functions and made sure they work. But there's 1 issue on arrayCopy(): it does shallow copy only. In the original Processing code, it does shallow copy, too. But it seems like deep copy is more useful. This should be addressed on my 0.2 Release.

My 0.2 Release

0.2 released.

In this release, I have implemented the HashMap function.

HashMap function contains the following member functions:

put(key,value)
get(key)
remove(key)
isEmpty()
size()
clear()
containsKey(key)
containsValue(value)