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

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 des collections d'objets.

Arrière-plan

NSObject fournit par défaut implémentations de -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: retourne YES pour les deux objets, alors le résultat de -hash pour ces objets doit être le 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 laquelle -compare: retourne 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:

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:] autrement. 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 dispose ce qui suit: (l'emphase est mienne)

"Si une mutable objet 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, 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 du contenu, 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 œuvre -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 à -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. Car il ne peut pas savoir ce que le hachage est utilisée, le résultat doit être uniforme pour tous possible instances qui devrait être considéré comme l'égal/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 la représenter.

Questions

  1. Sont là les meilleures pratiques lors de la mise en œuvre de de comparaison d'égalité -hash pour les collections?
  2. Sont là toutes les particularités de plan pour en Objective-C et Cocoa-esque collections?
  3. Y a de bonnes approches pour les tests unitaires -hash avec un degré raisonnable de confiance?
  4. Des 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 pas implique -isEqual:".)

Edit: je devrais avoir 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 sur le minimisant 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.

InformationsquelleAutor |
  1. 18

    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 pas implique -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 si (et vous avez la preuve dans de mesures concrètes des 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 de la combiner avec, disons, la -count de la collection. - Ce assez pour fournir une bonne hachage.

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

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

    Il y a une chose à faire attention qui peuvent influer sur ce que vous décidez de le faire pour vos 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 hors de la collection du contenu.

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

    • La bonne réponse. Le fait que "l'égalité -les valeurs de hachage ne pas implique -isEqual:" grandement simplifié de la portée du problème et a changé la façon dont je pensais à ce sujet. Je me demande si elle fait sens pour le cache de la valeur de hachage de l'intérieur de l'objet, et de le mettre à jour chaque fois qu'un objet est ajouté ou supprimé. Cela amortit le coût de calcul de la table de hachage, et les mises à jour que lorsque la collection est modifié, pas à chaque fois de hachage est appelé. Pour le hachage de lui-même, bien sûr, il est idéal pour obtenir une distribution uniforme, mais c'est un équilibre avec la vitesse. Je vais essayer de le XOR de compter, d'abord, et la dernière (si > 1) pour l'instant. 🙂
    • En ce qui concerne ma 2ème question, je suppose que mon problème est sur la correspondance de la façon dont la Fondation des collections de mettre en œuvre isEqual: et de hachage. Depuis l'Objective-C homologues à la Base de la Fondation, les collections sont à code source fermé, je n'ai aucun moyen de savoir si je suis en train de faire "la façon de Cacao". Je veux émuler le comportement des collections existantes d'obéir à la "Principe de moindre Surprise". Aussi, l'égalité des contrats de Cacao sont un peu différents de langues comme Java. J'ai lu ce post pour avoir des idées: karlkraft.com/index.php/2008/01/07/equality-vs-identity
    InformationsquelleAutor kperryua
  2. 4

    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 en passant. 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 ensuite ne doit pas non plus de tout objet qui a une véritable fonction de hachage.

    • J'ai édité ma question pour clarifier ma compréhension préalable de votre premier et dernier alinéas. Merci de remarquer que le hachage n'est pas obligatoire pour retourner des valeurs différentes pour des valeurs hétérogènes. Il n'avait pas de sens au premier abord, mais une remise à niveau rapide sur les collections que l'utilisation des hachages m'a rappelé à propos de seaux et de l'enchaînement. Vos suggestions pour la création d'une table de hachage sont d'accord, mais @kperryua soulève un excellent point sur l'évolutivité de hachages, depuis que je suis en train de parler des collections.
    InformationsquelleAutor U62
  3. 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 une mutable objet 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

    De sorte qu'il coutures comme 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.

    • NSMutableArray ne repose pas sur la valeur de hachage pour la position de l'objet. Mais il est intéressant de noter que le hachage par défaut de mise en œuvre renvoie le nombre. Renforce ce kperryua dit ci-dessus.
    InformationsquelleAutor