Как настроить равенство объектов для JavaScript Set

167

Новый ES 6 (Гармония) представляет новый объект Set . Алгоритм идентификации, используемый Set, похож на ===оператор и поэтому мало подходит для сравнения объектов:

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

Как настроить равенство для объектов Set для глубокого сравнения объектов? Есть что-нибудь похожее на Java equals(Object)?

Черни
источник
3
Что вы подразумеваете под «настроить равенство»? Javascript не допускает перегрузку операторов, поэтому нет возможности перегрузить ===оператор. Установленный объект ES6 не имеет методов сравнения. .has()Метод и .add()методы работа только с нее быть тем же самым реальным объектом или же значением для примитивного.
jfriend00
12
Под «настроить равенство» я имею в виду любой способ, которым разработчик может определить определенную пару объектов, которые будут считаться равными или нет.
Черни,

Ответы:

107

Объект ES6 Setне имеет методов сравнения или настраиваемой расширяемости сравнения.

В .has(), .add()и .delete()методы работы только от него быть таким же реальным объектом или же значением для примитивного и не имеют средств для подключения к или заменить только что логика.

Вы могли бы предположительно получить свой собственный объект из a Setи replace .has(), .add()а .delete()методы - с чем-то, что сначала делало глубокое сравнение объектов, чтобы выяснить, есть ли уже элемент в наборе, но производительность, вероятно, не будет хорошей, так как базовый Setобъект не поможет вообще. Вероятно, вам придется просто выполнить итерацию методом грубой силы по всем существующим объектам, чтобы найти соответствие, используя собственное сравнение, прежде чем вызывать оригинал .add().

Вот некоторая информация из этой статьи и обсуждение возможностей ES6:

5.2 Почему я не могу настроить, как карты и наборы сравнивают ключи и значения?

Вопрос: Было бы хорошо, если бы был способ настроить, какие ключи карты и какие элементы набора считаются равными. Почему там нет?

Ответ: Эта функция была отложена, поскольку ее трудно реализовать должным образом и эффективно. Один из вариантов - передать обратные вызовы коллекциям, которые определяют равенство.

Другой вариант, доступный в Java, - указать равенство с помощью метода, который реализует объект (equals () в Java). Однако такой подход проблематичен для изменчивых объектов: в общем случае, если объект изменяется, его «местоположение» внутри коллекции также должно меняться. Но это не то, что происходит в Java. Скорее всего, JavaScript пойдет по более безопасному пути - разрешить сравнение только по значению для специальных неизменяемых объектов (так называемых объектов значений). Сравнение по значению означает, что два значения считаются равными, если их содержимое одинаково. Примитивные значения сравниваются по значению в JavaScript.

jfriend00
источник
4
Добавлена ​​ссылка на статью об этой конкретной проблеме. Похоже, задача состоит в том, как справиться с объектом, который был точно таким же, как и другой, в тот момент, когда он был добавлен в набор, но теперь был изменен и больше не совпадает с этим объектом. Это в Setили нет?
jfriend00
3
Почему бы не реализовать простой GetHashCode или аналогичный?
Джемби
@Jamby - Это был бы интересный проект по созданию хэша, который обрабатывает все типы свойств и свойства хеширования в правильном порядке, имеет дело с циклическими ссылками и так далее.
jfriend00
1
@Jamby Даже с хэш-функцией вам все равно приходится сталкиваться с коллизиями. Вы просто откладываете проблему равенства.
17
5
@mpen Это не правильно, я позволяю разработчику управлять своей собственной хеш-функцией для своих конкретных классов, что почти во всех случаях предотвращает проблему коллизий, поскольку разработчик знает природу объектов и может получить хороший ключ. В любом другом случае откат к текущему методу сравнения. Лот из языков уже сделать это, JS нет.
Jamby
28

Как упоминалось в ответе jfriend00, настройка отношения равенства, вероятно, невозможна .

Следующий код представляет схему вычислительно эффективного (но дорогостоящего) обходного пути :

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());
    }

    // ...
}

Каждый вставленный элемент должен реализовывать toIdString()метод, который возвращает строку. Два объекта считаются равными тогда и только тогда, когда их toIdStringметоды возвращают одно и то же значение.

Черни
источник
Вы также можете заставить конструктор взять функцию, которая сравнивает элементы на равенство. Это хорошо, если вы хотите, чтобы это равенство было свойством набора, а не объектов, используемых в нем.
Бен Джей
1
@BenJ Смысл генерации строки и помещения ее в Map заключается в том, что ваш движок Javascript будет использовать поиск ~ O (1) в нативном коде для поиска значения хеш-функции вашего объекта, в то время как принятие функции равенства приведет к сделать линейное сканирование набора и проверить каждый элемент.
Джемби
3
Одна из проблем этого метода заключается в том, что, как мне кажется, предполагается, что значение item.toIdString()является инвариантным и не может измениться. Потому что, если это возможно, то он GeneralSetможет легко стать недействительным с «дублирующимися» элементами в нем. Таким образом, подобное решение будет ограничено только некоторыми ситуациями, в которых сами объекты не изменяются при использовании набора или когда набор, который становится недействительным, не имеет значения. Все эти проблемы, вероятно, дополнительно объясняют, почему ES6 Set не предоставляет эту функциональность, потому что он действительно работает только при определенных обстоятельствах.
jfriend00
Можно ли добавить правильную реализацию .delete()этого ответа?
jlewkovich
1
@JLewkovich уверен
Черни
6

Как отмечается в верхнем ответе , настройка равенства проблематична для изменчивых объектов. Хорошая новость (и я удивлен, что никто еще не упомянул об этом) есть очень популярная библиотека под названием immutable-js, которая предоставляет богатый набор неизменяемых типов, которые обеспечивают семантику глубокого равенства равенства, которую вы ищете.

Вот ваш пример использования 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}]
Рассел Дэвис
источник
10
Как производительность набора / карты immutable-js сравнивается с характеристиками набора / карты?
Франкстер
5

Чтобы добавить здесь ответы, я пошел дальше и реализовал оболочку Map, которая принимает пользовательскую хеш-функцию, пользовательскую функцию равенства и хранит различные значения, которые имеют эквивалентные (пользовательские) хеши в контейнерах.

Как и ожидалось, он оказался медленнее, чем метод конкатенации строк czerny .

Полный источник здесь: https://github.com/makoConstruct/ValueMap

мако
источник
«Конкатенация строк»? Разве его метод больше не похож на «суррогатную струну» (если вы собираетесь дать ей имя)? Или есть причина, по которой вы используете слово «конкатенация»? Мне любопытно ;-)
Бинки
@binki Это хороший вопрос, и я думаю, что ответ поднимает хорошую мысль, что мне понадобилось время, чтобы понять. Как правило, при вычислении хеш-кода выполняется что-то вроде HashCodeBuilder, который умножает хеш-коды отдельных полей и не гарантируется, что он будет уникальным (отсюда необходимость в пользовательской функции равенства). Однако при генерации строки идентификатора вы объединяете строки идентификаторов отдельных полей, которые гарантированно являются уникальными (и, следовательно, не требуется функция равенства)
Pace
Так что, если у вас есть Pointопределенное как, { x: number, y: number }то, id stringвероятно, ваш x.toString() + ',' + y.toString().
Pace
Проведение сравнения на основе равенства дает некоторую ценность, которая гарантированно будет меняться только в тех случаях, когда вещи должны рассматриваться как неравные. Это стратегия, которую я использовал ранее. Иногда легче думать о таких вещах. В этом случае вы генерируете ключи, а не хэши . Пока у вас есть ключ-производник, который выводит ключ в форме, которую существующие инструменты поддерживают с равным стилем значения, который почти всегда заканчивается String, тогда вы можете пропустить весь шаг хеширования и сегментирования, как вы сказали, и просто напрямую использовать Mapили даже простой объект старого стиля в терминах производного ключа.
Бинки
1
Если вы действительно используете конкатенацию строк в своей реализации производного ключа, нужно быть осторожным, так как свойства строки могут нуждаться в особой обработке, если им разрешено принимать любое значение. Например, если у вас есть {x: '1,2', y: '3'}и {x: '1', y: '2,3'}, то String(x) + ',' + String(y)выведите одинаковое значение для обоих объектов. Более безопасный вариант, при условии, что вы можете рассчитывать на JSON.stringify()детерминированность, состоит в том, чтобы использовать JSON.stringify([x, y])вместо него экранирование и использование строки .
Бинки
3

Сравнивать их напрямую кажется невозможным, но JSON.stringify работает, если ключи были отсортированы. Как я указал в комментарии

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

Но мы можем обойти это с помощью специального метода stringify. Сначала мы пишем метод

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);
}

Набор

Теперь мы используем набор. Но мы используем набор строк вместо объектов

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

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

Получить все значения

После того, как мы создали набор и добавили значения, мы можем получить все значения

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

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

Вот ссылка со всеми в одном файле http://tpcg.io/FnJg2i

relief.melone
источник
«если ключи отсортированы» - это большое «если», особенно для сложных объектов
Александр Миллс
именно поэтому я и выбрал этот подход;)
рельеф. melone
2

Может быть, вы можете попробовать использовать JSON.stringify()для глубокого сравнения объектов.

например :

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);

GuaHsu
источник
2
Это может работать, но не обязательно как JSON.stringify ({a: 1, b: 2})! == JSON.stringify ({b: 2, a: 1}), если все объекты созданы вашей программой в одном и том же Прикажите, что вы в безопасности. Но не совсем безопасное решение в целом
рельеф. Melone
1
Ах да, "преобразовать его в строку". Javascript ответ для всего.
Тимммм
2

Для пользователей Typescript ответы других (особенно czerny ) можно обобщить в хороший типобезопасный и многократно используемый базовый класс:

/**
 * 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;
}

В этом случае реализация примера так проста: просто переопределите stringifyKeyметод. В моем случае я даю некоторое uriсвойство.

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

Пример использования тогда, как если бы это было обычным 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
Ян Долейси
источник
-1

Создайте новый набор из комбинации обоих наборов, затем сравните длину.

let set1 = new Set([1, 2, 'a', 'b'])
let set2 = new Set([1, 'a', 'a', 2, 'b'])
let set4 = new Set([1, 2, 'a'])

function areSetsEqual(set1, set2) {
  const set3 = new Set([...set1], [...set2])
  return set3.size === set1.size && set3.size === set2.size
}

console.log('set1 equals set2 =', areSetsEqual(set1, set2))
console.log('set1 equals set4 =', areSetsEqual(set1, set4))

set1 равно set2 = true

set1 равно set4 = false

Стефан Мусарра
источник
2
Этот ответ связан с вопросом? Речь идет о равенстве элементов относительно экземпляра класса Set. Этот вопрос, кажется, обсуждает равенство двух экземпляров Set.
Черни,
@czerny Вы правы - я первоначально просматривал этот вопрос stackoverflow, где можно использовать описанный выше метод: stackoverflow.com/questions/6229197/…
Стефан
-2

Для того, кто нашел этот вопрос в Google (как я) и хотел получить значение карты, используя объект в качестве ключа:

Предупреждение: этот ответ не будет работать со всеми объектами

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");

Вывод:

Работал

DigaoParceiro
источник