Quelle est la manière correcte et efficace d'implémenter __hash __ ()?

150

Quelle est la manière correcte et efficace de mettre en œuvre __hash__()?

Je parle de la fonction qui renvoie un hashcode qui est ensuite utilisé pour insérer des objets dans des hashtables aka dictionnaires.

Comme __hash__()renvoie un entier et est utilisé pour "regrouper" des objets dans des tables de hachage, je suppose que les valeurs de l'entier retourné doivent être uniformément distribuées pour les données communes (pour minimiser les collisions). Quelle est une bonne pratique pour obtenir de telles valeurs? Les collisions sont-elles un problème? Dans mon cas, j'ai une petite classe qui agit comme une classe conteneur contenant des entiers, des flotteurs et une chaîne.

user229898
la source

Réponses:

185

Une manière simple et correcte d'implémenter __hash__()consiste à utiliser un tuple clé. Ce ne sera pas aussi rapide qu'un hachage spécialisé, mais si vous en avez besoin, vous devriez probablement implémenter le type en C.

Voici un exemple d'utilisation d'une clé pour le hachage et l'égalité:

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

En outre, la documentation de__hash__ contient plus d'informations, qui peuvent être utiles dans certaines circonstances.

John Millikin
la source
1
Mis à part les frais généraux mineurs liés à la factorisation de la __keyfonction, c'est à peu près aussi rapide que n'importe quel hachage peut l'être. Bien sûr, si les attributs sont connus pour être des entiers, et qu'il n'y en a pas trop, je suppose que vous pourriez potentiellement courir un peu plus vite avec un hachage personnalisé, mais il ne serait probablement pas aussi bien distribué. hash((self.attr_a, self.attr_b, self.attr_c))va être étonnamment rapide (et correcte ), car la création de petits tuples est spécialement optimisée, et elle pousse le travail d'obtention et de combinaison de hachages vers les fonctions intégrées C, ce qui est généralement plus rapide que le code de niveau Python.
ShadowRanger
Disons qu'un objet de classe A est utilisé comme clé pour un dictionnaire et si un attribut de classe A change, sa valeur de hachage changera également. Cela ne créerait-il pas un problème?
Mr Matrix le
1
Comme l'indique la réponse de @oved.by.Jesus ci-dessous, la méthode de hachage ne doit pas être définie / remplacée pour un objet mutable (défini par défaut et utilise id pour l'égalité et la comparaison).
Mr Matrix le
@Miguel, j'ai rencontré le problème exact , ce qui se passe, c'est que le dictionnaire revient Noneune fois que la clé change. La façon dont je l'ai résolu était de stocker l'identifiant de l'objet comme clé au lieu de simplement l'objet.
Jaswant P
@JaswantP Python utilise par défaut l'ID de l'objet comme clé pour tout objet hachable.
Mr Matrix
22

John Millikin a proposé une solution similaire à celle-ci:

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

Le problème avec cette solution est que le fichier hash(A(a, b, c)) == hash((a, b, c)). En d'autres termes, le hachage entre en collision avec celui du tuple de ses membres clés. Peut-être que cela n'a pas d'importance très souvent dans la pratique?

Mise à jour: la documentation Python recommande désormais d'utiliser un tuple comme dans l'exemple ci-dessus. Notez que la documentation indique

La seule propriété requise est que les objets qui se comparent égaux ont la même valeur de hachage

Notez que l'inverse n'est pas vrai. Les objets qui ne sont pas comparables peuvent avoir la même valeur de hachage. Une telle collision de hachage n'entraînera pas le remplacement d'un objet par un autre lorsqu'il est utilisé comme clé de dict ou élément d'ensemble tant que les objets ne se comparent pas également .

Solution obsolète / mauvaise

La documentation Python sur__hash__ suggère de combiner les hachages des sous-composants en utilisant quelque chose comme XOR , ce qui nous donne ceci:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Mise à jour: comme le souligne Blckknght, changer l'ordre de a, b et c pourrait poser des problèmes. J'ai ajouté un élément supplémentaire ^ hash((self._a, self._b, self._c))pour capturer l'ordre des valeurs hachées. Cette finale ^ hash(...)peut être supprimée si les valeurs combinées ne peuvent pas être réorganisées (par exemple, si elles ont des types différents et par conséquent, la valeur de _ane sera jamais attribuée à _bou _c, etc.).

Millerdev
la source
5
Vous ne voulez généralement pas faire un XOR direct des attributs ensemble, car cela vous donnera des collisions si vous changez l'ordre des valeurs. C'est, hash(A(1, 2, 3))sera égal à hash(A(3, 1, 2))(et ils à la fois hachage égale à toute autre Ainstance avec une permutation 1, 2et 3que ses valeurs). Si vous voulez éviter que votre instance ait le même hachage qu'un tuple de leurs arguments, créez simplement une valeur sentinelle (en tant que variable de classe ou en tant que global) puis incluez-la dans le tuple à hacher: return hash ((_ sentinel , self._a, self._b, self._c))
Blckknght
1
Votre utilisation de isinstancepourrait être problématique, car un objet d'une sous-classe de type(self)peut maintenant être égal à un objet de type(self). Ainsi, vous pouvez constater que l'ajout de a Caret a Fordà a set()peut entraîner l'insertion d'un seul objet, selon l'ordre d'insertion. En outre, vous pouvez rencontrer une situation dans laquelle a == best True mais b == aest False.
MaratC
1
Si vous faites une sous B- classe , vous voudrez peut-être changer cela enisinstance(othr, B)
millerdev
7
Une pensée: le tuple clé pourrait inclure le type de classe, ce qui empêcherait d' autres classes avec le même ensemble de clés d'attributs d'être montré égal: hash((type(self), self._a, self._b, self._c)).
Ben Mosher
2
Outre le fait d'utiliser Bau lieu de type(self), il est souvent considéré comme une meilleure pratique de revenir en NotImplementedcas de rencontre d'un type inattendu au __eq__lieu de False. Cela permet à d' autres types définis par l' utilisateur d'implémenter un __eq__qui en connaît Bet peut le comparer, s'ils le souhaitent.
Mark Amery
16

Paul Larson de Microsoft Research a étudié une grande variété de fonctions de hachage. Il m'a dit que

for c in some_string:
    hash = 101 * hash  +  ord(c)

fonctionnait étonnamment bien pour une grande variété de cordes. J'ai trouvé que des techniques polynomiales similaires fonctionnent bien pour calculer un hachage de sous-champs disparates.

George V. Reilly
la source
8
Apparemment, Java le fait de la même manière mais en utilisant 31 au lieu de 101
user229898
3
Quelle est la justification de l'utilisation de ces chiffres? Y a-t-il une raison de choisir 101 ou 31?
bigblind
1
Voici une explication des multiplicateurs principaux: stackoverflow.com/questions/3613102/… . 101 semble particulièrement bien fonctionner, sur la base des expériences de Paul Larson.
George V. Reilly
4
Python utilise (hash * 1000003) XOR ord(c)pour les chaînes avec une multiplication wraparound 32 bits. [Citation ]
tylerl
4
Même si cela est vrai, cela n'est d'aucune utilité pratique dans ce contexte car les types de chaînes Python intégrés fournissent déjà une __hash__méthode; nous n'avons pas besoin de rouler les nôtres. La question est de savoir comment implémenter __hash__pour une classe définie par l'utilisateur typique (avec un tas de propriétés pointant vers des types intégrés ou peut-être vers d'autres classes définies par l'utilisateur), que cette réponse ne traite pas du tout.
Mark Amery
3

Je peux essayer de répondre à la deuxième partie de votre question.

Les collisions ne résulteront probablement pas du code de hachage lui-même, mais du mappage du code de hachage à un index dans une collection. Ainsi, par exemple, votre fonction de hachage peut renvoyer des valeurs aléatoires de 1 à 10000, mais si votre table de hachage ne contient que 32 entrées, vous obtiendrez des collisions lors de l'insertion.

De plus, je pense que les collisions seraient résolues par la collection en interne, et il existe de nombreuses méthodes pour résoudre les collisions. Le plus simple (et le pire) est, étant donné une entrée à insérer à l'index i, d'ajouter 1 à i jusqu'à ce que vous trouviez un emplacement vide et l'insérez là. La récupération fonctionne alors de la même manière. Cela entraîne des récupérations inefficaces pour certaines entrées, car vous pourriez avoir une entrée qui nécessite de parcourir toute la collection pour la trouver!

D'autres méthodes de résolution de collision réduisent le temps de récupération en déplaçant les entrées dans la table de hachage lorsqu'un élément est inséré pour répartir les choses. Cela augmente le temps d'insertion mais suppose que vous lisez plus que vous n'insérez. Il existe également des méthodes qui essaient de dériver différentes entrées en collision afin que les entrées se regroupent à un endroit particulier.

De plus, si vous avez besoin de redimensionner la collection, vous devrez tout remanier ou utiliser une méthode de hachage dynamique.

En bref, selon ce que vous utilisez pour le code de hachage, vous devrez peut-être implémenter votre propre méthode de résolution de collision. Si vous ne les stockez pas dans une collection, vous pouvez probablement vous en tirer avec une fonction de hachage qui ne génère que des codes de hachage dans une très large plage. Si tel est le cas, vous pouvez vous assurer que votre conteneur est plus grand que nécessaire (le plus gros sera le mieux bien sûr) en fonction de vos problèmes de mémoire.

Voici quelques liens si vous êtes plus intéressé:

hachage coalescent sur wikipedia

Wikipedia propose également un résumé des différentes méthodes de résolution des collisions:

De plus, " File Organization And Processing " de Tharp couvre de nombreuses méthodes de résolution de collision. IMO c'est une excellente référence pour les algorithmes de hachage.

Kryptique
la source
1

Une très bonne explication sur le moment et la manière d'implémenter la __hash__fonction sur le site Web de programiz :

Juste une capture d'écran pour donner un aperçu: (Récupéré le 13/12/2019)

Capture d'écran de https://www.programiz.com/python-programming/methods/built-in/hash 2019-12-13

Quant à une implémentation personnelle de la méthode, le site mentionné ci-dessus fournit un exemple qui correspond à la réponse de millerdev .

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))
aimé.par.Jésus
la source
0

Dépend de la taille de la valeur de hachage que vous renvoyez. Il est logique que si vous avez besoin de renvoyer un int 32 bits basé sur le hachage de quatre ints 32 bits, vous allez avoir des collisions.

Je préférerais les opérations de bits. Comme, le pseudo code C suivant:

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

Un tel système pourrait également fonctionner pour les flottants, si vous les preniez simplement comme leur valeur en bits plutôt que de représenter réellement une valeur à virgule flottante, peut-être mieux.

Pour les cordes, j'ai peu / aucune idée.

Chiot
la source
Je sais qu'il y aura des collisions. Mais je n'ai aucune idée de la manière dont ils sont traités. De plus, mes valeurs d'attributs combinées sont très peu distribuées, je cherchais donc une solution intelligente. Et d'une manière ou d'une autre, je m'attendais à ce qu'il y ait une meilleure pratique quelque part.
user229898