Hachable, immuable

Question

D'après une récente question de l'OS (voir Créer un dictionnaire en python qui est indexé par des listes ) J'ai réalisé que j'avais probablement une mauvaise conception de la signification des objets hachables et immuables en python.

• Que signifie "hachable" en pratique ?
• Quelle est la relation entre hachable et immuable ?
• Existe-t-il des objets mutables qui sont hachables ou des objets immuables qui ne sont pas hachables ?

Answer 1

Hachage est le processus de conversion d'une grande quantité de données en une quantité beaucoup plus petite (typiquement un seul entier) d'une manière répétable afin qu'elle puisse être consultée dans une table en temps constant ( O(1) ), ce qui est important pour les algorithmes et les structures de données à haute performance.

Immutabilité est l'idée qu'un objet ne changera pas de manière importante après sa création, en particulier d'une manière qui pourrait modifier la valeur de hachage de cet objet.

Les deux idées sont liées car les objets utilisés comme clés de hachage doivent généralement être immuables afin que leur valeur de hachage ne change pas. Si elle était autorisée à changer, l'emplacement de cet objet dans une structure de données telle qu'une table de hachage changerait, ce qui irait à l'encontre de l'objectif d'efficacité du hachage.

Pour bien saisir l'idée, vous devriez essayer d'implémenter votre propre table de hachage dans un langage comme C/C++, ou lire l'implémentation Java de la table de hachage. HashMap classe.

Answer 2

Techniquement, hachable signifie que la classe définit __hash__() . Selon les docs :

__hash__() doit retourner un nombre entier. La seule propriété requise est que les objets qui se comparent de manière égale aient la même valeur de hachage ; il est conseillé de mélanger d'une manière ou d'une autre (par exemple en utilisant ou exclusif) les valeurs de hachage des composants de l'objet qui jouent également un rôle dans la comparaison des objets.

Je pense que pour les types intégrés à Python, tous les types hachables sont également immuables.

Il serait difficile mais peut-être pas impossible d'avoir un objet mutable qui soit néanmoins défini __hash__() .

Answer 3

Il existe une relation implicite, même s'il n'y a pas de relation explicite forcée entre immuable et hachable en raison de l'interaction entre

1. Les objets hachables qui sont comparables doivent avoir la même valeur de hachage.
2. Un objet est hachable s'il possède une valeur de hachage qui ne change jamais pendant sa durée de vie.

Il n'y a pas de problème ici, à moins que vous ne redéfinissiez __eq__ donc la classe des objets définit l'équivalence sur la valeur.

Une fois que vous avez fait cela, vous devez trouver une fonction de hachage stable qui renvoie toujours la même valeur pour les objets qui représentent la même valeur (par exemple, où __eq__ ) renvoie Vrai, et ne change jamais pendant la durée de vie d'un objet.

Il est difficile de voir une application où cela est possible, considérez une classe possible A qui répond à ces exigences. Bien qu'il existe le cas dégénéré évident où __hash__ renvoie une constante.

Maintenant

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

En fait cela signifie qu'à la création hash(b) == hash(c), malgré le fait qu'ils ne sont jamais comparés égaux. J'ai du mal à voir comment définir utilement __hash__ () pour un objet mutable qui définit la comparaison par valeur.

Note : __lt__ , __le__ , __gt__ y __ge__ Les comparaisons ne sont pas affectées. Vous pouvez donc toujours définir un ordre de classement des objets hachables, mutables ou non, en fonction de leur valeur.

Answer 4

Immuable signifie que l'objet ne changera pas de manière significative pendant sa durée de vie. Il s'agit d'une idée vague mais courante dans les langages de programmation.

La capacité de hachage est légèrement différente, et fait référence à la comparaison.

hachable Un objet est hachable s'il a une valeur de hachage qui ne change jamais pendant sa durée de vie (il a besoin d'une valeur de hachage). change pendant sa durée de vie (il a besoin d'une __hash__() ), et peut être comparé à d'autres objets (il a besoin d'une __eq__() o __cmp__() ). Les objets hachables qui sont comparables doivent avoir la même valeur de hachage.

Toutes les classes définies par l'utilisateur ont __hash__ qui, par défaut, ne renvoie que l'identifiant de l'objet. Ainsi, un objet qui répond aux critères de hachage n'est pas nécessairement immuable.

Les objets de toute nouvelle classe que vous déclarez peuvent être utilisés comme clé de dictionnaire, à moins que vous ne l'empêchiez, par exemple, en lançant de __hash__

On pourrait dire que tous les objets immuables sont hachables, car si le hachage change pendant la durée de vie de l'objet, cela signifie que l'objet a muté.

Mais pas tout à fait. Considérons un tuple qui a une liste (mutable). Certains disent que le tuple est immuable, mais en même temps il n'est pas forcément hachable (throws).

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

Le hachage et l'immuabilité font référence à l'instancess de l'objet, pas au type. Par exemple, un objet de type tuple peut être hachable ou non.

Answer 5

Hachable signifie que la valeur d'une variable peut être représentée (ou, plutôt, encodée) par une constante - chaîne de caractères, nombre, etc. Or, quelque chose qui est sujet à changement (mutable) ne peut être représenté par quelque chose qui ne l'est pas. Par conséquent, toute variable qui est mutable ne peut pas être hachable et, de la même manière, seules les variables immuables peuvent être hachables.

J'espère que cela vous aidera ...