Funciones Hash perfectas

Question

Recientemente me han hecho una tarea que me preguntaba si, dada una lista de teclas, sería posible realizar una función hash que no tenga colisiones. Investigando un poco, descubrí que dada una lista preordenada de claves, son posibles las funciones hash perfectas.

Sin embargo, no estoy muy seguro de qué decir más allá de eso. ¿Podría alguien darme algún consejo sobre cómo se hacen las funciones de hash perfectas, o qué le hace exactamente una lista predefinida a un creador de funciones hash que permite una función perfecta?

Gracias por cualquier ayuda.

Answer 1

La única manera de no tener colisiones es tener una relación de 1 a 1 entre la clave y el valor hash. El rango de los valores hash debe ser al menos tan grande como el número de claves, y la función de asignación debe transformar cada clave en un valor único. Mucha más información aquí: http://en.wikipedia.org/wiki/Perfect_hash