Reputation: 14264

Is there a hashmap library for JavaScript?

In JavaScript, all Objects act a bit like hashmaps. However, the keys to these hashmaps must be strings. If they're not, they're converted with toString(). That means:

var a = {foo: 1};
var b = {bar: 2};
var o = {};
o[a] = 100;
o[b];              // 100
JSON.stringify(o); // '{"[object Object]":100}'

That is, since the toString() of any plain Object is [object Object], they all address the same value.

I'd like to create a hashmap where Objects with the same properties and values address the same value, but objects with different properties or values address different values. That is:

var a = {foo: 1};
var b = {bar: 2, baz: 3};
var c = {baz: 3, bar: 2};
var hash = new Hash();
hash.set(a, 100);
hash.get(b);      // undefined
hash.set(b, 200);
hash.get(b);      // 200
hash.get(c);      // 200

My first instinct was to use JSON.stringify() to turn objects into strings, but:

var hash = {};
var b = {bar: 2, baz: 3};
var c = {baz: 3, bar: 2};
hash[JSON.stringify(b)] = 100
hash[JSON.stringify(b)] // 100
hash[JSON.stringify(c)] // undefined
JSON.stringify(b)       // '{"bar":2,"baz":3}'
JSON.stringify(c)       // '{"baz":3,"bar":2}'

That is, JSON serialization is order-dependent.

Is there a good library or technique to implement a hashmap like this?

Update:

Equivalently, is there a good hashing function such that:

hash({foo: 1, bar: 2}) == hash({bar: 2, foo: 1})

Upvotes: 11

Answers (8)

mwcz

Reputation: 9301

This is an old question, but ES6 has a feature that may be relevant: Map

Maps can have arbitrary objects as keys, and arbitrary values as values. The main distinction is that the objects used as keys stay unique, even if objects are identical.

Here's an example:

var map = new WeakMap();

var o1 = {x: 1};
var o2 = {x: 1};

map.set(o1, 'first object');
map.set(o2, 'second object');

// The keys are unique despite the objects being identical.

map.get(o1); // 'first object'
map.get(o2); // 'second object'
map.get({x: 1}); // undefined

JSON.stringifying the objects wouldn't be able to distinguish between o1 and o2.

MDN has more info. There's also a WeakMap which doesn't maintain references to the objects used as keys, so they may be garbage collected.

The Traceur compiler doesn't yet have official polyfills for Map and Weakmap, but there is an open pull request with polyfills for both. The code for those polyfills (in case anyone wants to add them individually) are here: Map and WeakMap. Assuming those polyfills work well, you can start using Map or WeakMap today. :)

Upvotes: 2

Ingo Bürk

Reputation: 20043

This thread actually led me to find a bug in my current project. However, this is fixed now and my HashMap implementation in my project (https://github.com/Airblader/jsava) will do exactly what you described. Unlike jshashtable, there are no buckets.

Upvotes: 0

jsn

Reputation: 5

the answer is to use two arrays, one for keys, one for values.

var i = keys.indexOf(key)
if (i == -1)
  {keys.push(key); values.push(value)}
else
  {values[i] = value; }

Upvotes: -2

LukeH

Reputation: 269368

Here's a quick proof-of-concept...

I've hardly tested it at all, and I'm certain that there will be corner-cases that it can't deal with.

Performance will be hideously inefficient because the __createHash function needs to recurse through the members of any objects and then sort them, in order to generate a "hash" that meets your requirements.

HashMap = function() {
    this.get = function(key) {
        var hash = this.__createHash(key);
        return this.__map[hash];
    };

    this.set = function(key, value) {
        var hash = this.__createHash(key);
        this.__map[hash] = value;
    };

    this.__createHash = function(key) {
        switch (typeof key) {
            case 'function':
                return 'function';

            case 'undefined':
                return 'undefined';

            case 'string':
                return '"' + key.replace('"', '""') + '"';

            case 'object':
                if (!key) {
                    return 'null';
                }

                switch (Object.prototype.toString.apply(key)) {
                    case '[object Array]':
                        var elements = [];
                        for (var i = 0; i < key.length; i++) {
                            elements.push(this.__createHash(key[i]));
                        }
                        return '[' + elements.join(',') + ']';

                    case '[object Date]':
                        return '#' + key.getUTCFullYear().toString()
                                   + (key.getUTCMonth() + 1).toString()
                                   + key.getUTCDate().toString()
                                   + key.getUTCHours().toString()
                                   + key.getUTCMinutes().toString()
                                   + key.getUTCSeconds().toString() + '#';

                    default:
                        var members = [];
                        for (var m in key) {
                            members.push(m + '=' + this.__createHash(key[m]));
                        }
                        members.sort();
                        return '{' + members.join(',') + '}';
                }

            default:
                return key.toString();
        }
    };

    this.__map = {};
}

Upvotes: 1

Dan Stocker

Reputation: 702

jOrder could be modified to treat objects with the same properties (but in different order) as identical when performing an index lookup.

If you have the object {bar: 2, baz: 3, val: 200} in your list, and you've previously put a fitting index on a jOrder table like this:

var table = jOrder(data)
    .index('signature', ['bar', 'baz'], {grouped: true});

Then right now table.where([{bar: 2, baz: 3}])[0].val will return 200, but table.where([{baz: 3, bar: 2}])[0].val won't. It wouldn't take much effort though to make it not depend on the order of properties. Let me know if you're interested and I'll push the fix to GitHub as soon as I can.

Upvotes: 0