Meilleures pratiques pour remplacer isEqual: et hachage

267

Comment remplacez-vous correctement isEqual:dans Objective-C? Le "catch" semble être que si deux objets sont égaux (comme déterminé par la isEqual:méthode), ils doivent avoir la même valeur de hachage.

La section Introspection du Cocoa Fundamentals Guide contient un exemple sur la façon de remplacer isEqual:, copié comme suit, pour une classe nommée 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;
}

Il vérifie l'égalité du pointeur, puis l'égalité des classes, et compare enfin les objets à l'aide isEqualToWidget:, qui vérifie uniquement les propriétés nameet data. Ce que l'exemple ne montre pas , c'est comment passer outre hash.

Supposons qu'il existe d'autres propriétés qui n'affectent pas l'égalité, par exemple age. Ne doit pas la hashméthode est surchargée de sorte que seule nameet dataaffecte le hachage? Et si oui, comment feriez-vous cela? Ajoutez simplement les hachages de nameet data? Par exemple:

- (NSUInteger)hash {
    NSUInteger hash = 0;
    hash += [[self name] hash];
    hash += [[self data] hash];
    return hash;
}

Est-ce suffisant? Existe-t-il une meilleure technique? Et si vous avez des primitives, comme int? Les convertir NSNumberpour obtenir leur hachage? Ou des structures comme NSRect?

( Brain fart : A l'origine écrit "bitwise OR" avec |=. Signifie ajouter.)

Dave Dribin
la source
2
if (![other isKindOfClass:[self class]])- Cela signifie techniquement que l'égalité ne sera pas commutative. C'est-à-dire A = B ne signifie pas B = A (par exemple si l'un est une sous-classe de l'autre)
Robert
Le lien vers la documentation est mort, maintenant archivé dans Introspection
jedwidz

Réponses:

111

Commencer avec

 NSUInteger prime = 31;
 NSUInteger result = 1;

Ensuite, pour chaque primitive que vous faites

 result = prime * result + var

Pour les objets, vous utilisez 0 pour nil et sinon leur code de hachage.

 result = prime * result + [var hash];

Pour les booléens, vous utilisez deux valeurs différentes

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

Explication et attribution

Ce n'est pas le travail de tcurdt, et les commentaires demandaient plus d'explications, donc je pense qu'une modification pour l'attribution est juste.

Cet algorithme a été popularisé dans le livre "Effective Java", et le chapitre correspondant est actuellement disponible en ligne ici . Ce livre a popularisé l'algorithme, qui est maintenant un défaut dans un certain nombre d'applications Java (y compris Eclipse). Il dérive cependant d'une implémentation encore plus ancienne, attribuée de diverses manières à Dan Bernstein ou Chris Torek. Cet ancien algorithme flottait à l'origine sur Usenet, et certaines attributions sont difficiles. Par exemple, il y a des commentaires intéressants dans ce code Apache (recherchez leurs noms) qui font référence à la source d'origine.

En fin de compte, il s'agit d'un algorithme de hachage très ancien et simple. Ce n'est pas le plus performant, et il n'est même pas prouvé mathématiquement être un "bon" algorithme. Mais c'est simple, et beaucoup de gens l'utilisent depuis longtemps avec de bons résultats, donc il a beaucoup de support historique.

tcurdt
la source
9
D'où vient le 1231: 1237? Je le vois aussi dans Java's Boolean.hashCode (). C'est magique?
David Leonard
17
C'est la nature d'un algorithme de hachage qu'il y aura des collisions. Je ne vois donc pas votre argument, Paul.
tcurdt
85
À mon avis, cette réponse ne répond pas à la question réelle (meilleures pratiques pour remplacer le hachage de NSObject). Il fournit juste un algorithme de hachage particulier. En plus de cela, la rareté de l'explication le rend difficile à comprendre sans une connaissance approfondie de la question, et peut amener les gens à l'utiliser sans savoir ce qu'ils font. Je ne comprends pas pourquoi cette question a autant de votes positifs.
Ricardo Sanchez-Saez
6
1er problème - (int) est petit et facile à déborder, utilisez NSUInteger. 2ème problème - Si vous continuez à multiplier le résultat par chaque hachage de variable, votre résultat débordera. par exemple. [NSString hash] crée de grandes valeurs. Si vous avez plus de 5 variables, il est facile de déborder avec cet algorithme. Cela entraînera tout ce qui correspond au même hachage, ce qui est mauvais. Voir ma réponse: stackoverflow.com/a/4393493/276626
Paul Solt
10
@PaulSolt - Le débordement n'est pas un problème pour générer un hachage, la collision l'est. Mais le débordement ne rend pas nécessairement la collision plus probable, et votre déclaration sur le débordement provoquant tout mappage sur le même hachage est tout simplement incorrecte.
DougW
81

Je prends juste Objective-C moi-même, donc je ne peux pas parler spécifiquement pour cette langue, mais dans les autres langues que j'utilise si deux instances sont "égales", elles doivent renvoyer le même hachage - sinon vous allez avoir tout sortes de problèmes lorsque vous essayez de les utiliser comme clés dans une table de hachage (ou toute collection de type dictionnaire).

En revanche, si 2 instances ne sont pas égales, elles peuvent ou non avoir le même hachage - il est préférable qu'elles ne le soient pas. C'est la différence entre une recherche O (1) sur une table de hachage et une recherche O (N) - si tous vos hachages entrent en collision, vous trouverez peut-être que la recherche dans votre table n'est pas meilleure que la recherche dans une liste.

En termes de meilleures pratiques, votre hachage doit renvoyer une distribution aléatoire de valeurs pour son entrée. Cela signifie que, par exemple, si vous avez un double, mais que la majorité de vos valeurs ont tendance à se regrouper entre 0 et 100, vous devez vous assurer que les hachages renvoyés par ces valeurs sont uniformément répartis sur toute la plage de valeurs de hachage possibles. . Cela améliorera considérablement vos performances.

Il existe un certain nombre d'algorithmes de hachage, dont plusieurs sont répertoriés ici. J'essaie d'éviter de créer de nouveaux algorithmes de hachage car cela peut avoir de grandes implications sur les performances, donc utiliser les méthodes de hachage existantes et faire une combinaison au niveau du bit comme vous le faites dans votre exemple est un bon moyen de l'éviter.

Brian B.
la source
4
+1 Excellente réponse, mérite plus de votes positifs, d'autant plus qu'il parle en fait de "meilleures pratiques" et de la théorie derrière pourquoi un bon (unique) hachage est important.
Quinn Taylor
30

Un XOR simple sur les valeurs de hachage des propriétés critiques est suffisant 99% du temps.

Par exemple:

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

Solution trouvée sur http://nshipster.com/equality/ par Mattt Thompson (qui a également référé cette question dans son article!)

Yariv Nissim
la source
1
Le problème avec cette réponse est qu'elle ne prend pas du tout en considération les valeurs primitives. Et les valeurs primitives peuvent également être importantes pour le hachage.
Vive
@Vive La plupart de ces problèmes sont résolus dans Swift, mais ces types représentent généralement leur propre hachage car ils sont primitifs.
Yariv Nissim
1
Bien que vous ayez raison pour Swift, il existe toujours de nombreux projets écrits avec objc. Parce que votre réponse est dédiée à objc, elle mérite au moins une mention.
Vive
XORing les valeurs de hachage ensemble est un mauvais conseil, il conduit à de nombreuses collisions de hachage. Au lieu de cela, multipliez avec un nombre premier, puis ajoutez, comme d'autres réponses l'indiquent.
fishinear
27

J'ai trouvé ce fil extrêmement utile fournissant tout ce dont j'avais besoin pour obtenir mes méthodes isEqual:et hashimplémentées avec une prise. Lors du test des variables d'instance d'objet dans isEqual:l'exemple de code utilise:

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

Cela a échoué à plusieurs reprises ( c.-à - d . Retourné NON ) sans erreur, quand j'ai su que les objets étaient identiques lors de mes tests unitaires. La raison en était que l'une des NSStringvariables d'instance était nulle, donc l'énoncé ci-dessus était:

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

et puisque nul répondra à n'importe quelle méthode, c'est parfaitement légal mais

[nil isEqual: nil]

renvoie nil , qui est NO , donc lorsque l'objet et celui testé ont tous deux un objet nil , ils seront considérés comme différents ( c'est -à- direisEqual: qu'ils renverraient NO ).

Cette solution simple consistait à remplacer l'instruction if par:

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

De cette façon, si leurs adresses sont les mêmes, il ignore l'appel de méthode, peu importe si elles sont toutes deux nulles ou toutes deux pointant vers le même objet, mais si l'une n'est pas nulle ou si elles pointent vers des objets différents, le comparateur est appelé de manière appropriée.

J'espère que cela fera gagner quelques minutes à quelqu'un de se gratter la tête.

LavaSlider
la source
20

La fonction de hachage doit créer une valeur semi-unique qui n'est pas susceptible d'entrer en collision ou de correspondre à la valeur de hachage d'un autre objet.

Voici la fonction de hachage complète, qui peut être adaptée aux variables d'instance de vos classes. Il utilise NSUInteger plutôt qu'int pour la compatibilité sur les applications 64 / 32bit.

Si le résultat devient 0 pour différents objets, vous courez le risque de heurter les hachages. La collision de hachages peut entraîner un comportement inattendu du programme lorsque vous travaillez avec certaines des classes de collection qui dépendent de la fonction de hachage. Assurez-vous de tester votre fonction de hachage avant de l'utiliser.

-(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
la source
3
Un problème ici: je préfère éviter la syntaxe des points, j'ai donc transformé votre instruction BOOL en (par exemple) result = prime * result + [self isSelected] ? yesPrime : noPrime;. J'ai ensuite trouvé que ce paramètre était réglé resultsur (par exemple) 1231, je suppose en raison de la ?priorité de l' opérateur. J'ai résolu le problème en ajoutant des crochets:result = prime * result + ([self isSelected] ? yesPrime : noPrime);
Ashley
12

Le moyen simple mais inefficace consiste à renvoyer la même -hashvaleur pour chaque instance. Sinon, oui, vous devez implémenter un hachage basé uniquement sur des objets qui affectent l'égalité. C'est délicat si vous utilisez des comparaisons laxistes -isEqual:(par exemple, des comparaisons de chaînes insensibles à la casse). Pour les ints, vous pouvez généralement utiliser l'int lui-même, sauf si vous comparez avec NSNumbers.

N'utilisez pas | =, cependant, cela saturera. Utilisez ^ = à la place.

Fait amusant au hasard:, [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]mais [[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]. (rdar: // 4538282, ouvert depuis le 05-mai-2006)

Jens Ayton
la source
1
Vous avez exactement raison sur le | =. Ça ne voulait pas vraiment dire ça. :) + = et ^ = sont assez équivalents. Comment gérez-vous les primitives non entières comme double et float?
Dave Dribin
Fait amusant au hasard: testez-le sur Snow Leopard ... ;-)
Quinn Taylor
Il a raison d'utiliser XOR au lieu de OR pour combiner des champs en un hachage. Cependant, n'utilisez pas le conseil de renvoyer la même valeur -hash pour chaque objet - bien que cela soit facile, cela peut dégrader gravement les performances de tout ce qui utilise le hachage de l'objet. Le hachage ne doit pas nécessairement être distinct pour les objets qui ne sont pas égaux, mais si vous pouvez y parvenir, il n'y a rien de tel.
Quinn Taylor
Le rapport de bogue radar ouvert est fermé. openradar.me/4538282 Qu'est-ce que cela signifie?
JJD
JJD, le bogue a été corrigé dans Mac OS X 10.6, comme l'a laissé entendre Quinn. (Notez que le commentaire date de deux ans.)
Jens Ayton
9

N'oubliez pas que vous devez uniquement fournir un hachage égal quand isEqualc'est vrai. Quand isEqualest faux, le hachage n'a pas à être inégal, bien que ce soit le cas. Par conséquent:

Gardez le hachage simple. Choisissez une variable membre (ou quelques membres) qui est la plus distinctive.

Par exemple, pour CLPlacemark, le nom seul suffit. Oui, il y a 2 ou 3 CLPlacemark distincts portant exactement le même nom mais ceux-ci sont rares. Utilisez ce hachage.

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

@implementation CLPlacemark (equal)

...

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


@end

Remarquez que je ne me donne pas la peine de préciser la ville, le pays, etc. Le nom suffit. Peut-être le nom et CLLocation.

Le hachage doit être réparti uniformément. Vous pouvez donc combiner plusieurs variables membres en utilisant le signe d'insertion ^ (signe xor)

C'est donc quelque chose comme

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

De cette façon, le hachage sera réparti uniformément.

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

Alors, que faire dans le tableau?

Encore une fois, simple. Vous n'avez pas besoin de hacher tous les membres du tableau. Assez pour hacher le premier élément, le dernier élément, le nombre, peut-être quelques éléments intermédiaires, et c'est tout.

user4951
la source
Les valeurs de hachage XORing ne donnent pas une distribution uniforme.
fishinear
7

Attendez, sûrement un moyen beaucoup plus facile de le faire est d'abord de passer outre - (NSString )description et de fournir une représentation sous forme de chaîne de l'état de votre objet (vous devez représenter l'état complet de votre objet dans cette chaîne).

Ensuite, fournissez simplement l'implémentation suivante de hash:

- (NSUInteger)hash {
    return [[self description] hash];
}

Ceci est basé sur le principe que "si deux objets chaîne sont égaux (comme déterminé par la méthode isEqualToString:), ils doivent avoir la même valeur de hachage."

Source: Référence de classe NSString

Jonathan Ellis
la source
1
Cela suppose que la méthode de description sera unique. L'utilisation du hachage de la description crée une dépendance, qui peut ne pas être évidente, et un risque plus élevé de collisions.
Paul Solt
1
+1 Surévalué. C'est une idée géniale. Si vous craignez que les descriptions provoquent des collisions, vous pouvez le remplacer.
user4951
Merci Jim, je ne nierai pas que c'est un peu un hack, mais cela fonctionnerait dans tous les cas auquel je peux penser - et comme je l'ai dit, à condition que vous remplaciez description, je ne vois pas pourquoi cela est inférieur à l'une des solutions les plus votées. Peut-être pas la solution la plus élégante mathématiquement, mais devrait faire l'affaire. Comme le déclare Brian B. (réponse la plus votée à ce stade): "J'essaie d'éviter de créer de nouveaux algorithmes de hachage" - d'accord! - Je viens de hashle NSString!
Jonathan Ellis
Voté parce que c'est une bonne idée. Je ne vais pas l'utiliser cependant parce que je crains les allocations NSString supplémentaires.
karwag
1
Ce n'est pas une solution générique car pour la plupart des classes, descriptionl'adresse du pointeur est incluse. Cela fait donc deux instances différentes de la même classe qui sont égales avec un hachage différent, ce qui viole l'hypothèse de base que deux objets égaux ont le même hachage!
Diogo T
5

Les contrats d'égalité et de hachage sont bien spécifiés et font l'objet de recherches approfondies dans le monde Java (voir la réponse de @ mipardi), mais les mêmes considérations devraient s'appliquer à Objective-C.

Eclipse fait un travail fiable pour générer ces méthodes en Java, voici donc un exemple Eclipse porté manuellement à Objective-C:

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

Et pour une sous-classe YourWidgetqui ajoute une propriété 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;
}

Cette implémentation évite certains pièges de sous-classement dans l'exemple isEqual:d'Apple:

  • Le test de classe d'Apple other isKindOfClass:[self class]est asymétrique pour deux sous-classes différentes de MyWidget. L'égalité doit être symétrique: a = b si et seulement si b = a. Cela pourrait facilement être corrigé en changeant le test en other isKindOfClass:[MyWidget class], alors toutes les MyWidgetsous-classes seraient mutuellement comparables.
  • L'utilisation d'un isKindOfClass:test de sous-classe empêche les sous-classes de remplacer isEqual:par un test d'égalité affiné. En effet, l'égalité doit être transitive: si a = b et a = c alors b = c. Si une MyWidgetinstance se compare à deux YourWidgetinstances, ces YourWidgetinstances doivent alors se comparer égales les unes aux autres, même si leurs serialNodifférences.

Le deuxième problème peut être résolu en ne considérant les objets comme égaux que s'ils appartiennent exactement à la même classe, d'où le [self class] != [object class]test ici. Pour les classes d'application typiques , cela semble être la meilleure approche.

Cependant, il y a certainement des cas où le isKindOfClass:test est préférable. Ceci est plus typique des classes de framework que des classes d'application. Par exemple, tout NSStringdoit être égal à n'importe quel autre NSStringavec la même séquence de caractères sous-jacente, quelle que soit la distinction NSString/ NSMutableString, et quelles que soient les classes privées du NSStringcluster de classes impliquées.

Dans de tels cas, isEqual:devrait avoir un comportement bien défini et bien documenté, et il devrait être clair que les sous-classes ne peuvent pas remplacer cela. En Java, la restriction 'no override' peut être appliquée en signalant les méthodes equals et hashcode comme final, mais Objective-C n'a pas d'équivalent.

jedwidz
la source
@adubr C'est couvert dans mes deux derniers paragraphes. Ce n'est pas focal car il MyWidgetest entendu que ce n'est pas un cluster de classe.
jedwidz
5

Cela ne répond pas directement à votre question (du tout) mais j'ai déjà utilisé MurmurHash pour générer des hachages: murmurhash

Je suppose que je devrais expliquer pourquoi: le murmurhash est sanglant rapidement ...

schwa
la source
2
Une bibliothèque C ++ qui se concentre sur des hachages uniques pour une clé void * en utilisant un nombre aléatoire (et ne se rapporte pas non plus aux objets Objective-C) n'est vraiment pas une suggestion utile ici. La méthode -hash devrait retourner une valeur cohérente à chaque fois, sinon elle sera totalement inutile. Si l'objet est ajouté à une collection qui appelle -hash et renvoie une nouvelle valeur à chaque fois, les doublons ne seront jamais détectés et vous ne pourrez jamais non plus récupérer l'objet de la collection. Dans ce cas, le terme "hachage" est différent de la signification en sécurité / cryptographie.
Quinn Taylor
3
murmurhash n'est pas une fonction de hachage cryptographique. Veuillez vérifier vos faits avant de publier des informations incorrectes. Murmurhash pourrait être utile pour hacher des classes objectives-c personnalisées (surtout si vous avez beaucoup de NSDatas impliqués) car il est extrêmement rapide. Cependant, je vous accorde que suggérer peut-être que ce n'est pas le meilleur conseil à donner à quelqu'un "ne faisant que ramasser l'objectif-c", mais veuillez noter mon préfixe sur ma réponse originale à la question.
schwa
4

Je suis aussi un débutant en Objective C, mais j'ai trouvé un excellent article sur l'identité vs l'égalité dans Objective C ici . D'après ma lecture, il semble que vous pourriez simplement conserver la fonction de hachage par défaut (qui devrait fournir une identité unique) et implémenter la méthode isEqual afin de comparer les valeurs de données.

cèperie
la source
Je suis un débutant Cocoa / Objective C, et cette réponse et ce lien m'ont vraiment aidé à couper toutes les choses plus avancées ci-dessus jusqu'à la ligne du bas - je n'ai pas besoin de m'inquiéter des hachages - implémentant simplement la méthode isEqual :. Merci!
John Gallagher
Ne manquez pas le lien de @ ceperry. L'article Equality vs Identityde Karl Kraft est vraiment bon.
JJD
6
@John: Je pense que vous devriez relire l'article. Il indique très clairement que «les instances égales doivent avoir des valeurs de hachage égales». Si vous remplacez isEqual:, vous devez également remplacer hash.
Steve Madsen
3

Quinn a tout simplement tort que la référence au hachage murmure soit inutile ici. Quinn a raison de vouloir comprendre la théorie du hachage. Le murmure distille une grande partie de cette théorie dans une implémentation. Il est intéressant d'explorer comment appliquer cette implémentation à cette application particulière.

Certains des points clés ici:

L'exemple de fonction de tcurdt suggère que «31» est un bon multiplicateur car il est premier. Il faut montrer qu'être premier est une condition nécessaire et suffisante. En fait, 31 (et 7) ne sont probablement pas des nombres premiers particulièrement bons, car 31 == -1% 32. Un multiplicateur impair avec environ la moitié des bits définis et la moitié des bits effacés est susceptible d'être meilleur. (La constante de multiplication de hachage de murmure a cette propriété.)

Ce type de fonction de hachage serait probablement plus fort si, après multiplication, la valeur du résultat était ajustée via un décalage et un xor. La multiplication a tendance à produire les résultats de nombreuses interactions binaires à l'extrémité supérieure du registre et de faibles résultats d'interaction à l'extrémité inférieure du registre. Le décalage et le xor augmentent les interactions à l'extrémité inférieure du registre.

La définition du résultat initial à une valeur où environ la moitié des bits sont nuls et environ la moitié des bits sont un aurait également tendance à être utile.

Il peut être utile de faire attention à l'ordre dans lequel les éléments sont combinés. On devrait probablement d'abord traiter les booléens et d'autres éléments où les valeurs ne sont pas fortement distribuées.

Il peut être utile d'ajouter quelques étapes de brouillage supplémentaires à la fin du calcul.

Que le hachage de murmure soit ou non rapide pour cette application est une question ouverte. Le hachage de murmure prémélange les bits de chaque mot d'entrée. Plusieurs mots d'entrée peuvent être traités en parallèle, ce qui aide les processeurs pipelinés à plusieurs problèmes.


la source
3

En combinant la réponse de @ tcurdt avec la réponse de @ oscar-gomez pour obtenir les noms de propriété , nous pouvons créer une solution de dépôt facile pour isEqual et hash:

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

Maintenant, dans votre classe personnalisée, vous pouvez facilement implémenter isEqual:et hash:

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

- (BOOL)isEqual:(id)other
{
    return IsEqualObjects(self, other);
}
johnboiles
la source
2

Notez que si vous créez un objet qui peut être muté après la création, la valeur de hachage ne doit pas changer si l'objet est inséré dans une collection. En pratique, cela signifie que la valeur de hachage doit être fixée à partir du point de la création initiale de l'objet. Voir la documentation d'Apple sur la méthode -hash du protocole NSObject pour plus d'informations:

Si un objet modifiable est ajouté à une collection qui utilise des valeurs de hachage pour déterminer la position de l'objet dans la collection, la valeur renvoyée par la méthode de hachage de l'objet ne doit pas changer pendant que l'objet se trouve dans la collection. Par conséquent, la méthode de hachage ne doit s'appuyer sur aucune des informations d'état interne de l'objet ou vous devez vous assurer que les informations d'état interne de l'objet ne changent pas pendant que l'objet se trouve dans la collection. Ainsi, par exemple, un dictionnaire modifiable peut être placé dans une table de hachage mais vous ne devez pas le modifier tant qu'il est là-dedans. (Notez qu'il peut être difficile de savoir si un objet donné se trouve ou non dans une collection.)

Cela me semble être un détournement complet, car il rend potentiellement les recherches de hachage beaucoup moins efficaces, mais je suppose qu'il est préférable de faire preuve de prudence et de suivre ce que dit la documentation.

user10345
la source
1
Vous lisez mal les documents de hachage - c'est essentiellement une situation "soit-ou". Si l'objet change, le hachage change généralement aussi. C'est vraiment un avertissement pour le programmeur, que si le hachage change à la suite de la mutation d'un objet, alors changer l'objet alors qu'il réside dans une collection qui utilise le hachage provoquera un comportement inattendu. Si l'objet doit être "mutable en toute sécurité" dans une telle situation, vous n'avez pas d'autre choix que de rendre le hachage sans rapport avec l'état mutable. Cette situation particulière me semble étrange, mais il y a certainement des situations peu fréquentes où elle s'applique.
Quinn Taylor
1

Désolé si je risque de sonner un boffin complet ici mais ... ... personne n'a pris la peine de mentionner que pour suivre les "meilleures pratiques", vous ne devriez certainement pas spécifier une méthode égale qui ne prendrait PAS en compte toutes les données appartenant à votre objet cible, par exemple quoi que ce soit les données sont agrégées à votre objet, par rapport à un associé de celui-ci, doivent être prises en compte lors de la mise en œuvre d'égal à égal. Si vous ne voulez pas prendre en compte, dites «âge» dans une comparaison, alors vous devriez écrire un comparateur et l'utiliser pour effectuer vos comparaisons au lieu de isEqual :.

Si vous définissez une méthode isEqual: qui effectue arbitrairement la comparaison d'égalité, vous courez le risque que cette méthode soit utilisée à mauvais escient par un autre développeur, ou même par vous-même, une fois que vous avez oublié le «rebondissement» dans votre interprétation égale.

Ergo, bien qu'il s'agisse d'un grand Q & A sur le hachage, vous n'avez normalement pas besoin de redéfinir la méthode de hachage, vous devriez probablement définir un comparateur ad hoc à la place.

Thibaud de Souza
la source