Como se puede observar en la figura 7.1, la ganancia en eficiencia de una tabla
hash con respecto a una lista encadenada que contenga todos los elementos se
basa en que la longitud de las listas de colisiones es
sensiblemente menor que el número total de
elementos. Si una tabla tiene todas sus cadenas de colisión de igual
longitud, el tiempo de búsqueda se reduce sensiblemente. Sin embargo, en el
caso extremo en el que todos los elementos están en una única
cadena de colisión, la tabla tiene la misma eficiencia que una
lista encadenada.
Esta observación sugiere que la función de hash no sólo debe
producir un índice en la tabla, sino que para un número elevado de
elementos, debe producir estos índices lo más dispersos
posible. La especificación de una función hash es muy simple. En
el caso de estudio es una función que dado un número de
pasaporte devuelve un índice válido de la tabla, y este índice debe ser el
mismo para cadenas idénticas. Además, se requiere que el cálculo realizado
por esta función sea lo más eficiente posible puesto que se utiliza en todo
acceso a la tabla.
