Modelo por capas

Función hash, cubetas y colisiones

Una tabla hash tiene un array de cubetas y una función hash: una función que convierte cualquier clave en un número entero. El índice de la cubeta es ese número reducido al tamaño de la tabla:

índice(clave) ← hash(clave) mod capacidad

Con capacidad 8 y hash(«ana») = 21, la clave va a la cubeta 21 mod 8 = 5.

La función hash tiene que dar siempre el mismo número para la misma clave, y repartir claves distintas lo más parejo posible.

Hay muchas más claves posibles que cubetas, así que dos claves distintas pueden dar el mismo índice: es una colisión. No es un error: es inevitable, y la tabla tiene que manejarlo.