Que signifie «hashable» en Python?

J'ai essayé de chercher sur Internet mais je n'ai pas trouvé la signification de hashable.

Quand ils disent que les objets sont hashableou hashable objectsqu'est-ce que cela signifie?

Depuis le glossaire Python :

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

Hashability rend un objet utilisable en tant que clé de dictionnaire et membre d'ensemble, car ces structures de données utilisent la valeur de hachage en interne.

Tous les objets intégrés immuables de Python sont hachables, alors qu'aucun conteneur mutable (comme les listes ou les dictionnaires) ne le sont. Les objets qui sont des instances de classes définies par l'utilisateur sont hachables par défaut; ils se comparent tous inégaux et leur valeur de hachage est la leur id().

Toutes les réponses ici ont une bonne explication fonctionnelle des objets hachables en python, mais je pense qu'il faut d'abord comprendre le terme Hashing.

Le hachage est un concept en informatique utilisé pour créer des structures de données pseudo-aléatoires hautes performances dans lesquelles une grande quantité de données doit être stockée et accessible rapidement.

Par exemple, si vous avez 10 000 numéros de téléphone et que vous souhaitez les stocker dans un tableau (qui est une structure de données séquentielle qui stocke les données dans des emplacements de mémoire contigus et fournit un accès aléatoire), mais que vous ne disposez peut-être pas de la quantité requise de contigus emplacements de mémoire.

Ainsi, vous pouvez à la place utiliser un tableau de taille 100 et utiliser une fonction de hachage pour mapper un ensemble de valeurs aux mêmes indices, et ces valeurs peuvent être stockées dans une liste liée. Cela fournit des performances similaires à celles d'une baie.

Maintenant, une fonction de hachage peut être aussi simple que de diviser le nombre par la taille du tableau et de prendre le reste comme index.

Pour plus de détails, consultez https://en.wikipedia.org/wiki/Hash_function

Voici une autre bonne référence: http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html

Tout ce qui n'est pas mutable (signifie mutable, susceptible de changer) peut être haché. Outre la fonction de hachage à rechercher, si une classe l'a, par exemple. dir(tuple)et à la recherche de la __hash__méthode, voici quelques exemples

#x = hash(set([1,2])) #set unhashable
x = hash(frozenset([1,2])) #hashable
#x = hash(([1,2], [2,3])) #tuple of mutable objects, unhashable
x = hash((1,2,3)) #tuple of immutable objects, hashable
#x = hash()
#x = hash({1,2}) #list of mutable objects, unhashable
#x = hash([1,2,3]) #list of immutable objects, unhashable

Liste des types immuables:

int, float, decimal, complex, bool, string, tuple, range, frozenset, bytes

Liste des types mutables:

list, dict, set, bytearray, user-defined classes

D'après ce que je comprends, selon le glossaire Python, lorsque vous créez une instance d'objets hachables, une valeur immuable est également calculée en fonction des membres ou des valeurs de l'instance. Par exemple, cette valeur pourrait ensuite être utilisée comme clé dans un dict comme ci-dessous:

>>> tuple_a = (1,2,3)
>>> tuple_a.__hash__()
2528502973977326415
>>> tuple_b = (2,3,4)
>>> tuple_b.__hash__()
3789705017596477050
>>> tuple_c = (1,2,3)
>>> tuple_c.__hash__()
2528502973977326415
>>> id(a) == id(c)  # a and c same object?
False
>>> a.__hash__() == c.__hash__()  # a and c same value?
True
>>> dict_a = {}
>>> dict_a[tuple_a] = 'hiahia'
>>> dict_a[tuple_c]
'hiahia'

nous pouvons trouver que les valeurs de hachage de tuple_a et tuple_c sont les mêmes puisqu'elles ont les mêmes membres. Lorsque nous utilisons tuple_a comme clé dans dict_a, nous pouvons constater que la valeur de dict_a [tuple_c] est la même, ce qui signifie que, lorsqu'ils sont utilisés comme clé dans un dict, ils renvoient la même valeur car les valeurs de hachage sont le même. Pour les objets qui ne sont pas hachables, la méthode de hachage est définie comme Aucun:

>>> type(dict.__hash__) 
<class 'NoneType'>

Je suppose que cette valeur de hachage est calculée lors de l'initialisation de l'instance, pas de manière dynamique, c'est pourquoi seuls les objets immuables sont hachables. J'espère que cela t'aides.

Permettez-moi de vous donner un exemple de travail pour comprendre les objets hachables en python. Je prends 2 tuples pour cet exemple.Chaque valeur d'un tuple a une valeur de hachage unique qui ne change jamais pendant sa durée de vie. Donc, sur la base de cette valeur, la comparaison entre deux tuples est effectuée. Nous pouvons obtenir la valeur de hachage d'un élément de tuple en utilisant Id ().

En python, cela signifie que l'objet peut être membre d'ensembles afin de renvoyer un index. Autrement dit, ils ont une identité / un identifiant unique.

par exemple, en python 3.3:

la structure de données Les listes ne sont pas hachables mais la structure de données Les tuples sont hachables.

Hashable = capable d'être haché.

Ok, qu'est-ce que le hachage? Une fonction de hachage est une fonction qui prend un objet, disons une chaîne telle que «Python», et renvoie un code de taille fixe. Par souci de simplicité, supposons que la valeur de retour est un entier.

Lorsque j'exécute hash ('Python') dans Python 3, j'obtiens 5952713340227947791 comme résultat. Différentes versions de Python sont libres de modifier la fonction de hachage sous-jacente, vous obtiendrez donc probablement une valeur différente. L'important est que peu importe maintenant que je lance plusieurs fois hash ('Python'), j'obtiendrai toujours le même résultat avec la même version de Python.

Mais hash ('Java') renvoie 1753925553814008565. Donc, si l'objet que je hache change, le résultat change également. D'un autre côté, si l'objet que je hache ne change pas, le résultat reste le même.

Pourquoi est-ce important?

Eh bien, les dictionnaires Python, par exemple, exigent que les clés soient immuables. Autrement dit, les clés doivent être des objets qui ne changent pas. Les chaînes sont immuables en Python, tout comme les autres types de base (int, float, bool). Les tuples et les frozensets sont également immuables. Les listes, en revanche, ne sont pas immuables (c'est-à-dire qu'elles sont modifiables) car vous pouvez les modifier. De même, les dictionnaires sont mutables.

Donc, quand nous disons que quelque chose est hachable, nous voulons dire qu'il est immuable. Si j'essaye de passer un type mutable à la fonction hash (), cela échouera:

>>> hash('Python')
1687380313081734297
>>> hash('Java')
1753925553814008565
>>>
>>> hash([1, 2])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> hash({1, 2})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'
>>> hash({1 : 2})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>>
>>> hash(frozenset({1, 2}))
-1834016341293975159
>>> hash((1, 2))
3713081631934410656

En Python, tout objet immuable (tel qu'un entier, un booléen, une chaîne, un tuple) est hachable, ce qui signifie que sa valeur ne change pas pendant sa durée de vie. Cela permet à Python de créer une valeur de hachage unique pour l'identifier, qui peut être utilisée par les dictionnaires pour suivre des clés uniques et des ensembles pour suivre des valeurs uniques.

C'est pourquoi Python nous oblige à utiliser des types de données immuables pour les clés d'un dictionnaire.

Pour créer une table de hachage à partir de zéro, toutes les valeurs doivent être définies sur "Aucune" et modifiées une fois qu'une exigence se présente. Les objets hachables font référence aux types de données modifiables (dictionnaire, listes, etc.). En revanche, les ensembles ne peuvent pas être réinitialisés une fois affectés, les ensembles ne sont donc pas hachables. Alors que, la variante de set () - frozenset () - est hachable.