Curiosidad sobre __hash__()

[Pepe Aracil]

Rodrigo Gallardo escribió:
> On Wed, Feb 04, 2009 at 10:49:42AM +0100, Francesc Alted wrote:
>> A Wednesday 04 February 2009, Pepe Aracil escrigué:
>>> Hola lista.
>>>
>>> Me ha sorprendido que la función hash "solo"
>>> devuelva un entero.
>>>
>>> (1,2,3,4).__hash__()
>>> 89902565
>>>
>>> ¿No os parece que aumenta mucho las probabilidades
>>> de que se produzca una colisión no deseada en un
>>> diccionario por ej.?
>> Bueno, si la función hash está bien elegida, un entero de 32-bit da para 
>> 2**31 hash diferentes, y ya tendria que ser grande el diccionario para 
>> que esto sea un problema.
> 
> Esto es la "paradoja del cumpleaños"
> 
> http://en.wikipedia.org/wiki/Birthday_paradox
> http://es.wikipedia.org/wiki/Paradoja_del_cumplea%C3%B1os
> 
> Suponiendo que la distribución de los hash es uniforme (lo cual
> depende de los datos a guardar y de la implementación exacta de la
> función) tenemos que con 32 bits, un diccionario de 2^16 = 65536
> entradas tiene una probabilidad de 50% de tener una colisión. Con 64
> bits, necesita tener 2^32 entradas para la misma probabilidad.

Creo que con un diccionario de 65536 entradas y un hash de 32 bits,
tengo 1/65536 posibilidades de tener una colisión.

Son pocas posibilidades, pero yo no utilizaría un hash de 32 bits para 
"cosas" críticas.

Saludos.

_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes