Recorrido narrado
Las tres situaciones de una posición
función buscar(t, k): i ← hash(k) mod t.capacidad mientras t.estado[i] ≠ vacía: si t.estado[i] = ocupada y t.clave[i] = k: devolver t.valor[i] i ← (i + 1) mod t.capacidad devolver nada- vacía: nunca hubo nada; corta la búsqueda.
- ocupada: hay una clave; si es k, se devuelve, si no, se sigue.
- borrada: hubo una clave; se sigue.
El factor de carga importa más que en el encadenamiento: con la tabla casi llena, los sondeos se alargan mucho, porque las claves forman grupos contiguos que crecen y se juntan. Por eso el límite de carga suele estar entre 0,5 y 0,875, y las lápidas cuentan como carga.
Su fila en la tabla de costos
La tabla con direccionamiento abierto y sondeo lineal, en las columnas de conjunto y diccionario de la ruta. La condición cambia: ahora la carga tiene que mantenerse por debajo del límite, y las lápidas cuentan.
| Representación | buscar(k) |
insertar(k) |
borrar(k) |
|---|---|---|---|
| tabla hash con sondeo lineal | O(1) esperado con la carga acotada; O(n) en el peor caso | O(1) esperado y amortizado | O(1) esperado, con lápida |
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.