Où puis-je trouver la source ou l'algorithme de la fonction hash() de Python?

Question

>>> hash("\x01") 
128000384 
>>> hash("\x02") 
256000771 
>>> hash("\x03") 
384001154 
>>> hash("\x04") 
512001541 

partie intéressante est 128000384 x 2 n'est pas 256000771, ainsi que d'autres

Je me demande à quel que fonctionne l'algorithme et veulent apprendre quelque chose sur elle.

Answer 1

Si vous téléchargez le code source de Python, vous le trouverez à coup sûr! Mais gardez à l'esprit que la fonction de hachage est implémentée différemment pour chaque type d'objet. Par exemple, vous trouverez la fonction de hachage unicode dans Objects/unicodeobject.c dans la fonction unicode_hash. Vous devrez peut-être regarder un peu plus pour trouver la fonction de hachage de chaîne. Trouvez la structure définissant l'objet qui vous intéresse, et dans le champ tp_hash, vous trouverez la fonction qui calcule le code de hachage de cet objet.

Pour l'objet chaîne: Le code exact se trouve dans Objects/stringobject.c dans la fonction string_hash:

static long string_hash(PyStringObject *a) 
{ 
    register Py_ssize_t len; 
    register unsigned char *p; 
    register long x; 

    if (a->ob_shash != -1) 
     return a->ob_shash; 
    len = Py_SIZE(a); 
    p = (unsigned char *) a->ob_sval; 
    x = *p << 7; 
    while (--len >= 0) 
     x = (1000003*x)^*p++; 
    x ^= Py_SIZE(a); 
    if (x == -1) 
     x = -2; 
    a->ob_shash = x; 
    return x; 
} 

Answer 2

je vous recommande de lire l'entrée de Wikipedia pour les fonctions de hachage (http://en.wikipedia.org/wiki/Hash_function) pour mieux comprendre les fonctions de hachage . Vous aurez beaucoup de réponses pour la mise en œuvre!

Pour résumer quelques points clés (non seulement pour cette fonction spécifique, mais en général pour toutes les fonctions de hachage):

• sur une entrée donnée (en fonction des besoins sera un numéro, une chaîne, et l'objet , etc.) peut produire une sortie plus petite et de longueur fixe. Habituellement (pour ne pas dire toujours), est un nombre entier.
• Différentes entrées produisent différentes sorties. Comme la sortie est plus petite que l'entrée, il y aura TOUJOURS différentes entrées qui produisent la même sortie. C'est l'appel 'hash collition' et devrait être rare si la fonction de hachage est bien conçue
• Pour certains types de fonctions de hachage, il est important d'obtenir le hachage d'une donnée d'entrée. que les entrées similaires produisent pas de sorties similaires. pour d'autres, ce n'est pas une condition nécessaire, mais il est généralement atteint. Voilà pourquoi hash("\x02") n'est pas 2*hash("\x01")

Fondamentalement, les fonctions de hachage sont utilisées pour utiliser un entier à la place de l'objet complet , que vous pouvez gérer plus facilement et plus efficacement