Que fait le hash en python ?

Question

J'ai vu un exemple de code où hash est appliquée à un tuple. En conséquence, elle renvoie un nombre entier négatif. Je me demande ce que fait cette fonction. Google ne m'aide pas. J'ai trouvé une page qui explique comment le hachage est calculé mais elle n'explique pas pourquoi nous avons besoin de cette fonction.

Answer 1

Un hash est un nombre entier de taille fixe qui identifie une valeur particulière. . Chaque valeur doit avoir son propre hachage. Ainsi, pour une même valeur, vous obtiendrez le même hachage même s'il ne s'agit pas du même objet.

>>> hash("Look at me!")
4343814758193556824
>>> f = "Look at me!"
>>> hash(f)
4343814758193556824

Les valeurs de hachage doivent être créées de manière à ce que les valeurs résultantes soient distribuées de manière égale afin de réduire le nombre de collisions de hachage. On parle de collisions de hachage lorsque deux valeurs différentes ont le même hachage. Par conséquent, des modifications relativement mineures donnent souvent lieu à des hachages très différents.

>>> hash("Look at me!!")
6941904779894686356

Ces chiffres sont très utiles, car ils permettent de rechercher rapidement des valeurs dans une grande collection de valeurs. Deux exemples de leur utilisation sont les fonctions de Python suivantes set y dict . Dans un list si vous voulez vérifier si une valeur est dans la liste, avec if x in values: Python doit parcourir toute la liste et comparer les éléments suivants x avec chaque valeur de la liste values . Cela peut prendre beaucoup de temps pour une longue list . Dans un set Python garde la trace de chaque hachage, et lorsque vous tapez if x in values: Python obtiendra la valeur de hachage pour x , consultez-le dans une structure interne, puis comparez seulement x avec les valeurs qui ont le même hash que x .

La même méthodologie est utilisée pour la recherche dans les dictionnaires. Cela rend la recherche dans set y dict très rapidement, tout en cherchant dans list est lent. Cela signifie également que vous pouvez avoir des objets non-hashables dans un fichier list mais pas dans un set ou comme clés dans un dict . L'exemple typique d'objets non hachables est tout objet qui est mutable, c'est-à-dire que vous pouvez changer sa valeur. Si vous avez un objet mutable, il ne devrait pas être hachable, car son hachage changera au cours de sa durée de vie, ce qui causerait beaucoup de confusion, car un objet pourrait se retrouver sous la mauvaise valeur de hachage dans un dictionnaire.

Notez que le hachage d'une valeur ne doit être le même que pour une seule exécution de Python. Dans Python 3.3, ils seront en fait modifiés à chaque nouvelle exécution de Python :

$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
1849024199686380661
>>> 
$ /opt/python33/bin/python3
Python 3.3.2 (default, Jun 17 2013, 17:49:21) 
[GCC 4.6.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash("foo")
-7416743951976404299

Il est ainsi plus difficile de deviner la valeur de hachage d'une certaine chaîne de caractères, ce qui constitue un élément de sécurité important pour les applications Web, etc.

Les valeurs de hachage ne doivent donc pas être stockées de manière permanente. Si vous avez besoin d'utiliser des valeurs de hachage de façon permanente, vous pouvez vous pencher sur les types de hachage plus "sérieux", fonctions de hachage cryptographiques qui peut être utilisé pour faire des sommes de contrôle vérifiables de fichiers, etc.

Answer 2

TL;DR :

Veuillez vous référer à le glossaire : hash() est utilisé comme un raccourci pour comparer des objets, un objet est considéré comme hachable s'il peut être comparé à d'autres objets. c'est pourquoi nous utilisons hash() . Il est également utilisé pour accéder dict y set qui sont mis en œuvre en tant que tables de hachage redimensionnables en CPython .

Considérations techniques

• En général, la comparaison d'objets (qui peut impliquer plusieurs niveaux de récursion) est coûteuse.
• de préférence, le hash() est un ordre de grandeur (ou plusieurs) moins coûteux.
• La comparaison de deux hachages est plus facile que la comparaison de deux objets, c'est là que se trouve le raccourci.

Si vous lisez sur comment les dictionnaires sont mis en œuvre ils utilisent des tables de hachage, ce qui signifie que la dérivation d'une clé à partir d'un objet est la pierre angulaire de la recherche d'objets dans les dictionnaires de l'UE. O(1) . Cela dépend cependant beaucoup de votre fonction de hachage qui doit être résistant aux collisions . Le site le pire cas pour obtenir un article dans un dictionnaire est en fait O(n) .

À ce propos, 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, que doit retourner la fonction de hachage ? S'agit-il de la même clé ou d'une clé différente ? Il s'agit de dépend de sur la façon dont vous définissez votre fonction de hachage.

Apprendre par l'exemple :

Imaginez que nous ayons 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
... 

Remarque : tout ceci est basé sur l'hypothèse que le SSN ne change jamais pour un individu (je ne sais même pas où vérifier ce fait auprès 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')

Voici ce que nous savons :

>>> bob == jim
True

Mais il s'agit de deux objets différents avec une mémoire allouée différente, tout comme deux enregistrements différents de la même personne :

>>> bob is jim
False

Maintenant vient la partie où hash() est pratique :

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

Devinez quoi :

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

A 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

Qu'est-ce qui vient de se passer ? C'est une collision. Parce que hash(jim) == hash(hash(jim)) qui sont tous deux des entiers, nous devons comparer l'entrée de __getitem__ avec tous les éléments qui entrent en collision. La fonction intégrée int n'a pas de ssn attribut pour qu'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 en cas de collision, la comparaison est effectuée, les objets ne sont plus égaux, ce qui signifie qu'elle soulève avec succès un problème de collision. KeyError .

Answer 3

Le Python documents pour hash() l'État :

Les valeurs de hachage sont des entiers. Elles sont utilisées pour comparer rapidement les clés d'un dictionnaire lors d'une recherche dans le dictionnaire.

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

En outre, le pour le dict type l'État :

Les valeurs qui ne sont pas hachable Les 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ées comme clés.

Answer 4

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 Wikipédia sur les tables de hachage .

Answer 5

Vous pouvez utiliser le Dictionary type de données en python. Il est très très similaire au hash et il supporte également l'imbrication, similaire au hash imbriqué.

Ejemplo:

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
dict['Age'] = 8; # update existing entry
dict['School'] = "DPS School" # Add new entry

print ("dict['Age']: ", dict['Age'])
print ("dict['School']: ", dict['School'])

Pour plus d'informations, veuillez vous référer à tutoriel sur le type de données dictionnaire .