Python: Ce qui est correct et la bonne façon de mettre en œuvre __hash__()?

Question

Ce qui est correct et la bonne façon de mettre en œuvre __hash__()?

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

En tant que __hash__() renvoie un entier et est utilisé pour le "binning" les objets dans les tables de hashage je suppose que les valeurs de l'entier retourné doit être uniformément répartie de données communes (pour minimiser les collisions). Ce qui 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 un conteneur de classe contenant de l'ints, certains flotteurs et d'une chaîne.

Answer 1

Facile, bonne façon de mettre en oeuvre __hash__() est d'utiliser une clé de tuple. Il ne sera pas aussi rapide qu'un spécialisé de hachage, mais si vous avez besoin, alors vous devriez probablement mettre en œuvre le type C.

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

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

    def __eq__(x, y):
        return x.__key() == y.__key()

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

Answer 2

Jean Millikin proposé une solution similaire à ceci:

class A(object):

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

    def __eq__(self, othr):
        return ((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 l' hash(A(a, b, c)) == hash((a, b, c)). En d'autres termes, la valeur de hachage entre en collision avec celle de la n-uplet de ses principaux membres. Peut-être que cela n'a pas d'importance très souvent dans la pratique?

La documentation Python sur __hash__ suggère de combiner les valeurs de hachage de la sous-composants à l'aide de 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):
        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) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Bonus: plus robuste __eq__ jetés là pour faire bonne mesure.

Mise à jour: comme Blckknght points, modification de l'ordre de a, b, et c peuvent causer des problèmes. J'ai ajouté une supplémentaire ^ hash((self._a, self._b, self._c)) de la capture de l'ordre des valeurs hachées. Cette dernière ^ hash(...) peut être retiré si les valeurs ne peut être modifié (par exemple, si ils ont des types différents et, par conséquent, la valeur de _a ne sera jamais attribué à l' _b ou _c, etc.).

Answer 3

Paul Larson, de Microsoft Research a étudié un large éventail de fonctions de hachage. Il m'a dit que

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

travaillé étonnamment bien pour une grande variété de chaînes de caractères. J'ai trouvé que même polynôme techniques fonctionnent bien pour le calcul d'un hash de la disparité des sous-champs.

Answer 4

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

Les collisions se traduira probablement pas de le code de hachage de lui-même, mais de la cartographie du code de hachage d'un index dans une collection. Donc, pour votre exemple de fonction de hachage peut retourner des valeurs aléatoires de 1 à 10000, mais si votre table de hachage a seulement 32 entrées vous obtiendrez des collisions sur l'insertion.

En outre, je pense que les collisions seront résolues par la collecte en interne, et il existe de nombreuses méthodes pour résoudre les collisions. Le plus simple (et le pire) est, compte tenu d'une entrée à insérer à l'indice i, ajouter 1 à i jusqu'à ce que vous trouver un endroit vide et de l'y insérer. Récupération puis fonctionne de la même manière. Il en résulte une perte d'efficacité de récupérations pour certaines entrées, comme vous avez pu avoir une entrée qui nécessite traversant l'ensemble de la collection à trouver!

D'autres méthodes de résolution de collision de réduire le temps de récupération en déplaçant les entrées dans la table de hachage quand un élément est inséré à la propagation des choses. Cela augmente le moment de l'insertion, mais suppose que vous avez lu plus que vous insérez. Il y a également d'autres méthodes essayer et de direction des différentes entrées en collision, de façon que les entrées de cluster dans un endroit particulier.

Aussi, si vous avez besoin de redimensionner la collection, vous aurez besoin de ressasser tout ce ou de l'utilisation d'une dynamique de la méthode de hachage.

En bref, selon ce que vous êtes en utilisant le code de hachage pour vous peut avoir à mettre en place votre propre méthode de résolution de collision. Si vous n'êtes pas de les ranger dans une collection, vous pouvez probablement vous en sortir avec une fonction de hachage qui génère des codes de hachage dans une très large gamme. Si oui, vous pouvez assurez-vous que votre conteneur est plus grand qu'il doit être (plus le mieux, bien sûr) en fonction de vos soucis de mémoire.

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

conflué de hachage sur wikipédia

Wikipédia a aussi un résumé des différentes méthodes de résolution de collision:

Aussi, "l'Organisation des Fichiers Et de Traitement" par Tharp couvre beaucoup de collision des méthodes de résolution en profondeur. IMO c'est une grande référence pour les algorithmes de hachage.

Answer 5

Dépend de la taille de la valeur de hachage de retour. C'est de la simple logique que si vous avez besoin de retourner un 32 bits int basée sur le hachage de quatre entiers 32 bits, vous allez obtenir des collisions.

Je favoriserais les opérations sur les 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 fonctionner pour les flotteurs de trop, si vous avez simplement pris leur peu de valeur plutôt que de représenter une valeur à virgule flottante, peut-être mieux. Les chaînes, j'ai peu/pas d'idée.