Que fait hash en python?

TL; DR:

, Veuillez vous référer à le glossaire: hash() est utilisé comme un raccourci pour comparer des objets, un objet est réputé hashable s'il peut être comparé à d'autres objets. c'est pourquoi nous utilisons hash(). Il est également utilisé pour accéder aux éléments dict et set qui sont implémentés en tant que tables de hachage redimensionnables dans CPython .

Considérations Techniques

• généralement comparer des objets (qui peuvent impliquer plusieurs niveaux de récursivité) est coûteux.
• de préférence, la fonction hash() est d'un ordre de grandeur (ou plusieurs) moins cher.
• comparer deux hachages est plus facile que de comparer deux objets, c'est là que se trouve le raccourci.

Si vous lisez à propos de comment les dictionnaires sont implémentés , ils utilisent des tables de hachage, ce qui signifie que dériver une clé à partir d'un objet est une pierre angulaire pour récupérer des objets dans les dictionnaires dans O(1). C'est cependant très dépendant de votre fonction de hachage résistant aux collisions . Le pire cas pour obtenir un élément dans un dictionnaire est en fait O(n).

Sur cette note, les objets mutables ne sont généralement pas hachables. La propriété hashable signifie que vous pouvez utiliser un objet comme clé. Si la valeur de hachage est utilisée comme clé et que le contenu de ce même objet change, alors que devrait retourner la fonction de hachage? Est - ce la même clé ou une autre? Il dépend de la façon dont vous définissez votre fonction de hachage.

Apprendre par exemple:

Imaginez que nous avons cette classe:

>>> class Person(object):
...     def __init__(self, name, ssn, address):
...         self.name = name
...         self.ssn = ssn
...         self.address = address
...     def __hash__(self):
...         return hash(self.ssn)
...     def __eq__(self, other):
...         return self.ssn == other.ssn
... 

Veuillez noter: tout cela est basé sur l'hypothèse que le SSN ne change jamais pour un individu (Je ne sais même pas où vérifier réellement ce fait à partir d'une source faisant autorité).

Et nous avons Bob:

>>> bob = Person('bob', '1111-222-333', None)

Bob va voir un juge pour changer son nom:

>>> jim = Person('jim bo', '1111-222-333', 'sf bay area')

C'est ce que nous savons:

>>> bob == jim
True

Mais ce sont deux objets différents avec une mémoire différente allouée, tout comme deux objets différents enregistrements de la même personne:

>>> bob is jim
False

Vient maintenant la partie où hash () est pratique:

>>> dmv_appointments = {}
>>> dmv_appointments[bob] = 'tomorrow'

Devinez quoi:

>>> dmv_appointments[jim] #?
'tomorrow'

À partir de deux enregistrements différents, vous pouvez accéder aux mêmes informations. Maintenant, essayez ceci:

>>> dmv_appointments[hash(jim)]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 9, in __eq__
AttributeError: 'int' object has no attribute 'ssn'
>>> hash(jim) == hash(hash(jim))
True

Ce qui s'est passé? C'est une collision. Parce que {[16] } qui sont les deux entiers btw, nous devons comparer l'entrée de __getitem__ avec tous les éléments qui entrent en collision. Le int intégré n'a pas d'attribut ssn donc il se déclenche.

>>> del Person.__eq__
>>> dmv_appointments[bob]
'tomorrow'
>>> dmv_appointments[jim]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: <__main__.Person object at 0x7f611bd37110>

Dans ce dernier exemple, je montre que même avec une collision, la comparaison est effectuée, les objets ne sont plus égaux, ce qui signifie qu'il soulève avec succès un KeyError.

Les documents Python pour hash() État:

Les valeurs de hachage sont des entiers. Ils sont utilisés pour comparer rapidement les clés du dictionnaire lors d'une recherche de dictionnaire.

Les dictionnaires Python sont implémentés en tant que tables de hachage. Donc, chaque fois que vous utilisez un dictionnaire, hash() est appelé sur les clés que vous passez pour l'affectation, ou la recherche.

De plus, les documents pour l'étatdict type :

Valeurs qui ne sont pas hashable , c'est-à-dire des valeurs contenant des listes, des dictionnaires ou d'autres types mutables (qui sont comparés par valeur plutôt que par identité d'objet) ne peuvent pas être utilisés comme clés.

Le hachage est utilisé par les dictionnaires et les ensembles pour rechercher rapidement l'objet. Un bon point de départ est L'article de Wikipedia sur les tables de hachage .