Como se puede observar en la figura 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.