Meilleures pratiques pour remplacer isEqual : et hash

Question

Comment contourner correctement isEqual: en Objective-C ? Le "piège" semble être que si deux objets sont égaux (comme déterminé par la fonction isEqual: ), ils doivent avoir la même valeur de hachage.

El Introspection de la section Guide des fondamentaux de Cocoa a 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é des pointeurs, puis l'égalité des classes, et enfin compare les objets à l'aide de la fonction isEqualToWidget: qui ne vérifie que le name y data propriétés. Ce que l'exemple n'a pas montre comment passer outre hash .

Supposons qu'il existe d'autres propriétés qui n'affectent pas l'égalité, par exemple age . Ne devrait-on pas hash de telle sorte que seule la méthode name y data affectent le hachage ? Et si oui, comment le feriez-vous ? Il suffit d'ajouter les hachages de name y 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 en NSNumber pour obtenir leur hachage ? Ou des structures comme NSRect ?

( Perturbation cérébrale : A l'origine, j'ai écrit "bitwise OR" les deux ensemble avec |= . Je voulais ajouter.)

Answer 1

Commencez par

 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 édition pour l'attribution est juste.

Cet algorithme a été popularisé dans le livre "Effective Java", et le chapitre concerné peut actuellement être consulté 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 est cependant dérivé d'une mise en œuvre encore plus ancienne, attribuée à Dan Bernstein ou Chris Torek. Cet ancien algorithme circulait à l'origine sur Usenet, et il est difficile de l'attribuer avec certitude. Par exemple, il existe des commentaire intéressant dans ce code Apache (recherchez leur nom) qui fait référence à la source originale.

En résumé, il s'agit d'un algorithme de hachage simple et très ancien. Il n'est pas le plus performant, et il n'est même pas prouvé mathématiquement qu'il soit un "bon" algorithme. Mais il est simple et beaucoup de gens l'ont utilisé pendant longtemps avec de bons résultats, il bénéficie donc d'un soutien historique important.

Answer 2

Je suis moi-même en train d'apprendre l'Objective-C, donc je ne peux pas parler spécifiquement de ce langage, mais dans les autres langages que j'utilise, si deux instances sont "égales", elles doivent retourner le même hash - sinon vous allez avoir toutes sortes de problèmes lorsque vous essayez de les utiliser comme clés dans une table de hachage (ou toute autre collection de type dictionnaire).

D'autre part, si 2 instances ne sont pas égales, elles peuvent ou non avoir le même hachage - il est préférable qu'elles ne l'aient pas. C'est la différence entre une recherche O(1) sur une table de hachage et une recherche O(N) - si tous vos hashs entrent en collision, vous pouvez constater que la recherche dans votre table n'est pas meilleure que la recherche dans une liste.

En termes de bonnes pratiques, votre hachage doit retourner une distribution aléatoire de valeurs pour son entrée. Cela signifie que, par exemple, si vous disposez d'un double, mais que la majorité de vos valeurs tendent à se situer entre 0 et 100, vous devez vous assurer que les hachages renvoyés par ces valeurs sont répartis uniformément sur l'ensemble des 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 des répercussions importantes sur les performances. L'utilisation des méthodes de hachage existantes et la réalisation d'une combinaison par bit, comme vous le faites dans votre exemple, est un bon moyen d'éviter cela.

Answer 3

J'ai trouvé ce fil de discussion extrêmement utile en fournissant tout ce dont j'avais besoin pour obtenir ma isEqual: y hash mises en œuvre avec une seule prise. Lors du test des variables d'instance d'objet dans isEqual: que le code d'exemple utilise :

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

Cela a échoué à plusieurs reprises ( c'est-à-dire retourné NON ) sans erreur, lorsque je connaissait les objets étaient identiques dans mes tests unitaires. La raison était que l'un des NSString Les variables d'instance étaient néant donc la déclaration ci-dessus était :

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

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

[nil isEqual: nil]

renvoie à néant qui est NON Ainsi, lorsque l'objet et celui qui est testé avaient tous deux une néant ils seraient considérés comme non égaux ( c'est-à-dire , isEqual: rendrait NON ).

Cette solution simple consistait à changer l'instruction if en :

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

De cette façon, si leurs adresses sont les mêmes, l'appel de la méthode est ignoré, même si les deux adresses sont identiques. néant ou les deux pointent vers le même objet mais si l'un ou l'autre n'est pas néant ou qu'ils pointent vers des objets différents, alors le comparateur est appelé de manière appropriée.

J'espère que cela évitera à quelqu'un de se creuser la tête pendant quelques minutes.

Answer 4

La fonction de hachage doit créer une valeur semi-unique qui ne risque pas 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. Elle utilise des NSUInteger's plutôt que des int pour la compatibilité avec les applications 64/32bit.

Si le résultat est égal à 0 pour différents objets, vous courez le risque d'avoir des hachages en collision. La collision des hachages peut entraîner un comportement inattendu du programme lors de l'utilisation de certaines classes de collection qui dépendent de la fonction de hachage. Veillez à 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;
}

Answer 5

Cela m'a beaucoup aidé ! C'est peut-être la réponse que vous cherchez. mise en œuvre de l'égalité et du hachage