Función hash () de Python incorporada

Windows XP, Python 2.5:

hash('http://stackoverflow.com') Result: 1934711907

Google App Engine ( http://shell.appspot.com/ ):

hash('http://stackoverflow.com') Result: -5768830964305142685

¿Porqué es eso? ¿Cómo puedo tener una función hash que me dé los mismos resultados en diferentes plataformas (Windows, Linux, Mac)?

Use hashlib como hash() fue diseñado para usarse para :

comparar rápidamente las claves del diccionario durante una búsqueda de diccionario

y por lo tanto no garantiza que será igual en todas las implementaciones de Python.

Como se indica en la documentación, la función hash () incorporada no está diseñada para almacenar los hash resultantes en algún lugar externo. Se utiliza para proporcionar el valor hash de los objetos, almacenarlos en diccionarios, etc. También es específico de la implementación (GAE usa una versión modificada de Python). Revisa:

>>> class Foo:
...     pass
... 
>>> a = Foo()
>>> b = Foo()
>>> hash(a), hash(b)
(-1210747828, -1210747892)

Como puede ver, son diferentes, ya que hash () usa el __hash__método del objeto en lugar de los algoritmos de hash "normales", como SHA.

Dado lo anterior, la elección racional es utilizar el módulo hashlib .

La respuesta no es ninguna sorpresa: de hecho

In [1]: -5768830964305142685L & 0xffffffff
Out[1]: 1934711907L

así que si desea obtener respuestas confiables en cadenas ASCII , simplemente obtenga los 32 bits inferiores como uint. La función hash para cadenas es segura para 32 bits y casi portátil.

Por otro lado, no puede confiar en absoluto en obtener el valor hash()de cualquier objeto sobre el que no haya definido explícitamente que el __hash__método sea invariante.

Sobre cadenas ASCII, funciona solo porque el hash se calcula en los caracteres individuales que forman la cadena, como el siguiente:

class string:
    def __hash__(self):
        if not self:
            return 0 # empty
        value = ord(self[0]) << 7
        for char in self:
            value = c_mul(1000003, value) ^ ord(char)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

donde la c_mulfunción es la multiplicación "cíclica" (sin desbordamiento) como en C.

La mayoría de las respuestas sugieren que esto se debe a las diferentes plataformas, pero hay más. De la documentación deobject.__hash__(self) :

Por defecto, los __hash__()valores de str, bytesy datetimelos objetos se “salada” con un valor aleatorio impredecible. Aunque permanecen constantes dentro de un proceso de Python individual, no son predecibles entre invocaciones repetidas de Python.

Esto tiene como objetivo proporcionar protección contra una denegación de servicio causada por entradas cuidadosamente seleccionadas que aprovechan el peor de los casos de una inserción de dict, complejidad O (n²). Consulte http://www.ocert.org/advisories/ocert-2011-003.html para obtener más detalles.

Cambio de valores hash afecta al orden de iteración dicts, sets y otras asignaciones. Python nunca ha ofrecido garantías sobre este pedido (y normalmente varía entre compilaciones de 32 y 64 bits).

Incluso la ejecución en la misma máquina producirá resultados variables en todas las invocaciones:

$ python -c "print(hash('http://stackoverflow.com'))"
-3455286212422042986
$ python -c "print(hash('http://stackoverflow.com'))"
-6940441840934557333

Mientras:

$ python -c "print(hash((1,2,3)))"
2528502973977326415
$ python -c "print(hash((1,2,3)))"
2528502973977326415

Consulte también la variable de entorno PYTHONHASHSEED:

Si esta variable no se establece o se establece en random, un valor aleatorio se utiliza para sembrar los hashes de str, bytesy datetimeobjetos.

Si PYTHONHASHSEEDse establece en un valor entero, se utiliza como semilla fija para generar hash()los tipos cubiertos por la aleatorización hash.

Su propósito es permitir el hash repetible, como las autopruebas del propio intérprete, o permitir que un grupo de procesos de Python comparta valores hash.

El número entero debe ser un número decimal en el rango [0, 4294967295]. Especificar el valor 0desactivará la aleatorización de hash.

Por ejemplo:

$ export PYTHONHASHSEED=0                            
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305
$ python -c "print(hash('http://stackoverflow.com'))"
-5843046192888932305

Los resultados de hash varían entre plataformas de 32 bits y 64 bits

Si un hash calculado debe ser el mismo en ambas plataformas, considere usar

def hash32(value):
    return hash(value) & 0xffffffff

Supongo que AppEngine está utilizando una implementación de Python de 64 bits (-5768830964305142685 no cabe en 32 bits) y su implementación de Python es de 32 bits. No puede confiar en que los hash de objetos sean comparables de manera significativa entre diferentes implementaciones.

Esta es la función hash que Google usa en producción para python 2.5:

def c_mul(a, b):
  return eval(hex((long(a) * b) & (2**64 - 1))[:-1])

def py25hash(self):
  if not self:
    return 0 # empty
  value = ord(self[0]) << 7
  for char in self:
    value = c_mul(1000003, value) ^ ord(char)
  value = value ^ len(self)
  if value == -1:
    value = -2
  if value >= 2**63:
    value -= 2**64
  return value

¿Qué pasa con el bit de señal?

Por ejemplo:

El valor hexadecimal 0xADFE74A5representa sin firmar 2919134373y firmado-1375832923 . El valor actual debe estar firmado (bit de signo = 1) pero Python lo convierte como sin firmar y tenemos un valor hash incorrecto después de la traducción de 64 a 32 bits.

Tenga cuidado al usar:

def hash32(value):
    return hash(value) & 0xffffffff

Hash polinomial para cadenas. 1000000009y 239son números primos arbitrarios. Es poco probable que se produzcan colisiones por accidente. La aritmética modular no es muy rápida, pero para prevenir colisiones es más confiable que tomarla como módulo 2. Por supuesto, es fácil encontrar una colisión a propósito.

mod=1000000009
def hash(s):
    result=0
    for c in s:
        result = (result * 239 + ord(c)) % mod
    return result % mod

El valor de PYTHONHASHSEED podría usarse para inicializar los valores hash.

Tratar:

PYTHONHASHSEED python -c 'print(hash('http://stackoverflow.com'))'

Probablemente solo pregunte la función proporcionada por el sistema operativo, en lugar de su propio algoritmo.

Como dicen otros comentarios, use hashlib o escriba su propia función hash.