Wie überschreiben Sie isEqual:
Objective-C richtig ? Der "Haken" scheint zu sein, dass zwei Objekte, wenn sie gleich sind (wie durch die isEqual:
Methode bestimmt), denselben Hashwert haben müssen.
Der Abschnitt Introspection des Cocoa Fundamentals Guide enthält ein Beispiel zum Überschreiben isEqual:
einer Klasse mit dem Namen MyWidget
:
- (BOOL)isEqual:(id)other {
if (other == self)
return YES;
if (!other || ![other isKindOfClass:[self class]])
return NO;
return [self isEqualToWidget:other];
}
- (BOOL)isEqualToWidget:(MyWidget *)aWidget {
if (self == aWidget)
return YES;
if (![(id)[self name] isEqual:[aWidget name]])
return NO;
if (![[self data] isEqualToData:[aWidget data]])
return NO;
return YES;
}
Es prüft die Zeigergleichheit, dann die Klassengleichheit und vergleicht schließlich die Objekte mit isEqualToWidget:
, wobei nur die Eigenschaften name
und überprüft data
werden. Was das Beispiel nicht zeigt, ist das Überschreiben hash
.
Nehmen wir an, es gibt andere Eigenschaften, die beispielsweise die Gleichheit nicht beeinflussen age
. Sollte nicht das hash
Verfahren, außer Kraft gesetzt wird , dass nur name
und data
den Hash beeinflussen? Und wenn ja, wie würden Sie das machen? Fügen Sie einfach die Hashes von name
und hinzu data
? Zum Beispiel:
- (NSUInteger)hash {
NSUInteger hash = 0;
hash += [[self name] hash];
hash += [[self data] hash];
return hash;
}
Ist das ausreichend Gibt es eine bessere Technik? Was ist, wenn Sie Primitive haben int
? Konvertieren Sie sie in NSNumber
, um ihren Hash zu bekommen? Oder Strukturen wie NSRect
?
( Brain Fart : Ursprünglich schrieb "bitwise OR" sie zusammen mit |=
. Gemeint hinzufügen.)
quelle
if (![other isKindOfClass:[self class]])
- Dies bedeutet technisch gesehen, dass Gleichheit nicht kommutativ ist. Dh A = B bedeutet nicht B = A (z. B. wenn eine eine Unterklasse der anderen ist)Antworten:
Beginnen mit
Dann für jedes Primitiv, das Sie tun
Für Objekte verwenden Sie 0 für Null und ansonsten deren Hashcode.
Für Boolesche Werte verwenden Sie zwei verschiedene Werte
Erklärung und Namensnennung
Dies ist nicht die Arbeit von tcurdt, und in den Kommentaren wurde um weitere Erklärung gebeten, daher halte ich eine Bearbeitung zur Zuschreibung für fair.
Dieser Algorithmus wurde im Buch "Effective Java" populär gemacht. Das entsprechende Kapitel finden Sie derzeit hier online . In diesem Buch wurde der Algorithmus populär gemacht, der heute in einer Reihe von Java-Anwendungen (einschließlich Eclipse) Standard ist. Es leitet sich jedoch aus einer noch älteren Implementierung ab, die Dan Bernstein oder Chris Torek unterschiedlich zugeschrieben wird. Dieser ältere Algorithmus schwebte ursprünglich im Usenet herum, und eine bestimmte Zuordnung ist schwierig. Zum Beispiel enthält dieser Apache-Code einige interessante Kommentare (Suche nach ihren Namen), die auf die Originalquelle verweisen.
Unterm Strich ist dies ein sehr alter, einfacher Hashing-Algorithmus. Es ist nicht das leistungsfähigste und es ist nicht einmal mathematisch bewiesen, dass es ein "guter" Algorithmus ist. Aber es ist einfach und viele Leute haben es lange Zeit mit guten Ergebnissen verwendet, so dass es viel historische Unterstützung hat.
quelle
Ich nehme nur Objective-C selbst auf, daher kann ich nicht speziell für diese Sprache sprechen, aber in den anderen Sprachen, die ich verwende, wenn zwei Instanzen "gleich" sind, müssen sie denselben Hash zurückgeben - sonst haben Sie alle Arten von Problemen beim Versuch, sie als Schlüssel in einer Hashtabelle (oder in Sammlungen vom Typ eines Wörterbuchs) zu verwenden.
Wenn andererseits zwei Instanzen nicht gleich sind, können sie denselben Hash haben oder auch nicht - es ist am besten, wenn sie dies nicht tun. Dies ist der Unterschied zwischen einer O (1) -Suche in einer Hash-Tabelle und einer O (N) -Suche. Wenn alle Ihre Hashes kollidieren, ist die Suche in Ihrer Tabelle möglicherweise nicht besser als die Suche in einer Liste.
In Bezug auf Best Practices sollte Ihr Hash eine zufällige Verteilung von Werten für seine Eingabe zurückgeben. Dies bedeutet, dass Sie beispielsweise sicherstellen müssen, dass die von diesen Werten zurückgegebenen Hashes gleichmäßig über den gesamten Bereich möglicher Hash-Werte verteilt sind, wenn Sie ein Double haben, die meisten Ihrer Werte jedoch zwischen 0 und 100 liegen . Dies wird Ihre Leistung erheblich verbessern.
Es gibt eine Reihe von Hashing-Algorithmen, darunter mehrere, die hier aufgeführt sind. Ich versuche zu vermeiden, neue Hash-Algorithmen zu erstellen, da dies große Auswirkungen auf die Leistung haben kann. Daher ist es eine gute Möglichkeit, die vorhandenen Hash-Methoden zu verwenden und eine bitweise Kombination wie in Ihrem Beispiel zu verwenden, um dies zu vermeiden.
quelle
Beispielsweise:
Lösung gefunden unter http://nshipster.com/equality/ von Mattt Thompson (der diese Frage auch in seinem Beitrag verwies!)
quelle
Ich fand diesen Thread äußerst hilfreich und lieferte alles, was ich brauchte, um meine
isEqual:
undhash
Methoden mit einem Haken zu implementieren. Beim Testen von Objektinstanzvariablen imisEqual:
Beispielcode werden verwendet:Dies schlug wiederholt ohne Fehler fehl ( dh es wurde NO zurückgegeben ), als ich wusste, dass die Objekte in meinen Komponententests identisch waren. Der Grund war, dass eine der
NSString
Instanzvariablen Null war, daher lautete die obige Aussage:und da nil auf jede methode reagiert, ist dies aber vollkommen legal
Returns nil , die ist , NO , so dass , wenn sowohl das Objekt und das eine A hatte getestet nil Objekt sie nicht gleich angesehen werden würde ( dh ,
isEqual:
zurückkehren würde NO ).Diese einfache Lösung bestand darin, die if-Anweisung in Folgendes zu ändern:
Auf diese Weise wird bei gleichen Adressen der Methodenaufruf übersprungen, unabhängig davon, ob beide null sind oder beide auf dasselbe Objekt zeigen. Wenn jedoch entweder nicht null ist oder sie auf verschiedene Objekte zeigen, wird der Komparator entsprechend aufgerufen.
Ich hoffe, das erspart jemandem ein paar Minuten Kopfkratzen.
quelle
Die Hash-Funktion sollte einen semi-eindeutigen Wert erstellen, der wahrscheinlich nicht mit dem Hash-Wert eines anderen Objekts kollidiert oder mit diesem übereinstimmt.
Hier ist die vollständige Hash-Funktion, die an die Instanzvariablen Ihrer Klassen angepasst werden kann. Es verwendet NSUInteger anstelle von int, um die Kompatibilität mit 64/32-Bit-Anwendungen zu gewährleisten.
Wenn das Ergebnis für verschiedene Objekte 0 wird, besteht die Gefahr, dass Hashes kollidieren. Kollidierende Hashes können zu unerwartetem Programmverhalten führen, wenn Sie mit einigen der Auflistungsklassen arbeiten, die von der Hash-Funktion abhängen. Stellen Sie sicher, dass Sie Ihre Hash-Funktion vor der Verwendung testen.
quelle
result = prime * result + [self isSelected] ? yesPrime : noPrime;
. B.) umgewandelt . Ich stellte dann fest, dass diesresult
auf (z. B.) eingestellt war1231
, ich nehme an, dass der?
Operator Vorrang hat. Ich habe das Problem durch Hinzufügen von Klammern behoben:result = prime * result + ([self isSelected] ? yesPrime : noPrime);
Der einfache, aber ineffiziente Weg besteht darin,
-hash
für jede Instanz den gleichen Wert zurückzugeben. Andernfalls müssen Sie Hash nur basierend auf Objekten implementieren, die die Gleichheit beeinflussen. Dies ist schwierig, wenn Sie laxe Vergleiche in verwenden-isEqual:
(z. B. Vergleiche zwischen Zeichenfolgen ohne Berücksichtigung der Groß- und Kleinschreibung). Für Ints können Sie im Allgemeinen das Int selbst verwenden, es sei denn, Sie vergleichen mit NSNumbers.Verwenden Sie jedoch nicht | =, da es sonst gesättigt wird. Verwenden Sie stattdessen ^ =.
Zufällige lustige Tatsache :
[[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]
, aber[[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]
. (rdar: // 4538282, geöffnet seit 05. Mai 2006)quelle
Denken Sie daran, dass Sie nur Hash bereitstellen müssen, der gleich ist, wenn er
isEqual
wahr ist. WennisEqual
es falsch ist, muss der Hash nicht ungleich sein, obwohl dies vermutlich der Fall ist. Daher:Halte den Hash einfach. Wählen Sie eine Mitgliedsvariable (oder wenige Mitgliedervariablen) aus, die am ausgeprägtesten ist.
Für CLPlacemark reicht beispielsweise nur der Name aus. Ja, es gibt 2 oder 3 verschiedene CLPlacemark mit genau demselben Namen, aber diese sind selten. Verwenden Sie diesen Hash.
...
Beachten Sie, dass ich nicht die Stadt, das Land usw. spezifiziere. Der Name ist genug. Vielleicht der Name und die CLLocation.
Hash sollte gleichmäßig verteilt sein. Sie können also mehrere Elementvariablen mit dem Caret ^ (xor-Zeichen) kombinieren.
Also ist es so etwas wie
Auf diese Weise wird der Hash gleichmäßig verteilt.
Was tun in Array?
Wieder einfach. Sie müssen nicht alle Mitglieder des Arrays hashen. Genug, um das erste Element, das letzte Element, die Anzahl, vielleicht einige mittlere Elemente zu hashen, und das war's.
quelle
Warten Sie, ein viel einfacherer Weg, dies zu tun, besteht sicherlich darin, zuerst
- (NSString )description
eine Zeichenfolgendarstellung Ihres Objektstatus zu überschreiben und bereitzustellen (Sie müssen den gesamten Status Ihres Objekts in dieser Zeichenfolge darstellen).Geben Sie dann einfach die folgende Implementierung von an
hash
:Dies basiert auf dem Prinzip, dass "wenn zwei Zeichenfolgenobjekte gleich sind (wie durch die Methode isEqualToString: bestimmt), sie denselben Hashwert haben müssen".
Quelle: NSString-Klassenreferenz
quelle
description
, sehe ich nicht, warum dies unterlegen ist eine der höher bewerteten Lösungen. Vielleicht nicht die mathematisch eleganteste Lösung, sollte aber den Trick machen. Wie Brian B. feststellt (die am meisten positiv bewertete Antwort an dieser Stelle): "Ich versuche zu vermeiden, neue Hash-Algorithmen zu erstellen" - stimmte zu! - Ich nurhash
dieNSString
!description
die Zeigeradresse enthalten. Dies führt also zu zwei verschiedenen Instanzen derselben Klasse, die mit unterschiedlichem Hash gleich sind, was gegen die Grundannahme verstößt, dass zwei gleiche Objekte denselben Hash haben!Die Gleichheits- und Hash-Verträge sind in der Java-Welt gut spezifiziert und gründlich recherchiert (siehe Antwort von @ mipardi), aber für Objective-C sollten dieselben Überlegungen gelten.
Eclipse generiert diese Methoden zuverlässig in Java. Hier ist ein Eclipse-Beispiel, das von Hand auf Objective-C portiert wurde:
Und für eine Unterklasse,
YourWidget
die eine Eigenschaft hinzufügtserialNo
:Diese Implementierung vermeidet einige Fallstricke bei Unterklassen im Beispiel
isEqual:
von Apple:other isKindOfClass:[self class]
ist asymmetrisch für zwei verschiedene Unterklassen vonMyWidget
. Gleichheit muss symmetrisch sein: a = b genau dann, wenn b = a. Dies könnte leicht durch Ändern des Tests auf behoben werdenother isKindOfClass:[MyWidget class]
, dannMyWidget
wären alle Unterklassen miteinander vergleichbar.isKindOfClass:
Unterklassentests verhindert, dass UnterklassenisEqual:
mit einem verfeinerten Gleichheitstest überschrieben werden. Dies liegt daran, dass Gleichheit transitiv sein muss: Wenn a = b und a = c, dann ist b = c. Wenn eineMyWidget
Instanz gleich zweiYourWidget
Instanzen ist,YourWidget
müssen diese Instanzen gleich miteinander verglichen werden, auch wenn sich ihre InstanzenserialNo
unterscheiden.Das zweite Problem kann behoben werden, indem Objekte nur dann als gleich betrachtet werden, wenn sie genau derselben Klasse angehören, daher der
[self class] != [object class]
Test hier. Für typische Anwendungsklassen scheint dies der beste Ansatz zu sein.Es gibt jedoch sicherlich Fälle, in denen der
isKindOfClass:
Test vorzuziehen ist. Dies ist typischer für Framework-Klassen als für Anwendungsklassen. Zum Beispiel sollte jederNSString
gleich mit jedem anderenNSString
mit derselben zugrunde liegenden Zeichenfolge verglichen werden, unabhängig von derNSString
/NSMutableString
Unterscheidung und auch unabhängig davon, welche privaten Klassen imNSString
Klassencluster beteiligt sind.In solchen Fällen
isEqual:
sollte ein genau definiertes, gut dokumentiertes Verhalten vorliegen, und es sollte klargestellt werden, dass Unterklassen dies nicht überschreiben können. In Java kann die Einschränkung "Keine Überschreibung" erzwungen werden, indem die Methoden equals und hashcode als gekennzeichnetfinal
werden. Objective-C hat jedoch keine Entsprechung.quelle
MyWidget
es sich nicht um einen Klassencluster handelt.Dies beantwortet Ihre Frage (überhaupt) nicht direkt, aber ich habe MurmurHash bereits verwendet, um Hashes zu generieren: murmurhash
Ich denke, ich sollte erklären, warum: Murmeln ist blutig schnell ...
quelle
Ich habe festgestellt, dass diese Seite eine hilfreiche Anleitung zum Überschreiben von Methoden vom Typ "Gleich" und "Hash" ist. Es enthält einen anständigen Algorithmus zur Berechnung von Hash-Codes. Die Seite ist auf Java ausgerichtet, aber es ist ziemlich einfach, sie an Objective-C / Cocoa anzupassen.
quelle
Ich bin auch ein Objective C-Neuling, aber ich habe hier in Objective C einen ausgezeichneten Artikel über Identität und Gleichheit gefunden . Nach meiner Lektüre können Sie möglicherweise nur die Standard-Hash-Funktion (die eine eindeutige Identität bereitstellen sollte) beibehalten und die isEqual-Methode implementieren, um Datenwerte zu vergleichen.
quelle
Equality vs Identity
von Karl Kraft ist wirklich gut.isEqual:
, müssen Sie auch überschreibenhash
.Quinn ist einfach falsch, dass der Verweis auf den Murmeln-Hash hier nutzlos ist. Quinn hat Recht, dass Sie die Theorie hinter dem Hashing verstehen wollen. Das Murmeln destilliert einen Großteil dieser Theorie in eine Implementierung. Es lohnt sich herauszufinden, wie diese Implementierung auf diese bestimmte Anwendung angewendet werden kann.
Einige der wichtigsten Punkte hier:
Die Beispielfunktion von tcurdt legt nahe, dass '31' ein guter Multiplikator ist, weil es eine Primzahl ist. Man muss zeigen, dass Priming eine notwendige und ausreichende Bedingung ist. Tatsächlich sind 31 (und 7) wahrscheinlich keine besonders guten Primzahlen, da 31 == -1% 32. Ein ungerader Multiplikator mit etwa der Hälfte der gesetzten Bits und der Hälfte der freien Bits ist wahrscheinlich besser. (Die Murmel-Hash-Multiplikationskonstante hat diese Eigenschaft.)
Diese Art von Hash-Funktion wäre wahrscheinlich stärker, wenn der Ergebniswert nach dem Multiplizieren über eine Verschiebung und xor angepasst würde. Die Multiplikation führt tendenziell zu den Ergebnissen vieler Bitinteraktionen am oberen Ende des Registers und zu niedrigen Interaktionsergebnissen am unteren Ende des Registers. Die Verschiebung und xor erhöhen die Wechselwirkungen am unteren Ende des Registers.
Das Setzen des Anfangsergebnisses auf einen Wert, bei dem ungefähr die Hälfte der Bits Null und ungefähr die Hälfte der Bits Eins sind, wäre ebenfalls nützlich.
Es kann nützlich sein, vorsichtig mit der Reihenfolge zu sein, in der Elemente kombiniert werden. Man sollte wahrscheinlich zuerst Boolesche Werte und andere Elemente verarbeiten, bei denen die Werte nicht stark verteilt sind.
Es kann nützlich sein, am Ende der Berechnung einige zusätzliche Bit-Verwürfelungsstufen hinzuzufügen.
Ob der Murmel-Hash für diese Anwendung tatsächlich schnell ist oder nicht, ist eine offene Frage. Der Murmel-Hash mischt die Bits jedes Eingabeworts vor. Es können mehrere Eingabewörter parallel verarbeitet werden, wodurch ein Pipeline-CPU mit mehreren Ausgaben unterstützt wird.
quelle
Wenn wir die Antwort von @ tcurdt mit der Antwort von @ oscar-gomez kombinieren, um Eigenschaftsnamen zu erhalten , können wir eine einfache Drop-In-Lösung für isEqual und hash erstellen:
Jetzt können Sie in Ihrer benutzerdefinierten Klasse einfach implementieren
isEqual:
undhash
:quelle
Beachten Sie, dass sich der Hashwert nicht ändern darf, wenn Sie ein Objekt erstellen, das nach der Erstellung mutiert werden kann, wenn das Objekt in eine Sammlung eingefügt wird. In der Praxis bedeutet dies, dass der Hash-Wert ab dem Zeitpunkt der anfänglichen Objekterstellung festgelegt werden muss. Weitere Informationen finden Sie in der Apple-Dokumentation zur -hash-Methode des NSObject-Protokolls :
Das klingt für mich nach völliger Verrücktheit, da es Hash-Lookups möglicherweise effektiv weniger effizient macht, aber ich nehme an, es ist besser, auf Nummer sicher zu gehen und den Anweisungen in der Dokumentation zu folgen.
quelle
Es tut mir leid, wenn ich riskiere, hier einen kompletten Trottel zu klingen, aber ... ... niemand hat sich die Mühe gemacht zu erwähnen, dass Sie, um 'Best Practices' zu befolgen, definitiv keine gleichwertige Methode angeben sollten, die NICHT alle Daten berücksichtigt, die Ihrem Zielobjekt gehören, z. B. was auch immer Daten, die zu Ihrem Objekt aggregiert werden, sollten bei der Implementierung von equals berücksichtigt werden. Wenn Sie bei einem Vergleich nicht "Alter" berücksichtigen möchten, sollten Sie einen Komparator schreiben und diesen verwenden, um Ihre Vergleiche anstelle von "isEqual:" durchzuführen.
Wenn Sie eine isEqual: -Methode definieren, die einen Gleichheitsvergleich willkürlich durchführt, besteht das Risiko, dass diese Methode von einem anderen Entwickler oder sogar von Ihnen selbst missbraucht wird, sobald Sie die Wendung in Ihrer Gleichheitsinterpretation vergessen haben.
Ergo, obwohl dies eine großartige Frage und Antwort zum Thema Hashing ist, müssen Sie die Hashing-Methode normalerweise nicht neu definieren. Sie sollten stattdessen wahrscheinlich einen Ad-hoc-Komparator definieren.
quelle