1

I want to implement an ObjectSet class, which contains a set of object references. In the implementation 1 below, I use an Array to store the objects. In the put/remove function, I iterate the whole array to find passed-in object. The set size would be very large and the functions are called frequently. The performance of the iteration is a concern.

In the implementation 2, I use an Object, which acts as a map, to store the object references. In this manner, it doesn't need to iterate all the objects in the put/remove functions. The performance would be better. But the Object property must be a string. I can't use the object as the key. The question is: Is there any algorithm to generate a unique key for an object?

Implementation 1 - Store object references in an Array

function ObjectSet() {
    this.store = []; // Array
}
ObjectSet.prototype = {
    put: function( obj) {
        var store = this.store;
        for (var i = 0; i < store.length; i++) {
            if (store[i] === obj) {
                return;
            }
        };
    },
    remove: function( obj ) {
        var store = this.store;
        for (var i = 0; i < store.length; i++) {
            if (store[i] === obj) {
                store.splice(i, 1);
            }
        };
    }
};

Implementation 2 - Store object references in an Object

function ObjectSet() {
    this.store = {}; // Object
}
ObjectSet.prototype = {
    put: function( obj) {
        var key = generateKeyFromObject(obj);
        if(!this.store[ key ]){
            this.store[ key ] = obj;
        }
    },
    remove: function( obj ) {
        var key = generateKeyFromObject(obj);
        if(this.store[ key ]){
            delete this.store[ key ];
        }
    }
};
function generateKeyFromObject(obj){
    // Question: How to generate a unique key for an object?
}

============UPDATE 7/2/2014================

Paste my implementation based on the answers/comments.

// Use the global index to avoid the clash when the same object is added to different sets.
var index = 1, key='##key';
function generateKeyFromObject(obj){
    if(!obj[key]){
        var uniqueKey="##uniqueKey" + (index++).toString();
        Object.defineProperty(obj, key, {
            writable: false,
            enumerable: false,
            configurable: false,
            value: uniqueKey
        });
   }
    return obj[key];
}
Jeffrey
  • 4,436
  • 9
  • 38
  • 54
  • I don't think Javascript currently has any good way to do this. In [ECMAScript 6](http://wiki.ecmascript.org/doku.php?id=harmony:simple_maps_and_sets), that'll probably change, but that's not happening any time soon. – user2357112 Jul 02 '14 at 07:31
  • 1
    See [this post](http://stackoverflow.com/questions/7958292/mimicking-sets-in-javascript/7958422#7958422) about an implementation of a `set` object. Then look [here on github](https://github.com/jfriend00/Javascript-Set) for an implementation of an ObjectSet that can store objects in the set. This implementation contains code to generate a unique key for each object. The chosen implementation here is just a monotomically increasing counter that is then stored on the object as a non-enumerable property. You may want to just use the implementation that is already built, working and tested. – jfriend00 Jul 02 '14 at 07:31
  • Well, you could JSON.stringify() the object, then generate a md5 hash. To be sure there's one unique object each time, create an object class that when instantiated, generate a random number or string, and put it as attribute. This way, every object would have a different signature, and the md5 would be different each time. – Larta Jul 02 '14 at 07:33
  • @Larta - no need for random number strings. You can just use a monotomically increasing counter. Unique ids don't have to be random, just unique. – jfriend00 Jul 02 '14 at 07:36
  • @jfriend00 Yep, that's true, i didn't think about an increasing id, what is way better than my solution. – Larta Jul 02 '14 at 07:38
  • FYI, the [ObjectSet implementation I linked to above](https://github.com/jfriend00/Javascript-Set/blob/master/objectset.js#L77) actually supports three ways of generating the unique id. The default it to just use a monotonically increasing counter, but it can also be told to use a particular method on the object, a particular property name on the object or a particular custom function to generate the id. – jfriend00 Jul 02 '14 at 07:39

1 Answers1

2

If it's no problem to add attributes to the objects you're inserting:

function ObjectSet() 
{
    var id = 0;

    this.nextId = function() { // id generator function
        return ++id;
    };

    this.store = {}; // Object
}

ObjectSet.prototype = {
    put: function(obj) {
        if (!obj.id) {
            obj.id = this.nextId();
            this.store[obj.id] = obj;
        }
    },
    remove: function(obj) {
        if (obj.id && this.store[obj.id]) {
            delete this.store[key];
        }
    }
};

As pointed out in the comments, this will become a problem if objects can be shared between sets; in that case the same id generator needs to be used for all objects that are used.

var nextId = function() {
    var id = 0;

    return function() {
        return ++id;
    };
}();
Ja͢ck
  • 170,779
  • 38
  • 263
  • 309
  • This has a problem that each `ObjectSet()` has it's own counter so if an object is used in more than one set, you can have id conflicts (e.g. different objects with the same id) which is not good. – jfriend00 Jul 02 '14 at 07:35
  • 1
    You could work around that by generating a unique string to use as the key for the id property in each set. – RobH Jul 02 '14 at 07:42
  • @RobH - there's no need for that. Just use a single counter for all your sets as Jack has in the last block of code. – jfriend00 Jul 02 '14 at 21:53
  • @jfriend00 - I know it's not required, it is just another option. – RobH Jul 03 '14 at 08:13