Best Practices zum Überschreiben von isEqual: und Hash

267

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 nameund überprüft datawerden. 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 hashVerfahren, außer Kraft gesetzt wird , dass nur nameund dataden Hash beeinflussen? Und wenn ja, wie würden Sie das machen? Fügen Sie einfach die Hashes von nameund 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.)

Dave Dribin
quelle
2
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)
Robert
Dokumentationslink ist tot, jetzt archiviert in Introspection
jedwidz

Antworten:

111

Beginnen mit

 NSUInteger prime = 31;
 NSUInteger result = 1;

Dann für jedes Primitiv, das Sie tun

 result = prime * result + var

Für Objekte verwenden Sie 0 für Null und ansonsten deren Hashcode.

 result = prime * result + [var hash];

Für Boolesche Werte verwenden Sie zwei verschiedene Werte

 result = prime * result + ((var)?1231:1237);

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.

tcurdt
quelle
9
Woher kam der 1231: 1237? Ich sehe es auch in Javas Boolean.hashCode (). Ist es magisch?
David Leonard
17
Es liegt in der Natur eines Hashing-Algorithmus, dass es zu Kollisionen kommt. Ich verstehe deinen Standpunkt also nicht, Paul.
tcurdt
85
Meiner Meinung nach antwortet diese Antwort nicht auf die eigentliche Frage (Best Practices zum Überschreiben des NSObject-Hashs). Es bietet nur einen bestimmten Hash-Algorithmus. Darüber hinaus macht es die spärliche Erklärung schwierig, ohne tiefes Wissen über die Angelegenheit zu verstehen, und kann dazu führen, dass Menschen sie verwenden, ohne zu wissen, was sie tun. Ich verstehe nicht, warum diese Frage so viele positive Stimmen hat.
Ricardo Sanchez-Saez
6
1. Problem - (int) ist klein und leicht zu überlaufen, verwenden Sie NSUInteger. 2. Problem - Wenn Sie das Ergebnis weiterhin mit jedem Variablen-Hash multiplizieren, läuft Ihr Ergebnis über. z.B. [NSString-Hash] erstellt große Werte. Wenn Sie mehr als 5 Variablen haben, kann dieser Algorithmus leicht überlaufen. Dies führt dazu, dass alles demselben Hash zugeordnet wird, was schlecht ist. Siehe meine Antwort: stackoverflow.com/a/4393493/276626
Paul Solt
10
@PaulSolt - Überlauf ist kein Problem beim Generieren eines Hashs, Kollision ist. Ein Überlauf macht eine Kollision jedoch nicht unbedingt wahrscheinlicher, und Ihre Aussage über einen Überlauf, der dazu führt, dass alles demselben Hash zugeordnet wird, ist einfach falsch.
DougW
81

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.

Brian B.
quelle
4
+1 Ausgezeichnete Antwort, verdient mehr positive Stimmen, zumal er tatsächlich über "Best Practices" und die Theorie spricht, warum ein guter (einzigartiger) Hash wichtig ist.
Quinn Taylor
30

Ein einfaches XOR über die Hashwerte kritischer Eigenschaften reicht in 99% der Fälle aus.

Beispielsweise:

- (NSUInteger)hash
{
    return [self.name hash] ^ [self.data hash];
}

Lösung gefunden unter http://nshipster.com/equality/ von Mattt Thompson (der diese Frage auch in seinem Beitrag verwies!)

Yariv Nissim
quelle
1
Das Problem bei dieser Antwort ist, dass primitive Werte überhaupt nicht berücksichtigt werden. Und primitive Werte können auch für das Hashing wichtig sein.
Vive
@Vive Die meisten dieser Probleme werden in Swift gelöst, aber diese Typen stellen normalerweise ihren eigenen Hash dar, da sie primitiv sind.
Yariv Nissim
1
Während Sie für Swift richtig sind, gibt es immer noch viele Projekte, die mit objc geschrieben wurden. Da Ihre Antwort dem Ziel gewidmet ist, ist sie zumindest eine Erwähnung wert.
Vive
Das gemeinsame XORing von Hash-Werten ist ein schlechter Rat, der zu vielen Hash-Kollisionen führt. Multiplizieren Sie stattdessen mit einer Primzahl und addieren Sie diese, wie in anderen Antworten angegeben.
Fisch
27

Ich fand diesen Thread äußerst hilfreich und lieferte alles, was ich brauchte, um meine isEqual:und hashMethoden mit einem Haken zu implementieren. Beim Testen von Objektinstanzvariablen im isEqual:Beispielcode werden verwendet:

if (![(id)[self name] isEqual:[aWidget name]])
    return NO;

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 NSStringInstanzvariablen Null war, daher lautete die obige Aussage:

if (![nil isEqual: nil])
    return NO;

und da nil auf jede methode reagiert, ist dies aber vollkommen legal

[nil isEqual: nil]

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:

if ([self name] != [aWidget name] && ![(id)[self name] isEqual:[aWidget name]])
    return NO;

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.

LavaSlider
quelle
20

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.

-(NSUInteger)hash {
    NSUInteger result = 1;
    NSUInteger prime = 31;
    NSUInteger yesPrime = 1231;
    NSUInteger noPrime = 1237;

    // Add any object that already has a hash function (NSString)
    result = prime * result + [self.myObject hash];

    // Add primitive variables (int)
    result = prime * result + self.primitiveVariable; 

    // Boolean values (BOOL)
    result = prime * result + (self.isSelected?yesPrime:noPrime);

    return result;
}
Paul Solt
quelle
3
Ein Problem hier: Ich bevorzuge die Punktsyntax, deshalb habe ich Ihre BOOL-Anweisung in (z result = prime * result + [self isSelected] ? yesPrime : noPrime;. B.) umgewandelt . Ich stellte dann fest, dass dies resultauf (z. B.) eingestellt war 1231, 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);
Ashley
12

Der einfache, aber ineffiziente Weg besteht darin, -hashfü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)

Jens Ayton
quelle
1
Sie sind genau richtig auf dem | =. Meinte das nicht wirklich so. :) + = und ^ = sind ziemlich gleichwertig. Wie gehen Sie mit nicht ganzzahligen Grundelementen wie double und float um?
Dave Dribin
Zufällige lustige Tatsache: Teste es auf Snow Leopard ... ;-)
Quinn Taylor
Er hat Recht damit, XOR anstelle von OR zu verwenden, um Felder zu einem Hash zu kombinieren. Verwenden Sie jedoch nicht den Rat von dem gleichen -hash Wert für jedes Objekt zurückkehrt - obwohl es leicht, es stark die Leistung verschlechtern kann etwas , das das Objekt Hash verwendet. Der Hash nicht haben , um für Objekte eindeutig sein , die nicht gleich sind, aber wenn man das erreichen kann, gibt es nichts Vergleichbares.
Quinn Taylor
Der offene Radarfehlerbericht ist geschlossen. openradar.me/4538282 Was bedeutet das?
JJD
JJD, der Fehler wurde in Mac OS X 10.6 behoben, wie Quinn angedeutet hat. (Beachten Sie, dass der Kommentar zwei Jahre alt ist.)
Jens Ayton
9

Denken Sie daran, dass Sie nur Hash bereitstellen müssen, der gleich ist, wenn er isEqualwahr ist. Wenn isEquales 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.

@interface CLPlacemark (equal)
- (BOOL)isEqual:(CLPlacemark*)other;
@end

@implementation CLPlacemark (equal)

...

-(NSUInteger) hash
{
    return self.name.hash;
}


@end

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

hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash

Auf diese Weise wird der Hash gleichmäßig verteilt.

Hash must be O(1), and not O(n)

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.

user4951
quelle
XORing-Hashwerte ergeben keine gleichmäßige Verteilung.
Fisch
7

Warten Sie, ein viel einfacherer Weg, dies zu tun, besteht sicherlich darin, zuerst - (NSString )descriptioneine 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:

- (NSUInteger)hash {
    return [[self description] 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

Jonathan Ellis
quelle
1
Dies setzt voraus, dass die Beschreibungsmethode eindeutig ist. Die Verwendung des Hashs der Beschreibung führt zu einer Abhängigkeit, die möglicherweise nicht offensichtlich ist, und zu einem höheren Kollisionsrisiko.
Paul Solt
1
+1 Upvoted. Das ist eine großartige Idee. Wenn Sie befürchten, dass Beschreibungen Kollisionen verursachen, können Sie diese überschreiben.
user4951
Danke Jim, ich werde nicht leugnen, dass dies ein bisschen ein Hack ist, aber es würde auf jeden Fall funktionieren, an den ich denken kann - und wie gesagt, vorausgesetzt, Sie überschreiben 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 nur hashdie NSString!
Jonathan Ellis
Upvoted, weil es eine nette Idee ist. Ich werde es jedoch nicht verwenden, da ich die zusätzlichen NSString-Zuweisungen fürchte.
Karwag
1
Dies ist keine generische Lösung, da die meisten Klassen descriptiondie 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!
Diogo T
5

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:

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if ([self class] != [object class])
        return false;
    MyWidget *other = (MyWidget *)object;
    if (_name == nil) {
        if (other->_name != nil)
            return false;
    }
    else if (![_name isEqual:other->_name])
        return false;
    if (_data == nil) {
        if (other->_data != nil)
            return false;
    }
    else if (![_data isEqual:other->_data])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = 1;
    result = prime * result + [_name hash];
    result = prime * result + [_data hash];
    return result;
}

Und für eine Unterklasse, YourWidgetdie eine Eigenschaft hinzufügt serialNo:

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if (![super isEqual:object])
        return false;
    if ([self class] != [object class])
        return false;
    YourWidget *other = (YourWidget *)object;
    if (_serialNo == nil) {
        if (other->_serialNo != nil)
            return false;
    }
    else if (![_serialNo isEqual:other->_serialNo])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = [super hash];
    result = prime * result + [_serialNo hash];
    return result;
}

Diese Implementierung vermeidet einige Fallstricke bei Unterklassen im Beispiel isEqual:von Apple:

  • Apples Klassentest other isKindOfClass:[self class]ist asymmetrisch für zwei verschiedene Unterklassen von MyWidget. Gleichheit muss symmetrisch sein: a = b genau dann, wenn b = a. Dies könnte leicht durch Ändern des Tests auf behoben werden other isKindOfClass:[MyWidget class], dann MyWidgetwären alle Unterklassen miteinander vergleichbar.
  • Die Verwendung eines isKindOfClass:Unterklassentests verhindert, dass Unterklassen isEqual: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 eine MyWidgetInstanz gleich zwei YourWidgetInstanzen ist, YourWidgetmüssen diese Instanzen gleich miteinander verglichen werden, auch wenn sich ihre Instanzen serialNounterscheiden.

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 jeder NSStringgleich mit jedem anderen NSStringmit derselben zugrunde liegenden Zeichenfolge verglichen werden, unabhängig von der NSString/ NSMutableStringUnterscheidung und auch unabhängig davon, welche privaten Klassen im NSStringKlassencluster 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 gekennzeichnet finalwerden. Objective-C hat jedoch keine Entsprechung.

jedwidz
quelle
@adubr Das wird in meinen letzten beiden Absätzen behandelt. Es ist nicht zentral, da MyWidgetes sich nicht um einen Klassencluster handelt.
jedwidz
5

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 ...

Schwa
quelle
2
Eine C ++ - Bibliothek, die sich auf eindeutige Hashes für einen void * -Schlüssel unter Verwendung einer Zufallszahl konzentriert (und sich auch nicht auf Objective-C-Objekte bezieht), ist hier wirklich kein hilfreicher Vorschlag. Die -hash-Methode sollte jedes Mal einen konsistenten Wert zurückgeben, da sie sonst völlig nutzlos ist. Wenn das Objekt einer Sammlung hinzugefügt wird, die -hash aufruft und jedes Mal einen neuen Wert zurückgibt, werden niemals Duplikate erkannt, und Sie können das Objekt auch nie aus der Sammlung abrufen. In diesem Fall unterscheidet sich der Begriff "Hash" von der Bedeutung in Sicherheit / Kryptographie.
Quinn Taylor
3
Murmhash ist keine kryptografische Hash-Funktion. Bitte überprüfen Sie Ihre Fakten, bevor Sie falsche Informationen veröffentlichen. Murmurhash könnte für Hashing benutzerdefinierte Objective-C - Klassen nützlich sein (insb. Wenn Sie eine Menge NSDatas haben beteiligt sind ) , weil es extrem schnell ist. Ich gebe Ihnen jedoch zu, dass es vielleicht nicht der beste Rat ist, jemandem zu geben, der "nur Ziel-c aufgreift", aber bitte beachten Sie mein Präfix in meiner ursprünglichen Antwort auf die Frage.
schwa
5

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.

Mipadi
quelle
1
zwischengespeicherter Link über archive.org: web.archive.org/web/20071013053633/http://www.geocities.com/…
Cobbal
4

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.

ceperry
quelle
Ich bin ein Cocoa / Objective C-Neuling, und diese Antwort und dieser Link haben mir wirklich geholfen, all die fortgeschritteneren Dinge oben bis zum Endergebnis durchzuschneiden - ich muss mich nicht um Hashes kümmern - nur die isEqual: -Methode implementieren. Vielen Dank!
John Gallagher
Verpassen Sie nicht den Link von @ ceperry. Der Artikel Equality vs Identityvon Karl Kraft ist wirklich gut.
JJD
6
@ John: Ich denke, Sie sollten den Artikel noch einmal lesen. Es wird sehr deutlich gesagt, dass "Instanzen, die gleich sind, gleiche Hashwerte haben müssen". Wenn Sie überschreiben isEqual:, müssen Sie auch überschreiben hash.
Steve Madsen
3

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
3

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:

NSArray *PropertyNamesFromObject(id object)
{
    unsigned int propertyCount = 0;
    objc_property_t * properties = class_copyPropertyList([object class], &propertyCount);
    NSMutableArray *propertyNames = [NSMutableArray arrayWithCapacity:propertyCount];

    for (unsigned int i = 0; i < propertyCount; ++i) {
        objc_property_t property = properties[i];
        const char * name = property_getName(property);
        NSString *propertyName = [NSString stringWithUTF8String:name];
        [propertyNames addObject:propertyName];
    }
    free(properties);
    return propertyNames;
}

BOOL IsEqualObjects(id object1, id object2)
{
    if (object1 == object2)
        return YES;
    if (!object1 || ![object2 isKindOfClass:[object1 class]])
        return NO;

    NSArray *propertyNames = PropertyNamesFromObject(object1);
    for (NSString *propertyName in propertyNames) {
        if (([object1 valueForKey:propertyName] != [object2 valueForKey:propertyName])
            && (![[object1 valueForKey:propertyName] isEqual:[object2 valueForKey:propertyName]])) return NO;
    }

    return YES;
}

NSUInteger MagicHash(id object)
{
    NSUInteger prime = 31;
    NSUInteger result = 1;

    NSArray *propertyNames = PropertyNamesFromObject(object);

    for (NSString *propertyName in propertyNames) {
        id value = [object valueForKey:propertyName];
        result = prime * result + [value hash];
    }

    return result;
}

Jetzt können Sie in Ihrer benutzerdefinierten Klasse einfach implementieren isEqual:und hash:

- (NSUInteger)hash
{
    return MagicHash(self);
}

- (BOOL)isEqual:(id)other
{
    return IsEqualObjects(self, other);
}
Johnboiles
quelle
2

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 :

Wenn einer Sammlung ein veränderbares Objekt hinzugefügt wird, das Hash-Werte verwendet, um die Position des Objekts in der Sammlung zu bestimmen, darf sich der von der Hash-Methode des Objekts zurückgegebene Wert nicht ändern, während sich das Objekt in der Sammlung befindet. Daher darf sich die Hash-Methode entweder nicht auf interne Statusinformationen des Objekts stützen, oder Sie müssen sicherstellen, dass sich die internen Statusinformationen des Objekts nicht ändern, während sich das Objekt in der Auflistung befindet. So kann beispielsweise ein veränderbares Wörterbuch in eine Hash-Tabelle eingefügt werden, Sie dürfen es jedoch nicht ändern, solange es sich dort befindet. (Beachten Sie, dass es schwierig sein kann zu wissen, ob sich ein bestimmtes Objekt in einer Sammlung befindet oder nicht.)

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.

user10345
quelle
1
Sie lesen die Hash-Dokumente falsch - es handelt sich im Wesentlichen um eine "Entweder-Oder" -Situation. Wenn sich das Objekt ändert, ändert sich im Allgemeinen auch der Hash. Dies ist wirklich eine Warnung an den Programmierer, dass, wenn sich der Hash infolge der Mutation eines Objekts ändert, das Ändern des Objekts, während es sich in einer Sammlung befindet, die den Hash verwendet, unerwartetes Verhalten verursacht. Wenn das Objekt in einer solchen Situation "sicher veränderbar" sein muss, haben Sie keine andere Wahl, als den Hash unabhängig vom veränderlichen Zustand zu machen. Diese besondere Situation klingt für mich seltsam, aber es gibt sicherlich seltene Situationen, in denen sie zutrifft.
Quinn Taylor
1

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.

Thibaud de Souza
quelle