¿Por qué -1 y -2 ambos hash a -2 en CPython?

Question

Duplicar posibles:
When is a python object's hash computed and why is the hash of -1 different?

¿Por qué -1 y -2 tanto hash para el mismo número si Python?

Como lo hacen, ¿cómo distingue Python estos dos números?

>>> -1 is -2 
False 
>>> hash(-1) is hash(-2) 
True 
>>> hash(-1) 
-2 
>>> hash(-2) 
-2 

Answer 1

-1 es un valor reservado en el nivel C de CPython que evita que las funciones de hash de ser capaz de producir un valor de hash de -1. Tal como lo señala DSM, no ocurre lo mismo en IronPython y PyPy donde hash(-1) != hash(-2).

Ver this Quora answer:

Si se escribe un tipo en un módulo de extensión C y proporcionar un método tp_hash , hay que evitar -1 - si regresa -1, Python asumirá que significaba para lanzar una error.

Si escribe una clase en Python puro y proporciona un método __hash__, no hay tal requisito, afortunadamente. Pero eso es porque el código C que invoca el método __hash__ lo hace por usted - si sus __hash__ vuelve -1, luego hash() aplicados a su objeto realmente va a volver -2.

Qué realmente sólo vuelve a empaquetar la información de effbot:

El hash valor -1 está reservado (se utiliza para marcar los errores en la implementación C ). Si el algoritmo hash genera este valor, simplemente usa -2 en su lugar.

También puede ver esto en la fuente. Por ejemplo para el objeto de Python 3 int, esto es al final de the hash implementation:

if (x == (Py_uhash_t)-1) 
    x = (Py_uhash_t)-2; 
return (Py_hash_t)x; 

---

Dado que hacen, cómo lo dice Python estos dos números separados?

Dado que todas las funciones hash asignan un gran espacio de entrada a un espacio de entrada más pequeño, siempre se esperan colisiones, sin importar qué tan buena sea la función hash. Piensa en hash strings, por ejemplo. Si los códigos hash son enteros de 32 bits, tiene 2^32 (poco más de 4 mil millones) de códigos hash. Si considera todas las cadenas ASCII de longitud 6, tiene (2^7)^6 (poco menos de 4.4 trillones) elementos diferentes en su espacio de entrada. Con solo este conjunto, se garantiza que tendrá muchas colisiones, sin importar lo bueno que sea. ¡Agregue caracteres Unicode y cadenas de longitud ilimitada a eso!

Por lo tanto, el código hash solo indica en la ubicación de un objeto, se sigue una prueba de igualdad para probar las claves candidatas. Para implementar una prueba de membresía en un conjunto de tablas hash, el código hash le da un número de "depósito" para buscar el valor. Sin embargo, todos los elementos establecidos con el mismo código hash están en el depósito. Para esto, también necesita una prueba de igualdad para distinguir entre todos los candidatos en el cubo.

Este código hash y dualidad de igualdad se insinúa en el CPython documentation on hashable objects. En otros lenguajes/marcos, existe una regla/regla de que si proporciona una función de código hash personalizado, también debe proporcionar una prueba de igualdad personalizada (realizada en los mismos campos que la función de código hash).

---

De hecho, la dirección actual versión de Python exactamente esto, con un parche de seguridad que aborda el tema de eficiencia cuando esto (valores hash idénticos, pero en una escala masiva) se utiliza como un ataque de denegación de servicio - http://mail.python.org/pipermail/python-list/2012-April/1290792.html