¿Dónde puedo encontrar la fuente o el algoritmo de la función hash() de Python?

Question

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

parte interesante es 128000384 x 2 no es 256000771, y también otros

Me pregunto cómo funciona el algoritmo y quieren aprender algo sobre ella.

Answer 1

Si descarga el código fuente de Python, ¡lo encontrará con seguridad! Pero tenga en cuenta que la función hash se implementa para cada tipo de objeto de forma diferente.

Por ejemplo, encontrará la función hash Unicode en Objects/unicodeobject.c en la función unicode_hash. Es posible que tenga que buscar un poco más para encontrar la función hash de cadena. Encuentre la estructura que define el objeto que le interesa y, en el campo tp_hash, encontrará la función que calcula el código hash de ese objeto.

Para el objeto de cadena: El código exacto se encuentra en Objects/stringobject.c en la función 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

recomiendo que lea la entrada de Wikipedia para las funciones de hash (http://en.wikipedia.org/wiki/Hash_function) para entender mejor las funciones de hash . ¡Obtendrá muchas respuestas para la implementación!

resumir algunos puntos clave (no sólo para esta función específica, pero en general para todas las funciones de hash):

• en una entrada determinada (en función de las necesidades será un número, una cadena, y el objeto , etc.) puede producir una salida que es más pequeña y de longitud fija. Por lo general (por no decir siempre), es un número entero.
• Las diferentes entradas producen salidas diferentes. Como la salida es más pequeña que la entrada, SIEMPRE habrá diferentes entradas que produzcan la misma salida. Esto se llama 'colisión hash' y debería ser raro si la función hash está bien diseñada.
• El proceso debe ser eficiente, por lo que es rápido obtener el hash de una entrada de datos
• Para algunos tipos de funciones hash es importante que los insumos similares producen salidas que no sean similares. para otros, no es un requisito, pero se consigue normalmente. es por eso que hash("\x02") no es 2*hash("\x01")

Básicamente, las funciones hash se utilizan para utilizar un número entero en el lugar del objeto completo , que puede administrar más fácil y más eficientemente