Nota: Lo puesto aquí es solamente ilustrativo, no pretendo hacer de esto una teoría ni mucho menos. Las pruebas realizadas y puestas aquí pueden no serte de utilidad alguna. Pero si necesitas una guia de como analizar una tabla hash y la función generadora de claves, puede ser un buen comienzo.
Al iniciar el proyecto, lo primero que uno se pregunta, es que estructura es la mas adecuada. Para contestarla correctamente debemos tener en cuenta tres factores. Velocidad de búsqueda, uso de la memoria y si la información debe estar ordenada o no.
Quizas el que menos importe para aplicaciones no-embebidas es el punto de la memoria. En general cualquier estructura que tenga un orden de búsqueda decente no utiliza memoria a mansalva.
Por lo que nos quedan dos pesos pesados bien claros, velocidad de búsqueda y si la información debe o no estar ordenada.
Las dos estructuras obvias que uno piensa en estos casos son: arboles binarios balanceados (AVL o rojo-negro por ejemplo) y la sencilla pero ingeniosa tabla hash.
Recordemos que el órden de búsqueda de los arboles binarios balanceados es O(log2(n)) siendo n la cantidad de elementos insertados. El orden de inserción y eliminación de elementos a pesar de que tiene que realizar operaciones para balancear el arbol, también tienden al mismo orden que el de búsqueda. Pueden ver un análisis mas detallado aquí
Por otro lado, la tabla hash teórica tiende a un orden mínimo tanto en búsqueda como inserción y eliminación, que sería O(1). Esto en la práctica dificilmente se cumpla, ya que generar una clave hash unica e irrepetible para cada elemento es una tarea casi imposible para una cantidad grande de elementos. Hablamos del orden de 10000 elementos o mas. Si querés ver mas sobre tablas hash podes verlo aquí
Incluso una buena función generadora de hash como puede ser esta:
nos sigue devolviendo valores repetidos ante distintas entradas. Incluso aunque la cantidad de entradas en la tabla supere ampliamente la cantidad de elementos a insertar. Lo que nos ocasiona una tabla muy grande (3 o 4 veces la cantidad de items a insertar) y que nunca la podamos llenar correctamente. Al ser algo inevitable la repetición de entradas podemos aprovechar esto como un fuerte para disminuir el uso de los lugares no utilizados, un buen número para la longitud de la tabla es entre un 30% y un 60% del total de los items que tenemos (o planeamos tener). Por lo tanto, para 10.000 elementos deberiamos tener una tabla de 3.000 a 6.000 elementos. De esta forma tenemos un acceso promedio de 2 o 3 elementos por clave, distribuido normalmente con una baja desviación estándard. El algoritmo para sacar una desviación standard de valores acumulados es este:
.
Puedes ver la implementación aquí y el análisis de la tabla aquí