So passen Sie die Objektgleichheit für JavaScript Set an

166

Mit dem neuen ES 6 (Harmony) wird ein neues Set- Objekt eingeführt. Der von Set verwendete Identitätsalgorithmus ähnelt dem ===Operator und ist daher für den Vergleich von Objekten nicht besonders geeignet:

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

Wie kann ich die Gleichheit für Set-Objekte anpassen, um einen tiefen Objektvergleich durchzuführen? Gibt es so etwas wie Java equals(Object)?

czerny
quelle
3
Was meinst du mit "Gleichheit anpassen"? Javascript erlaubt keine Überladung des ===Operators, daher gibt es keine Möglichkeit, den Operator zu überladen . Das ES6-Set-Objekt verfügt über keine Vergleichsmethoden. Die .has()Methode und die .add()Methode funktionieren nur, wenn es sich um dasselbe tatsächliche Objekt oder denselben Wert für ein Grundelement handelt.
jfriend00
12
Mit "Gleichheit anpassen" meine ich jede Art und Weise, wie Entwickler bestimmte Objekte definieren können, die als gleich oder nicht gleich angesehen werden sollen.
Czerny

Antworten:

107

Das ES6- SetObjekt verfügt über keine Vergleichsmethoden oder benutzerdefinierte Vergleichserweiterbarkeit.

Die .has(), .add()und .delete()Methoden funktionieren nur ab es das gleiche eigentliche Objekt oder denselben Wert für ein primitives Wesen und haben keine Mittel , um Stecker in oder ersetzen Sie einfach die Logik.

Vermutlich könnten Sie Ihr eigenes Objekt von a ableiten und Methoden Setersetzen .has(), die zuerst einen umfassenden Objektvergleich durchgeführt haben, um festzustellen, ob sich das Element bereits im Set befindet. Die Leistung wäre jedoch wahrscheinlich nicht gut, da das zugrunde liegende Objekt nicht hilfreich wäre überhaupt. Sie müssten wahrscheinlich nur eine Brute-Force-Iteration durch alle vorhandenen Objekte durchführen, um eine Übereinstimmung mit Ihrem eigenen benutzerdefinierten Vergleich zu finden, bevor Sie das Original aufrufen ..add().delete()Set.add()

Hier einige Informationen aus diesem Artikel und eine Diskussion der ES6-Funktionen:

5.2 Warum kann ich nicht konfigurieren, wie Maps und Sets Schlüssel und Werte vergleichen?

Frage: Es wäre schön, wenn es eine Möglichkeit gäbe, zu konfigurieren, welche Map-Schlüssel und welche Set-Elemente als gleich angesehen werden. Warum gibt es nicht?

Antwort: Diese Funktion wurde verschoben, da es schwierig ist, sie ordnungsgemäß und effizient zu implementieren. Eine Möglichkeit besteht darin, Rückrufe an Sammlungen zu übergeben, in denen Gleichheit angegeben ist.

Eine weitere in Java verfügbare Option besteht darin, die Gleichheit über eine Methode anzugeben, die das Objekt implementiert (equals () in Java). Dieser Ansatz ist jedoch für veränderbare Objekte problematisch: Wenn sich ein Objekt ändert, muss sich im Allgemeinen auch seine „Position“ innerhalb einer Sammlung ändern. Aber das passiert in Java nicht. JavaScript wird wahrscheinlich den sichereren Weg gehen, nur den Vergleich nach Wert für spezielle unveränderliche Objekte (sogenannte Wertobjekte) zu ermöglichen. Wertvergleich bedeutet, dass zwei Werte als gleich angesehen werden, wenn ihr Inhalt gleich ist. Primitive Werte werden in JavaScript nach Wert verglichen.

jfriend00
quelle
4
Artikelreferenz zu diesem speziellen Problem hinzugefügt. Es sieht so aus, als ob die Herausforderung darin besteht, mit einem Objekt umzugehen, das zum Zeitpunkt des Hinzufügens zum Set genau mit einem anderen Objekt identisch war, jetzt jedoch geändert wurde und nicht mehr mit diesem Objekt identisch ist. Ist es in der Setoder nicht?
jfriend00
3
Warum nicht einen einfachen GetHashCode oder ähnliches implementieren?
Jamby
@Jamby - Das wäre ein interessantes Projekt, um einen Hash zu erstellen, der alle Arten von Eigenschaften und Hashes in der richtigen Reihenfolge behandelt und sich mit Zirkelverweisen usw. befasst.
jfriend00
1
@ Jamby Auch mit einer Hash-Funktion muss man sich noch mit Kollisionen auseinandersetzen. Sie verschieben nur das Gleichstellungsproblem.
Mpen
5
@mpen Das stimmt nicht, ich erlaube dem Entwickler, seine eigene Hash-Funktion für seine spezifischen Klassen zu verwalten, was in fast allen Fällen das Kollisionsproblem verhindert, da der Entwickler die Art der Objekte kennt und einen guten Schlüssel ableiten kann. In jedem anderen Fall auf die aktuelle Vergleichsmethode zurückgreifen. Lot von Sprachen bereits tun, js nicht.
Jamby
28

Wie in der Antwort von jfriend00 erwähnt, ist eine Anpassung der Gleichheitsbeziehung wahrscheinlich nicht möglich .

Der folgende Code enthält einen Überblick über die rechnerisch effiziente (aber speicherintensive) Problemumgehung :

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

    // ...
}

Jedes eingefügte Element muss eine toIdString()Methode implementieren , die eine Zeichenfolge zurückgibt. Zwei Objekte werden genau dann als gleich angesehen, wenn ihre toIdStringMethoden denselben Wert zurückgeben.

czerny
quelle
Sie können den Konstruktor auch eine Funktion übernehmen lassen, die Elemente auf Gleichheit vergleicht. Dies ist gut, wenn Sie möchten, dass diese Gleichheit ein Merkmal der Menge und nicht der darin verwendeten Objekte ist.
Ben J
1
@BenJ Wenn Sie eine Zeichenfolge generieren und in eine Map einfügen möchten, verwendet Ihre Javascript-Engine auf diese Weise eine ~ O (1) -Suche im nativen Code, um den Hash-Wert Ihres Objekts zu suchen, während das Akzeptieren einer Gleichheitsfunktion erzwingen würde um einen linearen Scan des Sets durchzuführen und jedes Element zu überprüfen.
Jamby
3
Eine Herausforderung bei dieser Methode besteht darin, dass meiner Meinung nach davon ausgegangen wird, dass der Wert von item.toIdString()unveränderlich ist und sich nicht ändern kann. Denn wenn dies möglich ist, GeneralSetkann das mit "doppelten" Elementen leicht ungültig werden. Eine solche Lösung wäre also nur auf bestimmte Situationen beschränkt, in denen die Objekte selbst während der Verwendung des Satzes nicht geändert werden oder in denen ein ungültiger Satz keine Konsequenz hat. All diese Probleme erklären wahrscheinlich weiter, warum das ES6-Set diese Funktionalität nicht verfügbar macht, da es wirklich nur unter bestimmten Umständen funktioniert.
jfriend00
Ist es möglich .delete(), dieser Antwort die richtige Implementierung hinzuzufügen ?
Jlewkovich
1
@JLewkovich sicher
czerny
6

Wie in der Top-Antwort erwähnt, ist das Anpassen der Gleichheit für veränderbare Objekte problematisch. Die gute Nachricht ist (und ich bin überrascht, dass dies noch niemand erwähnt hat), dass es eine sehr beliebte Bibliothek namens immutable-js gibt , die eine Vielzahl unveränderlicher Typen bietet, die die von Ihnen gesuchte tiefe Gleichheitssemantik bieten.

Hier ist Ihr Beispiel mit unveränderlichen-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}]
Russell Davis
quelle
10
Wie ist die Leistung von unveränderlichem -s Set / Map mit nativem Set / Map zu vergleichen?
Frankster
5

Um die Antworten hier zu ergänzen, habe ich einen Map-Wrapper implementiert, der eine benutzerdefinierte Hash-Funktion und eine benutzerdefinierte Gleichheitsfunktion verwendet und unterschiedliche Werte mit äquivalenten (benutzerdefinierten) Hashes in Buckets speichert.

Vorhersehbar stellte sich heraus, dass es langsamer war als die String-Verkettungsmethode von czerny .

Vollständige Quelle hier: https://github.com/makoConstruct/ValueMap

Mako
quelle
"String-Verkettung"? Ist seine Methode nicht eher wie "String Surrogating" (wenn Sie ihm einen Namen geben wollen)? Oder gibt es einen Grund, warum Sie das Wort "Verkettung" verwenden? Ich bin neugierig ;-)
Binki
@binki Dies ist eine gute Frage, und ich denke, die Antwort bringt einen guten Punkt auf den Punkt, für den ich eine Weile gebraucht habe. Wenn Sie einen Hash-Code berechnen, wird normalerweise HashCodeBuilder ausgeführt, der die Hash-Codes einzelner Felder multipliziert und nicht garantiert eindeutig ist (daher ist eine benutzerdefinierte Gleichheitsfunktion erforderlich). Wenn jedoch eine ID - String zu erzeugen verketten Sie die ID - Strings einzelner Felder, die garantiert eindeutig (und damit keine Gleichheit Funktion erforderlich)
Pace
Also, wenn Sie eine als Pointdefiniert haben, { x: number, y: number }dann ist Ihre id stringwahrscheinlich x.toString() + ',' + y.toString().
Pace
Es ist eine Strategie, die ich zuvor angewendet habe, Ihren Gleichstellungsvergleich zu einem Wert zu machen, der garantiert nur dann variiert, wenn die Dinge als ungleich angesehen werden sollten. Manchmal ist es einfacher, über solche Dinge nachzudenken. In diesem Fall generieren Sie eher Schlüssel als Hashes . Solange Sie einen Schlüsselableiter haben, der einen Schlüssel in einer Form ausgibt, die vorhandene Tools mit einer Wertgleichheit unterstützen, die fast immer endet String, können Sie den gesamten Hashing- und Bucketing-Schritt wie gesagt überspringen und direkt a verwenden Mapoder sogar ein einfaches Objekt alten Stils in Bezug auf den abgeleiteten Schlüssel.
Binki
1
Wenn Sie bei der Implementierung eines Schlüsselableiters tatsächlich die Verkettung von Zeichenfolgen verwenden, sollten Sie darauf achten, dass Zeichenfolgeneigenschaften möglicherweise besonders behandelt werden müssen, wenn sie einen beliebigen Wert annehmen dürfen. Wenn Sie beispielsweise {x: '1,2', y: '3'}und haben {x: '1', y: '2,3'}, String(x) + ',' + String(y)wird für beide Objekte der gleiche Wert ausgegeben. Eine sicherere Option, vorausgesetzt, Sie können sich darauf verlassen JSON.stringify(), deterministisch zu sein, besteht darin, die Escapezeichenfolge zu nutzen und JSON.stringify([x, y])stattdessen zu verwenden.
Binki
3

Ein direkter Vergleich scheint nicht möglich zu sein, aber JSON.stringify funktioniert, wenn die Schlüssel nur sortiert wurden. Wie ich in einem Kommentar betonte

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

Aber wir können das mit einer benutzerdefinierten Stringify-Methode umgehen. Zuerst schreiben wir die Methode

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

Der Satz

Jetzt benutzen wir ein Set. Wir verwenden jedoch eine Reihe von Zeichenfolgen anstelle von Objekten

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

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

Holen Sie sich alle Werte

Nachdem wir die Menge erstellt und die Werte hinzugefügt haben, können wir alle Werte von abrufen

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

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

Hier ist ein Link mit allen in einer Datei http://tpcg.io/FnJg2i

relief.melone
quelle
"Wenn die Schlüssel sortiert sind" ist ein großes Wenn, insbesondere für komplexe Objekte
Alexander Mills
Genau deshalb habe ich diesen Ansatz gewählt;)
Relief.melone
2

Vielleicht können Sie versuchen, einen JSON.stringify()tiefen Objektvergleich durchzuführen.

zum Beispiel :

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
quelle
2
Dies kann funktionieren, muss aber nicht als JSON.stringify ({a: 1, b: 2})! == JSON.stringify ({b: 2, a: 1}) erfolgen, wenn alle Objekte von Ihrem Programm im selben erstellt werden damit du in Sicherheit bist. Aber keine wirklich sichere Lösung im Allgemeinen
Relief.melone
1
Ah ja, "konvertiere es in einen String". Javascript Antwort für alles.
Timmmm
2

Für Typescript-Benutzer können die Antworten anderer (insbesondere von czerny ) auf eine nette typsichere und wiederverwendbare Basisklasse verallgemeinert werden:

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

Die Beispielimplementierung ist dann so einfach: Überschreiben Sie einfach die stringifyKeyMethode. In meinem Fall stringifiziere ich eine uriEigenschaft.

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

Beispielgebrauch ist dann, als ob dies ein regulärer war 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
Jan Dolejsi
quelle
-1

Erstellen Sie einen neuen Satz aus der Kombination beider Sätze und vergleichen Sie dann die Länge.

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 ist gleich set2 = true

set1 ist gleich set4 = false

Stefan Musarra
quelle
2
Bezieht sich diese Antwort auf die Frage? Die Frage betrifft die Gleichheit von Elementen in Bezug auf eine Instanz der Set-Klasse. Diese Frage scheint die Gleichheit zweier Set-Instanzen zu diskutieren.
Czerny
@czerny Sie sind richtig - ich habe ursprünglich diese Stackoverflow-Frage angezeigt, bei der die oben beschriebene Methode verwendet werden könnte: stackoverflow.com/questions/6229197/…
Stefan Musarra
-2

Für jemanden, der diese Frage bei Google gefunden hat (wie ich), der einen Wert einer Karte mit einem Objekt als Schlüssel erhalten möchte:

Warnung: Diese Antwort funktioniert nicht mit allen Objekten

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

Ausgabe:

Hat funktioniert

DigaoParceiro
quelle