Is there a data structure like the Java Set in JavaScript?

Question

I want to use a data structure in JavaScript that can be used to store number of IDs. I should be able to check if a key already exists in that set, something like Java Sets.

I want to achive same behaviours as follows (this code is in Java):

Set<String> st = new HashSet<String>();
//add elemets

if(st.contains("aks") ){
  //do something
}

I want a JavaScript/dojo equivalent of the above code.

Answer 1

I've written a JavaScript HashSet implementation that does what you want and allows any object to be a member of the set: http://code.google.com/p/jshashtable

However, if you just need to store strings, you could do something more simply by storing set members as property names of a normal Object. For example:

function StringSet() {
    var setObj = {}, val = {};

    this.add = function(str) {
        setObj[str] = val;
    };

    this.contains = function(str) {
        return setObj[str] === val;
    };

    this.remove = function(str) {
        delete setObj[str];
    };

    this.values = function() {
        var values = [];
        for (var i in setObj) {
            if (setObj[i] === val) {
                values.push(i);
            }
        }
        return values;
    };
}

A note about the implementation: val is an object used internally by the StringSet implementation that is unique to each set. Comparing property values of the object whose property names make up the set (setObj) against val eliminates the need for a hasOwnProperty() check and guarantees that only strings that have been added to the set will show up in values.

Example usage:

var set = new StringSet();
set.add("foo");
set.add("bar");

alert(set.contains("foo")); // true
alert(set.contains("baz")); // false

set.values(); // ["foo", "bar"], though not necessarily in that order
set.remove("foo");
set.values(); // ["bar"]

Answer 2

Why not use a normal object and check if a key exists with JavaScript's hasOwnProperty?

var x = {};
x['key'] = 'val';
x.hasOwnProperty('key'); // true //
x.hasOwnProperty('key2'); // false //

And here is a more advanced use case:

var x = {};
var prefix = 'item_';
for(var i=0;i<10;i++){
   x[prefix+i] = 'value '+(i+1);
}
x.hasOwnProperty('item_6'); // true //
x.hasOwnProperty('other key'); // false //

Removing items can be done like this:

delete x['key'];

Answer 3

No Dojo needed, this is native to Javascript. Use Objects. Sounds like you only need the keys, not the values. Lookup is constant time.

var st = {'aks':1, 'foo':1, 'bar':1};  // or could start with empty {}. 1 could be any value of any type, it's just short.

//add elements
st.baz = 1;

//or load up dynamically

myArrayOfStrings.forEach(function(key){
 st[key] = 1;
});


if("aks" in st){
  //do something
}

Answer 4

Possibly with an associative array / Hashtable / dictionary (I don't know how it's called exactly), using the set elements as keys and "anything else" as values.

insert: mySet[key] = "Whatever";

delete: mySet[key] = null;

check: if (mySet[key] != null) { ... }

Answer 5

Hash is good candidate for implementing Set. You could create a set using a function like that:

function set () {
    var result = {};
    for (var i = 0; i < arguments.length; i++) result[arguments[i]] = true;
    return result;
}

For instance:

x = set([1,2,2,4])
x[1] #==> true
x[3] #==> false
x[5] = true; # add element to the set
x[5] = false; # remove element from the set

Answer 6

Sets don't have keys. They only have set of values, but maps have pairs of key/value entities.

As a result, you have 2 options. Each of them has its drawbacks and advantages:

1. You can use as described above JavaScript object. Actually it is a map/associative array/hash table. One of its advantage - you can guarantee with this kind of structure that keys - are unique items. Its drawback connected to the issue - you have to keep some extra information that you don't need at all. Values of maps. trues or some other values. It does not matter. Why do you need them?

2. To resolve the previous disadvantage you may consider using JavaScript arrays. But, you'll have to write some wrappers so arrays's behavior will look like sets behavior. Also operations that will search by the uniqueId will be slower than the same ones for hashtables cause you'll have to iterate via all items of an array.

So, I think you should prefer hashtables to arrays, examples you can find in other posts. But probably you should consider changing of your data structure. don't keep uniqueId as keys with unselerss values if its possible. Let your unique ids point to some real objects for which these unique ids are used.

PS: one more thing. Arrays are also objects actually. As a result they can be used as hashtables/maps too.