8 October 2013

Javascript dictionary using objects as keys

One thing that bugs me about Javascript is the inability to have a dictionary with objects as keys. Objects are dictionaries, but essentially toString gets called on anything you use as a key, which isn't always very helpful.

Typical solutions are to call stringify on each object, which is relatively slow and doesn't guarantee reference equality, or to have a custom hashing function, which feels like unnecessary effort. (The jshashtable library generally looks useful, but unless you provide the hashing function the performance drops considerably.

So my requirements are:
  • A dictionary that takes objects as keys
  • And will only resolve values using the same instance of the object (not just some string match)
  • Is fast
  • Without any custom hashing functions
It took a little while to realize that since the key is an object, the value can be stored directly on it, so long as we know which property the value got stored in. Job done. But because my poor head wants to deal with something like a traditional dictionary API, it can be achieved something like this:

function Dict() {
    Dict.id = (Dict.id || 0) + 1;
    this._prop = '_dict' + Dict.id;
Dict.prototype = {
    add: function(key, value) {
        key[this._prop] = value;
    contains: function(key) {
        return typeof key[this._prop] != 'undefined';
    get: function(key) {
        return key[this._prop];
    remove: function(key) {
        delete key[this._prop];

// Sample usage
var a = {};
var b = {};
var c = {};

var dict1 = new Dict();
dict1.add(a, 123);
dict1.add(b, 456);
var dict2 = new Dict();
dict2.add(c, 789);

alert(dict1.get(a));         // 123
alert(dict1.contains(c));    // false
alert(dict2.contains(c));    // true
alert(dict2.contains(c));    // false

OK, it needs a whole lot more work, but you get the idea. We keep track of a global ID so that a key can be used in more than one dictionary simultaneously. If we want to have some way to enumerate over the values or get a count, then we'd also need to store keys/values in the Dictionary itself. I'd probably go with a doubly-linked-list, otherwise add/removes would get slow.

The main disadvantage is that we are adding an extra property to the key objects, which may be undesirable in some circumstances. But overall it solves the requirements without too much mess.

No comments: