views:

2295

answers:

4

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?

+17  A: 

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.

keparo
I'd like to use other data types other than just strings as keys...
Pablo Cabrera
The only trouble with this will be determining equality when you try to look up values according to a specific type of key. Do you want this with or without type coercion? Can you provide more detail on how you plan to use it? What are the benefits of having a certain type of key?
keparo
Because sometimes I wan't to map two or more objects that are not directly related to each other.
Pablo Cabrera
I'll answer this more thoroughly if you like, but it sounds like you could still use a String or a Number (think Array()) for a key, and any unrelated type as a value. Is this incorrect?
keparo
If I knew beforehand wich index would match every entry then yes, but thats the purpouse of a hash function isn't it? So given an object, I don't need to know it's index.
Pablo Cabrera
Ok, you're the boss. Answer is above..
keparo
'Guess you're right. I've googled a bit for it and the closest thing I've fould was this (http://blogs.acceleration.net/russ/archive/2005/07/05/1736.aspx). I'll just wait a bit more to see if someone comes with something new before acceptiong your answer ok?
Pablo Cabrera
I think it's a good question.. definitely worth chewing on..
keparo
That's not a hashtable, at least not in performance. Every operation you have is O(n) (they all call containsKey, which, unless I'm missing something, just loops over the keys). You created an object that stores keys/values, but it does NOT perform like a hashtable.
Herms
@Herms- That was exactly my point.. Read my commentary.
keparo
Oops, I totally missed that in your comment. :)
Herms
I think there is a decent implementation of Java's HashMap now: my jshashtable (http://www.timdown.co.uk/jshashtable)
Tim Down
A: 

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"
insin
+1  A: 

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).

Herms
+3  A: 

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

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

Tim Down
That's a really good implementation indeed. I thought of doing something along these lines.
Pablo Cabrera
Although I would work on the generic hash function. "toString()" wouldn't be a good hash function I think.
Pablo Cabrera
True, but it keeps things simple. What do you suggest?
Tim Down
You could mimick Java's hashCode method's for it's "primitive" classes maybe, or even enforce the user to provide a hash function... just a thought. Good work anyway I'll be glad to use your implementation anytime. =]
Pablo Cabrera
I've recently revisited jshashtable and released a new version. I thought about your comments and decided to leave the generic hash function as it is. I simply can't see a decent way to make a generic hash function. Iterating over properties of a key object would be painfully slow. Checking the constructor property of the key object could be useful if only it was possible to easily extract the constructor function's name. It's left to the calling code, which will know more about the keys than a generic function can hope to, to provide a sensible hashing function.
Tim Down