Recorrido narrado
Insertar con crecimiento
función insertar(t, k, v): si (t.n + 1) / t.capacidad > límite: crecer(t, 2 × t.capacidad) agregar (k, v) a la cubeta hash(k) mod t.capacidad t.n ← t.n + 1función crecer(t, nueva): viejas ← t.cubetas t.cubetas ← nueva cantidad de cubetas vacías t.capacidad ← nueva para cada cubeta c en viejas: para cada (k, v) en c: agregar (k, v) a la cubeta hash(k) mod nuevaCrecer recorre todas las claves: O(n). Pero, como en el array dinámico, duplicar hace que pase pocas veces: el total de recolocaciones para n inserciones es menor que 2n.
Por eso insertar es O(1) esperado y amortizado: esperado por la función hash, amortizado por el crecimiento. Las dos condiciones juntas.
Su fila en la tabla de costos
La tabla hash con encadenamiento que crece mantiene la carga acotada; esa condición es la que sostiene el O(1) esperado.
| Representación | buscar(k) |
insertar(k) |
borrar(k) |
|---|---|---|---|
| tabla hash que crece al superar el límite de carga | O(1) esperado; O(n) en el peor caso | O(1) esperado y amortizado; O(n) la inserción que crece | O(1) esperado |
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.