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.
la source
__key
fonction, 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 petitstuple
s 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.None
une 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.John Millikin a proposé une solution similaire à celle-ci:
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
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, ce qui nous donne ceci:__hash__
suggère de combiner les hachages des sous-composants en utilisant quelque chose comme XORMise à 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_a
ne sera jamais attribuée à_b
ou_c
, etc.).la source
hash(A(1, 2, 3))
sera égal àhash(A(3, 1, 2))
(et ils à la fois hachage égale à toute autreA
instance avec une permutation1
,2
et3
que 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))isinstance
pourrait être problématique, car un objet d'une sous-classe detype(self)
peut maintenant être égal à un objet detype(self)
. Ainsi, vous pouvez constater que l'ajout de aCar
et aFord
à aset()
peut entraîner l'insertion d'un seul objet, selon l'ordre d'insertion. En outre, vous pouvez rencontrer une situation dans laquellea == b
est True maisb == a
est False.B
- classe , vous voudrez peut-être changer cela enisinstance(othr, B)
hash((type(self), self._a, self._b, self._c))
.B
au lieu detype(self)
, il est souvent considéré comme une meilleure pratique de revenir enNotImplemented
cas de rencontre d'un type inattendu au__eq__
lieu deFalse
. Cela permet à d' autres types définis par l' utilisateur d'implémenter un__eq__
qui en connaîtB
et peut le comparer, s'ils le souhaitent.Paul Larson de Microsoft Research a étudié une grande variété de fonctions de hachage. Il m'a dit que
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.
la source
(hash * 1000003) XOR ord(c)
pour les chaînes avec une multiplication wraparound 32 bits. [Citation ]__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.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.
la source
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)
Quant à une implémentation personnelle de la méthode, le site mentionné ci-dessus fournit un exemple qui correspond à la réponse de millerdev .
la source
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:
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.
la source