Modelo por capas

El contrato de una clave

Una tabla hash usa dos operaciones sobre las claves:

• hash(k): para elegir la cubeta;
• igualdad (a = b): para reconocer la clave dentro de la cubeta.

Para que funcione, tienen que cumplir un contrato:

si a = b, entonces hash(a) = hash(b)

Si dos claves iguales dieran hashes distintos, irían a cubetas distintas y la búsqueda miraría en la equivocada. Lo contrario no hace falta: claves distintas pueden tener el mismo hash (es una colisión).

En el fenómeno, el punto (3, 4) usaba una igualdad que compara x e y, pero un hash calculado a partir de su posición en memoria: dos puntos (3, 4) creados por separado daban hashes distintos.