220

I'm working in JavaScript. I'd like to store a list of unique, unordered string values, with the following properties:

  1. a fast way to ask 'is A in the list'?
  2. a fast way to do 'delete A from the list if it exists in the list'
  3. a fast way to do 'add A to the list if it is not already present'.

What I really want is a set. Any suggestions for the best way to mimic a set in JavaScript?

This question recommends using an Object, with the keys storing properties, and the values all set to true: is that a sensible way?

Community
  • 1
  • 1
Richard
  • 31,629
  • 29
  • 108
  • 145
  • 2
    possible duplicate of [JavaScript implementation of a set data structure](http://stackoverflow.com/questions/2523436/javascript-implementation-of-a-set-data-structure) and http://stackoverflow.com/questions/4343746/ – Matt Ball Oct 31 '11 at 19:00
  • 1
    [ES6 has native sets](http://stackoverflow.com/a/27588953/1090562) – Salvador Dali Jan 19 '16 at 22:42

7 Answers7

263

If you are programming in an ES6-capable environment (such as node.js, a specific browser with the ES6 capabilities you need or transpiling ES6 code for your environment), then you can use the Set object built into ES6. It has very nice capabilities and can be used as is right in your environment.


For many simple things in an ES5 environment, using an Object works very well. If obj is your object and A is a variable that has the value you want to operate on in the set, then you can do these:

Initialization code:

// create empty object
var obj = {};

// or create an object with some items already in it
var obj = {"1":true, "2":true, "3":true, "9":true};

Question 1: Is A in the list:

if (A in obj) {
    // put code here
}

Question 2: Delete 'A' from the list if it's there:

delete obj[A];

Question 3: Add 'A' to the list if it wasn't already there

obj[A] = true;

For completeness, the test for whether A is in the list is a little safer with this:

if (Object.prototype.hasOwnProperty.call(obj, A))
    // put code here
}

because of potential conflict between built-in methods and/or properties on the base Object like the constructor property.


Sidebar on ES6: The current working version of ECMAScript 6 or somethings called ES 2015 has a built-in Set object. It is implemented now in some browsers. Since browser availability changes over time, you can look at the line for Set in this ES6 compatibility table to see the current status for browser availability.

One advantage of the built-in Set object is that it doesn't coerce all keys to a string like the Object does so you can have both 5 and "5" as separate keys. And, you can even use Objects directly in the set without a string conversion. Here's an article that describes some of the capabilities and MDN's documentation on the Set object.

I have now written a polyfill for the ES6 set object so you could start using that now and it will automatically defer to the built-in set object if the browser supports it. This has the advantage that you're writing ES6 compatible code that will work all the way back to IE7. But, there are some downsides. The ES6 set interface takes advantage of the ES6 iterators so you can do things like for (item of mySet) and it will automatically iterate through the set for you. But, this type of language feature cannot be implemented via polyfill. You can still iterate an ES6 set without using the new ES6 languages features, but frankly without the new language features, it isn't as convenient as the other set interface I include below.

You can decide which one works best for you after looking at both. The ES6 set polyfill is here: https://github.com/jfriend00/ES6-Set.

FYI, in my own testing, I've noticed that the Firefox v29 Set implementation is not fully up-to-date on the current draft of the spec. For example, you can't chain .add() method calls like the spec describes and my polyfill supports. This is probably a matter of a specification in motion as it is not yet finalized.


Pre-Built Set objects: If you want an already built object that has methods for operating on a set that you can use in any browser, you can use a series of different pre-built objects that implement different types of sets. There is a miniSet which is small code that implements the basics of a set object. It also has a more feature rich set object and several derivations including a Dictionary (let's you store/retrieve a value for each key) and an ObjectSet (let's you keep a set of objects - either JS objects or DOM objects where you either supply the function that generates a unique key for each one or the ObjectSet will generate the key for you).

Here's a copy of the code for the miniSet (most up-to-date code is here on github).

"use strict";
//-------------------------------------------
// Simple implementation of a Set in javascript
//
// Supports any element type that can uniquely be identified
//    with its string conversion (e.g. toString() operator).
// This includes strings, numbers, dates, etc...
// It does not include objects or arrays though
//    one could implement a toString() operator
//    on an object that would uniquely identify
//    the object.
// 
// Uses a javascript object to hold the Set
//
// This is a subset of the Set object designed to be smaller and faster, but
// not as extensible.  This implementation should not be mixed with the Set object
// as in don't pass a miniSet to a Set constructor or vice versa.  Both can exist and be
// used separately in the same project, though if you want the features of the other
// sets, then you should probably just include them and not include miniSet as it's
// really designed for someone who just wants the smallest amount of code to get
// a Set interface.
//
// s.add(key)                      // adds a key to the Set (if it doesn't already exist)
// s.add(key1, key2, key3)         // adds multiple keys
// s.add([key1, key2, key3])       // adds multiple keys
// s.add(otherSet)                 // adds another Set to this Set
// s.add(arrayLikeObject)          // adds anything that a subclass returns true on _isPseudoArray()
// s.remove(key)                   // removes a key from the Set
// s.remove(["a", "b"]);           // removes all keys in the passed in array
// s.remove("a", "b", ["first", "second"]);   // removes all keys specified
// s.has(key)                      // returns true/false if key exists in the Set
// s.isEmpty()                     // returns true/false for whether Set is empty
// s.keys()                        // returns an array of keys in the Set
// s.clear()                       // clears all data from the Set
// s.each(fn)                      // iterate over all items in the Set (return this for method chaining)
//
// All methods return the object for use in chaining except when the point
// of the method is to return a specific value (such as .keys() or .isEmpty())
//-------------------------------------------


// polyfill for Array.isArray
if(!Array.isArray) {
    Array.isArray = function (vArg) {
        return Object.prototype.toString.call(vArg) === "[object Array]";
    };
}

function MiniSet(initialData) {
    // Usage:
    // new MiniSet()
    // new MiniSet(1,2,3,4,5)
    // new MiniSet(["1", "2", "3", "4", "5"])
    // new MiniSet(otherSet)
    // new MiniSet(otherSet1, otherSet2, ...)
    this.data = {};
    this.add.apply(this, arguments);
}

MiniSet.prototype = {
    // usage:
    // add(key)
    // add([key1, key2, key3])
    // add(otherSet)
    // add(key1, [key2, key3, key4], otherSet)
    // add supports the EXACT same arguments as the constructor
    add: function() {
        var key;
        for (var i = 0; i < arguments.length; i++) {
            key = arguments[i];
            if (Array.isArray(key)) {
                for (var j = 0; j < key.length; j++) {
                    this.data[key[j]] = key[j];
                }
            } else if (key instanceof MiniSet) {
                var self = this;
                key.each(function(val, key) {
                    self.data[key] = val;
                });
            } else {
                // just a key, so add it
                this.data[key] = key;
            }
        }
        return this;
    },
    // private: to remove a single item
    // does not have all the argument flexibility that remove does
    _removeItem: function(key) {
        delete this.data[key];
    },
    // usage:
    // remove(key)
    // remove(key1, key2, key3)
    // remove([key1, key2, key3])
    remove: function(key) {
        // can be one or more args
        // each arg can be a string key or an array of string keys
        var item;
        for (var j = 0; j < arguments.length; j++) {
            item = arguments[j];
            if (Array.isArray(item)) {
                // must be an array of keys
                for (var i = 0; i < item.length; i++) {
                    this._removeItem(item[i]);
                }
            } else {
                this._removeItem(item);
            }
        }
        return this;
    },
    // returns true/false on whether the key exists
    has: function(key) {
        return Object.prototype.hasOwnProperty.call(this.data, key);
    },
    // tells you if the Set is empty or not
    isEmpty: function() {
        for (var key in this.data) {
            if (this.has(key)) {
                return false;
            }
        }
        return true;
    },
    // returns an array of all keys in the Set
    // returns the original key (not the string converted form)
    keys: function() {
        var results = [];
        this.each(function(data) {
            results.push(data);
        });
        return results;
    },
    // clears the Set
    clear: function() {
        this.data = {}; 
        return this;
    },
    // iterate over all elements in the Set until callback returns false
    // myCallback(key) is the callback form
    // If the callback returns false, then the iteration is stopped
    // returns the Set to allow method chaining
    each: function(fn) {
        this.eachReturn(fn);
        return this;
    },
    // iterate all elements until callback returns false
    // myCallback(key) is the callback form
    // returns false if iteration was stopped
    // returns true if iteration completed
    eachReturn: function(fn) {
        for (var key in this.data) {
            if (this.has(key)) {
                if (fn.call(this, this.data[key], key) === false) {
                    return false;
                }
            }
        }
        return true;
    }
};

MiniSet.prototype.constructor = MiniSet;
HoldOffHunger
  • 18,769
  • 10
  • 104
  • 133
jfriend00
  • 683,504
  • 96
  • 985
  • 979
  • How do you get the size of the set? – manova Oct 30 '12 at 03:57
  • @manova - You would have to iterate the items in the set and count them with a `for (var x in obj)` loop. This type of data structure doesn't keep track of the count. – jfriend00 Oct 30 '12 at 04:26
  • 16
    This solves the question, but to be clear, this implementation _won't_ work for sets of things besides integer or strings. – mkirk Nov 13 '12 at 09:43
  • 3
    @mkirk - yes the item you are indexing in the set must have a string representation that can be the index key (e.g. it either is a string or has a toString() method that uniquely describes the item). – jfriend00 Nov 13 '12 at 13:46
  • 4
    To get the items in the list, you can use `Object.keys(obj)`. – Blixt Dec 05 '12 at 16:05
  • 3
    @Blixt - `Object.keys()` needs IE9, FF4, Safari 5, Opera 12 or higher. There's a polyfill for older browsers [here](https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Object/keys). – jfriend00 Dec 05 '12 at 16:46
  • If you're not supporting older browsers, you can create the *set* with `Object.create(null)`, and then be safe with using the `in` operator. – alex Mar 28 '13 at 03:03
  • See http://stackoverflow.com/questions/2673121/how-to-check-if-object-has-any-properties-in-javascript to do an isEmpty() – Sam Apr 09 '13 at 14:14
  • Added a `set` object with various methods as an alternative. – jfriend00 Apr 10 '13 at 01:12
  • 1
    Don't use `obj.hasOwnProperty(prop)` for membership checks. Use `Object.prototype.hasOwnProperty.call(obj, prop)` instead, which works even if the "set" contains the value `"hasOwnProperty"`. – davidchambers Jul 11 '13 at 22:33
  • @davidchambers - changes made to do hasOwnProperty() the way you suggested. – jfriend00 Jul 11 '13 at 23:18
  • key:value does not make sense for a set: a set is an unordered list of elements (with no value). The solution by Tobo is more correct – blueFast Feb 07 '14 at 10:46
  • @gonvaled - This was always meant to allow the value to be optional so it could be just a set of keys. I've tweaked the `add()` method to make that clearer. – jfriend00 Feb 07 '14 at 14:57
  • Added new arguments to `.add()` and to constructor so an array of keys can be specified. – jfriend00 Feb 07 '14 at 15:35
  • Added new operations for comparing two sets `s.union(t)`, `s.intersection(t)`, `s.difference(t)`, `s.issubset(t)`, `s.issuperset(t)`. – jfriend00 Feb 07 '14 at 16:43
  • Updated answer to include a link to a series of set objects that were derived from the original work in this answer and are [now on github](https://github.com/jfriend00/Javascript-Set). – jfriend00 Feb 26 '14 at 03:44
  • 1
    Updated answer to include information about the built-in `Set` object in ECMAScript 6 (early versions implemented so far in Firefox and Chrome). – jfriend00 Apr 27 '14 at 06:02
  • Added link to an ES6-compatible polyfill for the ES6 Set object. – jfriend00 May 30 '14 at 23:39
  • You should tell that `obj = {1,2}` does not create anything – Val Jul 05 '14 at 20:12
  • `if (Object.prototype.hasOwnProperty.call(obj, A)` is missing an end parenthesis. Shouldn't the expression be "!Object.prototype.hasOwnProperty.call(obj, A)", so you put your code when it isn't a class method/property? Thanks! – kapace Dec 10 '14 at 17:35
  • Any chance to update the answer to feature the built-in Set object first, since these days the recommended development practice is to use the native feature and transpile it to ES5 if necessary? – Dan Dascalescu Jun 06 '16 at 23:47
  • @DanDascalescu - I wouldn't necessarily say it's "universally recommended" for everyone writing in Javascript to transpile ES6 code to ES5. That is one approach and is great for some purposes. But, if you have a lightweight web page and just need one or two ES6 features, pulling in much of an ES6 polyfill library and transpiling may be a bit overkill for what you're doing. I will move the ES6 Set to a more prominent place if you're programming in an ES6-capable environment. – jfriend00 Jun 06 '16 at 23:57
  • http://kangax.github.io/compat-table/es6/ shows excellent browser support for `Set`. – Dan Dascalescu Jun 07 '16 at 00:00
  • @DanDascalescu - Unless you need to support IE and some older Android or IOS mobile devices (which many would). It is well supported in all the latest desktop browsers and in node.js 4+. So, for this you downvoted me? This is a 2011 answer that I've endeavored to keep relatively up-to-date (which is way more than most people do here), but not wholly rewrite every so often. Why the downvote? Because I disagree that everybody should code to ES6 and transpile? I reference the compatibility table in my answer and let the reader make their own choice. – jfriend00 Jun 07 '16 at 00:14
72

You can create an Object with no properties like

var set = Object.create(null)

which can act as a set and eliminates the need to use hasOwnProperty.


var set = Object.create(null); // create an object with no properties

if (A in set) { // 1. is A in the list
  // some code
}
delete set[a]; // 2. delete A from the list if it exists in the list 
set[A] = true; // 3. add A to the list if it is not already present
Thorben Croisé
  • 12,407
  • 8
  • 39
  • 50
  • Nice, but not sure why you say that "eliminates the need to use hasOwnProperty" – blueFast Feb 07 '14 at 10:26
  • 13
    If you just use `set = {}` it will inherit all the properties from Object (e.g. `toString`), so you will have to check for the payload of the set (properties you added) with `hasOwnProperty` in `if (A in set)` – Thorben Croisé Feb 07 '14 at 10:31
  • 6
    I did not know that it is possible to create a completely empty object. Thanks, your solution is very elegant. – blueFast Feb 07 '14 at 10:51
  • 1
    Interesting, but the downside of this is surely that you have to have `set[A]=true` statements for every element you wish to add instead of just one initialiser? – vogomatix Jun 19 '14 at 12:14
  • 1
    Not sure what you mean, but if you are referring to initialising a set by an already present set, you can do something along the lines of `s = Object.create(null);s["thorben"] = true;ss = Object.create(s)` – Thorben Croisé Jun 19 '14 at 20:39
  • I wasn't able to get `prototype`s working with this solution. e.g. adding a `size` to a set. – dnozay Jun 23 '14 at 18:54
  • fun fact d3.js implements a set this way https://github.com/mbostock/d3/blob/master/src/arrays/set.js#L10 – Will May 04 '15 at 07:43
  • Lets say you create an object this way, add a property, but then JSON.stringify it and then JSON.parse it again. Will it still be 'a completely empty object'? How is that possible – ErikAGriffin Jul 29 '15 at 13:01
  • Just try it! It will depend on the JSON.parse implementation actually. I guess if you parse something like "{'a': 1}" you get a JavaScript Object that inherits from Object, not from null – Thorben Croisé Jul 29 '15 at 13:36
  • Note that `Object.create(null)` does not work on IE9. (in case you must support it) – David Balažic Sep 15 '16 at 11:59
  • It would be nice if you could mention a way to iterate over the elements of the set. – Buge Feb 27 '17 at 01:34
23

As of ECMAScript 6, the Set data-structure is a built-in feature. Compatibility with node.js versions can be found here.

hymloth
  • 6,869
  • 5
  • 36
  • 47
  • 4
    Hello, just for clarity - it's 2014 now, is this still experimental in Chrome? If it is not, could you please edit your answer? Thanks – Karel Bílek Feb 17 '14 at 01:08
  • 1
    Yes, it is still experimental for Chrome. I believe that by the end of 2014, when ECMAScript is supposed to be 'officially' released, it will be supported. I'll then update my answer accordingly. – hymloth Feb 17 '14 at 10:08
  • OK, thanks for answering! (JavaScript answers get outdated pretty quickly.) – Karel Bílek Feb 17 '14 at 18:11
  • `' ' in new Set(['\t', ' '])` produces `false` as well as `1 in new Set([1,2])`. – Val Jul 05 '14 at 20:05
  • 1
    @Val `in` doesn't work because `Set` objects doesn't have its elements as properties, which would be bad because sets can have elements of any type, but properties are strings. You can use [`has`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/has): `Set([1,2]).has(1)` – Oriol Jul 26 '14 at 22:07
  • 1
    [Salvador Dali's answer](http://stackoverflow.com/a/27588953/1269037) is more comprehensive and up-to-date. – Dan Dascalescu Jun 06 '16 at 23:49
15

In ES6 version of Javascript you have built in type for set (check compatibility with your browser).

var numbers = new Set([1, 2, 4]); // Set {1, 2, 4}

To add an element to the set you simply use .add(), which runs in O(1) and either adds the element to set (if it does not exist) or does nothing if it is already there. You can add element of any type there (arrays, strings, numbers)

numbers.add(4); // Set {1, 2, 4}
numbers.add(6); // Set {1, 2, 4, 6}

To check the number of elements in the set, you can simply use .size. Also runs in O(1)

numbers.size; // 4

To remove the element from the set use .delete(). It returns true if the value was there (and was removed), and false if the value did not exist. Also runs in O(1).

numbers.delete(2); // true
numbers.delete(2); // false

To check whether the element exist in a set use .has(), which returns true if the element is in the set and false otherwise. Also runs in O(1).

numbers.has(3); // false
numbers.has(1); // true

In addition to methods you wanted, there are few additional one:

  • numbers.clear(); would just remove all elements from the set
  • numbers.forEach(callback); iterating through the values of the set in insertion order
  • numbers.entries(); create an iterator of all the values
  • numbers.keys(); returns the keys of the set which is the same as numbers.values()

There is also a Weakset which allows to add only object-type values.

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
10

I have started an implementation of Sets that currently works pretty well with numbers and strings. My main focus was the difference operation, so I tried to make it as efficient as I could. Forks and code reviews are welcome!

https://github.com/mcrisc/SetJS

mcrisc
  • 809
  • 1
  • 9
  • 19
  • wow this class is nuts! I would totally use this if I wasn't writing JavaScript inside CouchDB map/reduce functions! – benathon Sep 03 '12 at 07:13
9

I just noticed that d3.js library has implementation of sets, maps and other data structures. I can't argue about their efficiency but judging by the fact that it is a popular library it must be what you need.

The documentation is here

For convenience I copy from the link (the first 3 functions are those of interest)


  • d3.set([array])

Constructs a new set. If array is specified, adds the given array of string values to the returned set.

  • set.has(value)

Returns true if and only if this set has an entry for the specified value string.

  • set.add(value)

Adds the specified value string to this set.

  • set.remove(value)

If the set contains the specified value string, removes it and returns true. Otherwise, this method does nothing and returns false.

  • set.values()

Returns an array of the string values in this set. The order of the returned values is arbitrary. Can be used as a convenient way of computing the unique values for a set of strings. For example:

d3.set(["foo", "bar", "foo", "baz"]).values(); // "foo", "bar", "baz"

  • set.forEach(function)

Calls the specified function for each value in this set, passing the value as an argument. The this context of the function is this set. Returns undefined. The iteration order is arbitrary.

  • set.empty()

Returns true if and only if this set has zero values.

  • set.size()

Returns the number of values in this set.

kon psych
  • 626
  • 1
  • 11
  • 26
4

Yes, that's a sensible way--that's all an object is (well, for this use-case)--a bunch of keys/values with direct access.

You'd need to check to see if it's already there before adding it, or if you just need to indicate presence, "adding" it again doesn't actually change anything, it just sets it on the object again.

Dave Newton
  • 158,873
  • 26
  • 254
  • 302