How to customize object equality for JavaScript Set

Question

New ES 6 (Harmony) introduces new Set object. Identity algorithm used by Set is similar to === operator and so not much suitable for comparing objects:

var set = new Set();
set.add({a:1});
set.add({a:1});
console.log([...set.values()]); // Array [ Object, Object ]

How to customize equality for Set objects in order to do deep object comparison? Is there anything like Java equals(Object)?

Answer 1

Update 3/2022

There is currently a proposal to add Records and Tuples (basically immutable Objects and Arrays) to Javascript. In that proposal, it offers direct comparison of Records and Tuples using === or !== where it compares values, not just object references AND relevant to this answer both Set and Map objects would use the value of the Record or Tuple in key comparisons/lookups which would solve what is being asked for here.

Since the Records and Tuples are immutable (can't be modified) and because they are easily compared by value (by their contents, not just their object reference), it allows Maps and Sets to use object contents as keys and the proposed spec explicitly names this feature for Sets and Maps.

This original question asked for customizability of a Set comparison in order to support deep object comparison. This doesn't propose customizability of the Set comparison, but it directly supports deep object comparison if you use the new Record or a Tuple instead of an Object or an Array and thus would solve the original problem here.

Note, this proposal advanced to Stage 2 in mid-2021. It has been moving forward recently, but is certainly not done.

Mozilla work on this new proposal can be tracked here.

---

Original Answer

The ES6 Set object does not have any compare methods or custom compare extensibility.

The .has(), .add() and .delete() methods work only off it being the same actual object or same value for a primitive and don't have a means to plug into or replace just that logic.

You could presumably derive your own object from a Set and replace .has(), .add() and .delete() methods with something that did a deep object comparison first to find if the item is already in the Set, but the performance would likely not be good since the underlying Set object would not be helping at all. You'd probably have to just do a brute force iteration through all existing objects to find a match using your own custom compare before calling the original .add().

Here's some info from this article and discussion of ES6 features:

5.2 Why can’t I configure how maps and sets compare keys and values?

Question: It would be nice if there were a way to configure what map keys and what set elements are considered equal. Why isn’t there?

Answer: That feature has been postponed, as it is difficult to implement properly and efficiently. One option is to hand callbacks to collections that specify equality.

Another option, available in Java, is to specify equality via a method that object implement (equals() in Java). However, this approach is problematic for mutable objects: In general, if an object changes, its “location” inside a collection has to change, as well. But that’s not what happens in Java. JavaScript will probably go the safer route of only enabling comparison by value for special immutable objects (so-called value objects). Comparison by value means that two values are considered equal if their contents are equal. Primitive values are compared by value in JavaScript.

Answer 2

As mentioned in jfriend00's answer customization of equality relation is probably not possible.

Following code presents an outline of computationally efficient (but memory expensive) workaround:

class GeneralSet {

    constructor() {
        this.map = new Map();
        this[Symbol.iterator] = this.values;
    }

    add(item) {
        this.map.set(item.toIdString(), item);
    }

    values() {
        return this.map.values();
    }

    delete(item) {
        return this.map.delete(item.toIdString());
    }

    // ...
}

Each inserted element has to implement toIdString() method that returns string. Two objects are considered equal if and only if their toIdString methods returns same value.

Answer 3

As the top answer mentions, customizing equality is problematic for mutable objects. The good news is (and I'm surprised no one has mentioned this yet) there's a very popular library called immutable-js that provides a rich set of immutable types which provide the deep value equality semantics you're looking for.

Here's your example using immutable-js:

const { Map, Set } = require('immutable');
var set = new Set();
set = set.add(Map({a:1}));
set = set.add(Map({a:1}));
console.log([...set.values()]); // [Map {"a" => 1}]

Answer 4

To add to the answers here, I went ahead and implemented a Map wrapper that takes a custom hash function, a custom equality function, and stores distinct values that have equivalent (custom) hashes in buckets.

Predictably, it turned out to be slower than czerny's string concatenation method.

Full source here: https://github.com/makoConstruct/ValueMap

Answer 5

Maybe you can try to use JSON.stringify() to do deep object comparison.

for example :

const arr = [
  {name:'a', value:10},
  {name:'a', value:20},
  {name:'a', value:20},
  {name:'b', value:30},
  {name:'b', value:40},
  {name:'b', value:40}
];

const names = new Set();
const result = arr.filter(item => !names.has(JSON.stringify(item)) ? names.add(JSON.stringify(item)) : false);

console.log(result);

Answer 6

Comparing them directly seems not possible, but JSON.stringify works if the keys just were sorted. As I pointed out in a comment

JSON.stringify({a:1, b:2}) !== JSON.stringify({b:2, a:1});

But we can work around that with a custom stringify method. First we write the method

Custom Stringify

Object.prototype.stringifySorted = function(){
    let oldObj = this;
    let obj = (oldObj.length || oldObj.length === 0) ? [] : {};
    for (let key of Object.keys(this).sort((a, b) => a.localeCompare(b))) {
        let type = typeof (oldObj[key])
        if (type === 'object') {
            obj[key] = oldObj[key].stringifySorted();
        } else {
            obj[key] = oldObj[key];
        }
    }
    return JSON.stringify(obj);
}

The Set

Now we use a Set. But we use a Set of Strings instead of objects

let set = new Set()
set.add({a:1, b:2}.stringifySorted());

set.has({b:2, a:1}.stringifySorted());
// returns true

Get all the values

After we created the set and added the values, we can get all values by

let iterator = set.values();
let done = false;
while (!done) {
  let val = iterator.next();

  if (!done) {
    console.log(val.value);
  }
  done = val.done;
}

Here's a link with all in one file http://tpcg.io/FnJg2i

Answer 7

For Typescript users the answers by others (especially czerny) can be generalized to a nice type-safe and reusable base class:

/**
 * Map that stringifies the key objects in order to leverage
 * the javascript native Map and preserve key uniqueness.
 */
abstract class StringifyingMap<K, V> {
    private map = new Map<string, V>();
    private keyMap = new Map<string, K>();

    has(key: K): boolean {
        let keyString = this.stringifyKey(key);
        return this.map.has(keyString);
    }
    get(key: K): V {
        let keyString = this.stringifyKey(key);
        return this.map.get(keyString);
    }
    set(key: K, value: V): StringifyingMap<K, V> {
        let keyString = this.stringifyKey(key);
        this.map.set(keyString, value);
        this.keyMap.set(keyString, key);
        return this;
    }

    /**
     * Puts new key/value if key is absent.
     * @param key key
     * @param defaultValue default value factory
     */
    putIfAbsent(key: K, defaultValue: () => V): boolean {
        if (!this.has(key)) {
            let value = defaultValue();
            this.set(key, value);
            return true;
        }
        return false;
    }

    keys(): IterableIterator<K> {
        return this.keyMap.values();
    }

    keyList(): K[] {
        return [...this.keys()];
    }

    delete(key: K): boolean {
        let keyString = this.stringifyKey(key);
        let flag = this.map.delete(keyString);
        this.keyMap.delete(keyString);
        return flag;
    }

    clear(): void {
        this.map.clear();
        this.keyMap.clear();
    }

    size(): number {
        return this.map.size;
    }

    /**
     * Turns the `key` object to a primitive `string` for the underlying `Map`
     * @param key key to be stringified
     */
    protected abstract stringifyKey(key: K): string;
}

Example implementation is then this simple: just override the stringifyKey method. In my case I stringify some uri property.

class MyMap extends StringifyingMap<MyKey, MyValue> {
    protected stringifyKey(key: MyKey): string {
        return key.uri.toString();
    }
}

Example usage is then as if this was a regular Map<K, V>.

const key1 = new MyKey(1);
const value1 = new MyValue(1);
const value2 = new MyValue(2);

const myMap = new MyMap();
myMap.set(key1, value1);
myMap.set(key1, value2); // native Map would put another key/value pair

myMap.size(); // returns 1, not 2

Answer 8

As other guys said there is no native method can do it by far. But if you would like to distinguish an array with your custom comparator, you can try to do it with the reduce method.

function distinct(array, equal) {
  // No need to convert it to a Set object since it may give you a wrong signal that the set can work with your objects.
  return array.reduce((p, c) => {
    p.findIndex((element) => equal(element, c)) > -1 || p.push(c);
    return p;
  }, []);
}

// You can call this method like below,
const users = distinct(
    [
      {id: 1, name: "kevin"},
      {id: 2, name: "sean"},
      {id: 1, name: "jerry"}
    ],
    (a, b) => a.id === b.id
);
...

Answer 9

A good stringification method for the special but frequent case of a TypedArray as Set/Map key is using

const key = String.fromCharCode(...new Uint16Array(myArray.buffer));

It generates the shortest possible unique string that can be easily converted back. However this is not always a valid UTF-16 string for display concerning Low and High Surrogates. Set and Map seem to ignore surrogate validity. As measured in Firefox and Chrome, the spread operator performs slowly. If your myArray has fixed size, it executes faster when you write:

const a = new Uint16Array(myArray.buffer);  // here: myArray = Uint32Array(2) = 8 bytes
const key = String.fromCharCode(a[0],a[1],a[2],a[3]);  // 8 bytes too

Probably the most valuable advantage of this method of key-building: It works for Float32Array and Float64Array without any rounding side-effect. Note that +0 and -0 are then different. Infinities are same. Silent NaNs are same. Signaling NaNs are different depending on their signal (never seen in vanilla JavaScript).

Answer 10

To someone who found this question on Google (as me) wanting to get a value of a Map using an object as Key:

Warning: this answer will not work with all objects

var map = new Map<string,string>();

map.set(JSON.stringify({"A":2} /*string of object as key*/), "Worked");

console.log(map.get(JSON.stringify({"A":2}))||"Not worked");

Output:

Worked