Simulación

Encadenamiento

La forma más simple de manejar colisiones es el encadenamiento: cada cubeta guarda una lista con todas las claves que caen en ella.

insertar(k): calcular la cubeta y añadir k a su lista (si no está).
buscar(k): calcular la cubeta y recorrer solo su lista.

Con capacidad 4 y hash(k) = k, insertas 7, 11, 2 y 15.

La cubeta de destino lleva el borde grueso y la clave recién añadida el asterisco. La cubeta 3 acaba con una cadena de tres claves.

Una tabla con encadenamiento tiene capacidad 5 y hash(k) = k. Insertas 12, 7, 21, 2 y 17, y cada cubeta añade al final de su lista. ¿Cómo quedan las cubetas y cuántas claves compara buscar(17)?Cubeta 1: [21]. Cubeta 2: [12]. Las otras claves se descartan por colisiónCubeta 1: [21]. Cubeta 2: [12, 7, 2, 17]. Compara 4 clavesCubeta 1: [21]. Cubeta 2: [12, 7, 2]. Cubeta 3: [17]. Compara 1 claveCubeta 1: [21]. Cubeta 2: [12, 7, 2, 17]. Compara 5 claves