Does JavaScript have an implementation of a set data structure?

Question

I'm looking for a decent implementation of a set data structure in JavaScript. It should be able to support elements that are plain JavaScript objects.

So far I only found Closure Library's structs.Set, but I don't like the fact that it modifies my data.

Solution 1

You could build a simple wrapper around the keys of a hash table provided by my jshashtable. I have one knocking around somewhere that I will dig out later.

UPDATE

I have completed and tested an implementation of HashSet and uploaded it to the jshashtable project on GitHub. You can download it or view the source.

var s = new HashSet();
var o1 = {name: "One"}, o2 = {name: "Two"};
s.add(o1);
s.add(o2);
s.values(); // Array containing o1 and o2

Solution 2

ECMAScript 6 has it

Spec: http://www.ecma-international.org/ecma-262/6.0/#sec-set-constructor

Usage: https://github.com/lukehoban/es6features#map--set--weakmap--weakset

Example:

var s = new Set()
s.add("hello").add("goodbye").add("hello")
s.size === 2
s.has("hello") === true

A module that implements it for browsers without support: https://github.com/medikoo/es6-set

Solution 3

I don't think there's a way to work with object's hash code other than store it in the object itself. Strictly speaking, it's possible to create a set class without hashing, using simple linear search, but this would hardly be efficient.

Solution 4

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.

Solution 5

Use the ECMAScript 2015 (ES6) standard Set Data structure really easy to use:

var mySet = new Set();

mySet.add(1);
mySet.add(5);
mySet.add("some text");
var o = {a: 1, b: 2};
mySet.add(o);

mySet.has(1); // true
mySet.has(3); // false, 3 has not been added to the set
mySet.has(5);              // true
mySet.has(Math.sqrt(25));  // true
mySet.has("Some Text".toLowerCase()); // true
mySet.has(o); // true

mySet.size; // 4

mySet.delete(5); // removes 5 from the set
mySet.has(5);    // false, 5 has been removed

mySet.size; // 3, we just removed one value

Update for those using AngularJs

Be aware that sets don't work with ng-repeat. So it is better you use an array and just apply a unique filter

View more solutions

Comments

[Amit Patil]

Indeed. There is no way to get an object's identity in JS other than to compare it with every other object.

[user187291]

can you explain how your library calculates object hash codes?

[Tim Down]

It's in the documentation, but in summary: the hash codes are strings, and you can provide a function to calculate hash codes to the Hashtable constructor (as well as a function that compares two object and decides if they're equal). Otherwise, it looks for a method called hashCode() on keys. As a last resort, it attempts to convert the key to a string using toString() or String(). If all your keys hash to the same value (e.g. "[object Object]") because you haven't used any of the above mechanisms then they'll all go into the same bucket and it has to use your simple linear search.

[Vatsal]

Are you sure, that insertion in Set runs in O(1) ? I am unable to find any implementation like this and which ever I found has a runtime of O(N) and the implementation had indexOf method which checks if the value exists in the array. I need to use it inside loop and hence I am hesitant of using indexOf method. Can you please point me any implementation or the resource you read it?

[Salvador Dali]

@Vatsal yes, it takes O(1) amortized time to insert an element to a set. I do not know where to find an implementation of sets in JS, but every elementary book in datastructures will confirm this. IndexOf is a method which operates on array, so there is no surprise that it takes O(n) time.

[Shanika Ediriweera]

This does not work with JS objects. Objects are kept as reference. Objects with same property values will be considered as two objects and added into the Set.

[sam]

Hi Tim, will this library store the following format in set: var o1 = {firstname: "John", lastname: "Doe"}, o2 = {firstname: "Eric", lastname: "Lencher"};