Is there any good JavaScript hash(code/table) implementation out there?

Question

Yes, I know you could use regular objects as associative arrays in JavaScript, but I'd like to use something closer to java's Map's implementation (HashMap, LinkedHashMap etc). Something that could have any kind of data used as key. Are there any good hash(code/table) in JavaScript implementation out there?

Answer 1

In javascript, objects are literally a hash implementation. A Java HashMap will be a little bit of a fake-out, so I'd challenge you to re-think your needs.

The straight answer is no, I don't believe that there is a great implementation of Java's HashMap in javascript. If there is, it's bound to be part of a library that you may or may not want to use, and you certainly don't need to include a library just to have a little hash table.

So let's go ahead and write one, just to examine the problem. You can use it if you like. We'll just start by writing a constructor, and we'll piggyback off of Array, which is Object, but has some useful methods that will keep this example from getting too tedious:

function HashMap () {
    var obj = [];
    return obj;
}

var myHashMap = HashMap();

We'll add some methods straight from the world of Java, but translate into javascript as we go...

function HashMap() {
    var obj = [];
    obj.size = function () {
        return this.length;
    };
    obj.isEmpty = function () {
        return this.length === 0;
    };
    obj.containsKey = function (key) {
        for (var i = 0; i < this.length; i++) {
            if (this[i].key === key) {
                return i;
            }
        }
        return -1;
    };
    obj.get = function (key) {
        var index = this.containsKey(key);
        if (index > -1) {
            return this[index].value;
        }
    };
    obj.put = function (key, value) {
        if (this.containsKey(key) !== -1) {
            return this.get(key);
        }
        this.push({'key': key, 'value': value});
    };
    obj.clear = function () {
        this = null;  // Just kidding...
    };
    return obj;
}

We could continue to build it out, but I think it's the wrong approach. At the end of the day, we end up using what javascript provides behind the scenes, because we just simply don't have the HashMap type. In the process of pretending, it lends itself to all kinds of extra work.

It's a bit ironic that one of the things that makes javascript such an interesting and diverse language is the ease with which it handles this kind of wrestling. We can literally do anything we'd like, and the quick example here does nothing if it doesn't illustrate the deceptive power of the language. Yet given that power, it seems best not to use it.

I just think javascript wants to be lighter. My personal recommendation is that you re-examine the problem before you try implement a proper Java HashMap. Javascript neither wants nor affords for one.

Remember the native alternative:

var map = [{}, 'string', 4, {}];

..so fast and easy by comparison.

On the other hand, I don't believe that there are any hard-and-fast answers here. This implementation really may be a perfectly acceptable solution. If you feel you can use it, I'd say give it a whirl. But I'd never use it if I felt that we have reasonably simpler and more natural means at our disposal.. which I'm almost certain that we do.

Sidenote: Is efficiency related to style? Notice the performance hit.. there's a big O staring us in the face at HashMap.put()... The less-than-optimal performance probably isn't a show-stopper here, and you'd probably need to be doing something very ambitious or have a large set of data before you'd even notice a performance hickup a modern browser. It's just interesting to note that operations tend to become less efficient when you're working against the grain, almost as if there is a natural entropy at work. Javascript is a high level language, and should offer efficient solutions when we keep in line with its conventions, just as a HashMap in Java will be a much more natural and high performing choice.

Answer 2

Here's a naive implementation I just put together - as keparo mentioned in a comment, one of the big issues is equality checking:

var ObjectMap = function()
{
    this._keys = [];
    this._values = [];
};

ObjectMap.prototype.clear = function()
{
    this._keys = [];
    this._values = [];
};

ObjectMap.prototype.get = function(key)
{
    var index = this._indexOf(key, this._keys);
    if (index != -1)
    {
        return this._values[index];
    }
    return undefined;
};

ObjectMap.prototype.hasKey = function(key)
{
    return (this._indexOf(key, this._keys) != -1);
};

ObjectMap.prototype.hasValue = function(value)
{
    return (this._indexOf(value, this._values) != -1);
};

ObjectMap.prototype.put = function(key, value)
{
    var index = this._indexOf(key, this._keys);
    if (index == -1)
    {
        index = this._keys.length;
    }

    this._keys[index] = key;
    this._values[index] = value;
};

ObjectMap.prototype.remove = function(key)
{
    var index = this._indexOf(key, this._keys);
    if (index != -1)
    {
        this._keys.splice(index, 1);
        this._values.splice(index, 1);
    }
};

ObjectMap.prototype.size = function()
{
    return this._keys.length;
};

ObjectMap.prototype._indexOf = function(item, list)
{
    for (var i = 0, l = list.length; i < l; i++)
    {
        if (this._equals(list[i], item))
        {
            return i;
        }
    }
    return -1;
};

ObjectMap.prototype._equals = function(a, b)
{
    if (a === b)
    {
        return true;
    }

    // Custom objects can implement an equals method
    if (typeof a.equals == "function" &&
        typeof b.equals == "function")
    {
        return a.equals(b);
    }

    // Arrays are equal if they're the same length and their contents are equal
    if (a instanceof Array && b instanceof Array)
    {
        if (a.length != b.length)
        {
            return false;
        }

        for (var i = 0, l = a.length; i < l; i++)
        {
            if (!this._equals(a[i], b[i]))
            {
                return false;
            }
        }

        return true;
    }

    // Checking object properties - objects are equal if they have all the same
    // properties and they're all equal.
    var seenProperties = {};
    for (var prop in a)
    {
        if (a.hasOwnProperty(prop))
        {
            if (!b.hasOwnProperty(prop))
            {
                return false;
            }

            if (!this._equals(a[prop], b[prop]))
            {
                return false;
            }

            seenProperties[prop] = true;
        }
    }

    for (var prop in b)
    {
        if (!(prop in seenProperties) && b.hasOwnProperty(prop))
        {
            if (!a.hasOwnProperty(prop))
            {
                return false;
            }

            if (!this._equals(b[prop], a[prop]))
            {
                return false;
            }
        }
    }

    return true;
};

Example usage:

>>> var map = new ObjectMap();
>>> var o = {a: 1, b: [1,2], c: true};
>>> map.put(o, "buns");
>>> map.get(o)
"buns"
>>> map.get({a: 1, b: [1,2], c: true});
"buns"
>>> map.get({a: 1, b: [1,2], c: true, d:"hi"});
>>> var a = [1,2,3];
>>> map.put(a, "cheese");
>>> map.get(a);
"cheese"
>>> map.get([1,2,3]);
"cheese"
>>> map.get([1,2,3,4]);
>>> var d = new Date();
>>> map.put(d, "toast");
>>> map.get(d);
"toast"
>>> map.get(new Date(d.valueOf()));
"toast"

This is in no way a complete implementation, just a pointer for a way to implement such an object. For example, looking at what I've given, you would also need to add constructor property checks before the object property check, as this currently works:

>>> function TestObject(a) { this.a = a; };
>>> var t = new TestObject("sandwich");
>>> map.put(t, "butter");
>>> map.get({a: "sandwich"})
"butter"

Answer 3

Note that java collections using "any kind of object" as a key isn't quite right. Yes, you can use any object, but unless that object has good hashcode() and equals() implementations then it won't work well. The base Object class has a default implementation for these, but for custom classes to work (effectively) as hashtable keys you need to override them. Javascript has no equivalent (that I know of).

To create a hashtable in javascript that can (effectively) use arbitrary objects as the key you'd need to enforce something similar on the objects you use, at least if you want to keep the performance gains of a hashtable. If you can enforce a 'hashcode()' method that returns a String, then you can just use an Object under the hood as the actual hashtable.

Otherwise, you'd need to so something like the other solutions posted, which as of right now do not perform like hashtables. They both do O(n) searches over the list to try and find the key, which pretty much defeats the purpose of a hashtable (hashtables are generally constant time for get/put).

Answer 4

I have released a standalone JavaScript hash table implementation that goes further than those listed here.

http://www.timdown.co.uk/jshashtable/