Curiosidad sobre __hash__()

[Rodrigo Gallardo]

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.
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes