La mise en œuvre de hachage / -isEqual: / -isEqualTo...: pour Objective-C collections

Question

Remarque: Le suivant de SORTE que les questions sont liées, mais ni eux, ni les ressources liées semblent pleinement répondre à mes questions, notamment en matière de mise en œuvre de tests d'égalité pour les collections d'objets.

• Les meilleures pratiques de remplacement -isEqual: et -de hachage
• Techniques pour la mise en œuvre de hachage sur mutable Cacao objets

---

Arrière-plan

NSObject fournit par défaut des implémentations -hash (qui renvoie l'adresse de l'instance, comme (NSUInteger)self) et -isEqual: (qui renvoie NO moins que les adresses du destinataire et le paramètre sont identiques). Ces méthodes sont destinées à être remplacées si nécessaire, mais la documentation indique clairement que vous devez fournir deux ou aucun des deux. De plus, si -isEqual: retours YES pour les deux objets, alors le résultat de l' -hash de ces objets doit être la même. Si pas, des problèmes peuvent se produire lorsque des objets qui doivent être les mêmes - comme deux instances de chaîne pour qui -compare: retours NSOrderedSame - sont ajoutés à une collection de Cacao ou de comparer directement.

Contexte

Je développe CHDataStructures.cadre, un open-source de la bibliothèque de l'Objective-C des structures de données. J'ai mis en œuvre un certain nombre de collections, et je suis actuellement en train d'affiner et d'améliorer leur fonctionnalité. Une des fonctionnalités que je veux ajouter, c'est la capacité à comparer des collections pour l'égalité avec l'autre.

Plutôt que de comparer uniquement les adresses de mémoire, ces comparaisons doivent considérer les objets présents dans les deux collections (y compris la commande, le cas échéant). Cette approche a un précédent dans le Cacao, et utilise généralement une méthode distincte, y compris les suivantes:

• -[NSArray isEqualToArray:]
• -[NSDate isEqualToDate:]
• -[NSDictionary isEqualToDictionary:]
• -[NSNumber isEqualToNumber:]
• -[NSSet isEqualToSet:]
• -[NSString isEqualToString:]
• -[NSValue isEqualToValue:]

Je veux faire mes collections personnalisées robuste pour les tests d'égalité, de sorte qu'ils peuvent en toute sécurité (et prévisible) sera ajoutée à d'autres collections, et de permettre à d'autres personnes (comme un NSSet) pour déterminer si les deux collections sont égaux/équivalent/doublons.

Problèmes

Un -isEqualTo...: méthode fonctionne très bien sur son propre, mais les classes qui définissent ces méthodes est généralement aussi remplacer -isEqual: d'invoquer [self isEqualTo...:] si le paramètre est de la même classe (ou peut-être sous-classe) comme récepteur, ou [super isEqual:] sinon. Cela signifie que la classe doit également définir -hash tel qu'il sera de retour la même valeur pour les disparates instances qui ont le même contenu.

En outre, la documentation d'Apple pour -hash stipule ce qui suit: (c'est moi qui souligne)

"Si un objet mutable est ajouté à une collection qui utilise les valeurs de hachage pour déterminer la position de l'objet dans la collecte, la valeur retournée par la méthode de hachage de l'objet ne doit pas changer pendant que l'objet est dans la collection. Donc, soit la méthode de hachage ne doit pas compter sur l'objet l'état interne de l'information ou vous devez vous assurer que l'objet interne de l'état de l'information ne change pas alors que l'objet est dans la collection. Ainsi, par exemple, une mutable dictionnaire peut être mis dans une table de hachage, mais vous ne devez pas modifier, alors qu'il est là. (Notez qu'il peut être difficile de savoir si un objet est dans une collection)."

Edit: j'ai certainement comprendre pourquoi cela est nécessaire et tout à fait d'accord avec le raisonnement - je mentionné ici pour fournir un contexte supplémentaire, et a frôlé le sujet de pourquoi c'est le cas pour des raisons de concision.

Toutes mes collections sont mutables, et le hachage devra tenir compte d'au moins certains des contenus, donc la seule option ici est à considérer comme une erreur de programmation pour muter une collection stockée dans une autre collection. (Mes collections tous adopter NSCopying, de sorte collections comme NSDictionary peut réussir à faire une copie pour l'utiliser comme une clé, etc.)

Il fait sens pour moi, pour mettre en oeuvre -isEqual: et -hash, puisque (par exemple) indirecte de l'utilisateur de l'une de mes classes ne peut pas savoir spécifique -isEqualTo...: méthode à appeler, ou même se préoccuper de savoir si deux objets sont des instances de la même classe. Ils devraient être en mesure d'appeler -isEqual: ou -hash sur toute variable de type id et obtenir le résultat escompté.

Contrairement aux -isEqual: (qui a accès aux deux instances en cours de comparaison), -hash doit renvoyer un résultat "à l'aveuglette", qui n'ont accès qu'aux données à l'intérieur d'une instance particulière. Depuis il ne peut pas savoir ce que le hachage est utilisée, le résultat doit être uniforme pour tous les cas possibles qui devraient être considérées comme égales/identique, et doit toujours être d'accord avec -isEqual:. (Edit: Ce qui a été démenti par les réponses ci-dessous, et cela rend la vie plus facile.) En outre, la rédaction d'un bon de fonctions de hachage est non-trivial - garantir l'unicité est un défi, surtout quand vous avez seulement une NSUInteger (32/64 bits) pour le représenter.

Questions

1. Sont là les meilleures pratiques lors de la mise en œuvre de l'égalité des comparaisons -hash pour les collections?
2. Existe-il des particularités de plan pour en Objective-C et Cocoa-esque collections?
3. Existe-il des bonnes approches pour les tests unitaires -hash avec un degré raisonnable de confiance?
4. Toutes les suggestions sur la mise en œuvre de -hash d'accord avec -isEqual: pour les collections contenant des éléments de types arbitraires? Quels sont les pièges dois-je connaître? (Edit: Pas aussi problématique que j'ai d'abord pensé que @kperryua le souligne, "l'égalité des -hash valeurs ne sont pas impliquent -isEqual:".)

---

Edit: j'aurais du précisé que je ne suis pas confus sur la façon de mettre en place des isEqual: ou -isEqualTo...: pour les collections, c'est simple. Je pense que ma confusion découle principalement de (à tort) à penser que le hachage DOIT renvoyer une valeur différente si -isEqual: retourne PAS. Ayant fait de la cryptographie dans le passé, je pensais que les hachages pour différentes valeurs DOIVENT être différentes. Cependant, les réponses ci-dessous m'a fait réaliser qu'une "bonne" fonction de hachage est vraiment à propos de minimiser seau de collisions et de chaînage pour les collections qui utilisent -hash. Tandis que les hachages sont préférables, ils ne sont pas d'une exigence stricte.

Answer 1

Je pense essayer de venir avec certains généralement utile en fonction de hachage qui va générer unique de valeurs de hachage pour les collections est un exercice futile. U62 la suggestion de combiner les valeurs de hachage de tous, le contenu n'est pas à l'échelle, car il rend la fonction de hachage O(n). Les fonctions de hachage devrait vraiment être O(1) pour assurer de bonnes performances, sinon le but de la table de hachage est vaincu. (Tenir compte de la commune de Cacao construire de plists, qui sont les dictionnaires contenant des tableaux et d'autres dictionnaires, potentiellement ad nauseam. Tenter de prendre le hachage de haut-niveau dictionnaire d'un grand plist serait atrocement lent si les collections de fonctions de hachage ont été O(n).)

Ma suggestion serait de ne pas s'inquiéter beaucoup sur une collection de hachage. Comme vous l'avez indiqué, -isEqual: implique l'égalité des -hash valeurs. D'autre part, l'égalité des -hash valeurs ne sont pas impliquent -isEqual:. Que fait vous donne beaucoup de marge de manœuvre pour créer un simple hash.

Si vous êtes vraiment inquiet à propos de collisions (et vous avez la preuve dans les mesures concrètes de situations du monde réel que confirmer que c'est quelque chose à être inquiet au sujet de), vous pouvez toujours suivre U62 conseils à un certain degré. Par exemple, vous pourriez prendre le hachage de, disons, le premier et/ou dernier élément de la collection, et les associer avec, disons, l' -count de la collection. - Ce assez pour fournir une bonne hachage.

J'espère que cela répond au moins à une de vos questions.

Comme pour les N ° 1: mise en oeuvre -isEqual: est très jolie coupe et sec. Vous énumérer le contenu, et de vérifier isEqual: sur chacun des éléments.

Il n'y a qu'une chose à faire attention qui peuvent influer sur ce que vous décidez de faire des collections,' -hash fonctions. Les Clients de vos collections doivent aussi comprendre les règles qui régissent -isEqual: et -hash. Si vous utilisez le contenu' -hash dans votre collection, -hash, votre collection sera en pause si le contenu' isEqual: et -hash ne sont pas d'accord. C'est la faute du client, bien sûr, mais c'est un autre argument à l'encontre de baser votre -hash off de la collection du contenu.

N ° 2 est une sorte de vague. Pas sûr de ce que vous avez à l'esprit.

Answer 2

Deux collections doivent être considérées comme égales si elles contiennent les mêmes éléments, et en outre, si les collections sont commandés, que les éléments sont dans le même ordre.

Sur le sujet de hachages pour les collections, il suffit de combiner les hachages des éléments d'une certaine façon (XOR ou modulo les ajouter). Notez que bien que les règles de l'état que deux objets sont égaux selon IsEqual besoin de retourner le même hachage, l'inverse ne tient pas : Bien que l'unicité de hachages est souhaitable, il n'est pas nécessaire pour assurer l'exactitude de la solution. Ainsi, une collection ordonnée n'a pas besoin de tenir compte de l'ordre des éléments.

L'extrait de la documentation d'Apple est une restriction nécessaire à la par la. Un objet ne peut pas maintenir la même valeur de hachage en vertu de mutation tout en veillant à ce que les objets ayant la même valeur ont le même hash. Qui s'applique pour le plus simple des objets ainsi que les collections. Bien sûr, il ne questions qu'un hachage de l'objet des modifications lorsqu'il est à l'intérieur d'un conteneur qui utilise le hachage, de les organiser et les éléments. Le résultat de tout cela est que mutable collections ne devrait pas muter dans un autre récipient, mais alors vous ne devriez tout objet qui a une véritable fonction de hachage.

Answer 3

J'ai fait quelques recherches dans le NSArray et NSMutableArray de hachage par défaut de mise en œuvre et (sauf si j'ai mal compris quelque chose) il coutures comme Apple ne suivent pas leurs propres règles:

Si un objet mutable est ajouté à une collection qui utilise les valeurs de hachage pour déterminer la position de l'objet dans la collecte, la valeur retournée par la méthode de hachage de l'objet ne doit pas changer pendant que l'objet est dans la collection. Par conséquent, la méthode de hachage ne doit pas compter sur l'objet l'état interne de l'information ou vous devez vous assurer l'objet de l'état interne de l'information ne change pas alors que le l'objet est dans la collection. Ainsi, par exemple, un dictionnaire mutable peut être mis dans une table de hachage, mais vous ne devez pas modifier, alors qu'il est dans il n'. (Notez qu'il peut être difficile de savoir si oui ou non un l'objet se trouve dans une collection).

Voici mon code de test

NSMutableArray* myMutableArray = [NSMutableArray arrayWithObjects:@"a", @"b", @"c", nil];
NSMutableArray* containerForMutableArray = [NSMutableArray arrayWithObject:myMutableArray];

NSUInteger hashBeforeMutation = [[containerForMutableArray objectAtIndex:0] hash];
[[containerForMutableArray objectAtIndex:0] removeObjectAtIndex:1];
NSUInteger hashAfterMutation = [[containerForMutableArray objectAtIndex:0] hash];

NSLog(@"Hash Before: %d", hashBeforeMutation);
NSLog(@"Hash After : %d", hashAfterMutation);

La sortie est:

Hash Before: 3
Hash After : 2

Donc, il appert que le défaut de mise en œuvre de la méthode de Hachage sur les deux NSArray et NSMutableArray est le calcul de la matrice et il dosn pas de soins si son à l'intérieur d'une collection ou pas.