must - Construido en la función python hash()

python hashmap

Question

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 dará los mismos resultados en diferentes plataformas (Windows, Linux, Mac)?

Answer 1

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

Por ejemplo:

El valor hexadecimal 0xADFE74A5 representa el 0xADFE74A5 sin 2919134373 y el firmado -1375832923 . El valor de corrección debe estar firmado (bit de signo = 1) pero Python lo convierte como no firmado y tenemos un valor de hash incorrecto después de la conversión de 64 a 32 bits.

Ten cuidado al usar:

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

Answer 2

Como se indica en la documentación, la función integrada hash () no está diseñada para almacenar los hashes resultantes en algún lugar externo. Se utiliza para proporcionar el valor de hash del objeto, para 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 método __hash__ del objeto en lugar de los algoritmos hash "normales", como SHA.

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

Answer 3

El valor de PYTHONHASHSEED se puede usar para inicializar los valores hash.

Tratar:

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

Answer 4

En una suposición, AppEngine está utilizando una implementación de 64 bits de Python (-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 significativamente comparables entre diferentes implementaciones.

Answer 5

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

Answer 6

Hash polinomial para cadenas. 1000000009 y 239 son números primos arbitrarios. Es poco probable que tenga colisiones por accidente. La aritmética modular no es muy rápida, pero para prevenir colisiones esto es más confiable que tomar un módulo de potencia de 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

Answer 7

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

De forma predeterminada, los __hash__() de los objetos str , bytes y datetime están "en sal" 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 la intención de proporcionar protección contra una denegación de servicio causada por entradas cuidadosamente elegidas que explotan el peor de los casos de una inserción dict, O (n²) complejidad. Ver http://www.ocert.org/advisories/ocert-2011-003.html para más detalles.

Cambiar los valores de hash afecta el orden de iteración de los dicts , los sets y otras asignaciones. Python nunca ha hecho garantías sobre este orden (y generalmente varía entre compilaciones de 32 bits y de 64 bits).

Incluso ejecutarse en la misma máquina arrojará resultados variables en todas las invocaciones:

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

Mientras:

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

Ver también la variable de entorno PYTHONHASHSEED :

Si esta variable no está configurada o configurada como random , se usa un valor aleatorio para generar los valores hash de str , bytes y objetos datetime .

Si PYTHONHASHSEED se establece en un valor entero, se usa como una semilla fija para generar el hash() de los tipos cubiertos por la asignación aleatoria de hash.

Su propósito es permitir el hash repetible, como autoevaluaciones para el propio intérprete, o permitir que un grupo de procesos de python comparta los valores hash.

El número entero debe ser un número decimal en el rango [0, 4294967295] . Al especificar el valor 0 se deshabilitará la aleatorización hash.

Por ejemplo:

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

Answer 8

La respuesta no es ninguna sorpresa: de hecho

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

así que si quiere obtener respuestas confiables en cadenas ASCII , solo obtenga los 32 bits más bajos como uint . La función hash para cadenas es de 32 bits segura y casi portátil.

Por otro lado, no puede confiar en que el hash() de cualquier objeto sobre el que no haya definido explícitamente el método __hash__ sea ​​invariante.

Sobre cadenas ASCII funciona simplemente 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 función c_mul es la multiplicación "cíclica" (sin desbordamiento) como en C.

Answer 9

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

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

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

Answer 10

Probablemente solo le pregunte a 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.

Answer 11

Usar hashlib como hash() fue diseñado para ser utilizado para :

Compare rápidamente claves de diccionario durante una búsqueda de diccionario

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