11

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})
Improve this question

8 Answers 8

Reset to default
8

I would recommend you the jshashtable project from Tim Down.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

jshashtable is a good start, but it only works when the key is the exact same object. I want to be able to use a different but equal object (b vs. c in the code above). Essentially, I need a library which provides a good definition of equality by properties and values.
As would I :). In this case, you'd need a custom equals function that compares the properties of two objects, either as a method of your objects or, better, passed into the Hashtable constructor: var objectsEqual = function(o1, o2) { for (var i in o1) { if (o1[i] !== o2[i]) { return false; } } for (i in o2) { if (!(i in o1)) { return false; } } return true; }; var hash = new Hashtable(null, objectsEqual);
Peeja: jshashtable handles that case when you provide it with your own equality function, as in my comment above (forgive the lack of formatting; comments don't allow any better).
True, that works. For the use I have in mind, I really need to use a hashCode approach (for performance). Do you know a good way to hash a JS object by its properties? That's really the heart of my question.
I considered this question when deciding whether to try and implement a default hash function for jshashtable. Really, there's no easy way in JavaScript. You could write a function to extract all the properties in an object into an array of key-value pairs, sort it on property name and then JSONify that, but once you're doing all that in your hashing function you may find that it's more efficient not to use it. A compromise could be to have a hashing function that simply concatenates the object's values for one or two properties that vary a lot between your objects.
2

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

Improve this answer

Comments

1

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 = {};
}
Improve this answer

2 Comments

Yeah, it needs some work to be perfomant and bullet-proof, but I think you've got the right idea.
@Peeja: I'm not sure that it can be made performant while still meeting your requirements. Although, depending on your exact needs then perhaps it can be made good enough.
0

You could implement your own class with a toString that ensures an ordering of keys.

Improve this answer

1 Comment

That's exactly what I'm trying to do.
0

Prototype has Hash quite nicely covered http://prototypejs.org/api/hash

Improve this answer

1 Comment

The Prototype's Hash implementation will not work to store an arbitrary object as a key, the OP will have exactly the same results that is having now, check the implementation of the set method and this example.
0

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.

Improve this answer

1 Comment

FYI I submitted the change. The queries above will both return 200 now.
0

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.

Improve this answer

Comments

-2

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; }
Improve this answer

2 Comments

Please don't. You'll have a performance nightmare. Benchmark here: people.iola.dk/arj/2012/05/30/hashtables-in-javascript
This does not answer the original question, which is about creating hashmaps with object keys.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.