Recorrido narrado
Por qué en promedio se mira poco
Con n claves repartidas al azar en m cubetas, cada cubeta tiene en promedio n / m claves. Buscar mira solo una cubeta, así que hace en promedio unas n / m comparaciones.
Si la tabla mantiene m proporcional a n (lo verás en el siguiente tema), n / m es una constante, y buscar es O(1) esperado. «Esperado» porque es un promedio que supone que la función hash reparte bien las claves.
función buscar(t, k): c ← t.cubetas[hash(k) mod t.capacidad] para cada (clave, valor) en c: si clave = k: devolver valor devolver nadaEsta tabla responde por clave. No sabe nada del orden: las claves están repartidas por la función hash, no ordenadas.
Su fila en la tabla de costos
Esta es la fila de la tabla hash con encadenamiento, en las columnas de conjunto y diccionario de la ruta.
| Representación | buscar(k) |
insertar(k) |
borrar(k) |
mínimo |
sucesor(k) |
rango(a, b) |
|---|---|---|---|---|---|---|
| tabla hash | O(1) esperado; O(n) en el peor caso | O(1) esperado y amortizado | O(1) esperado | O(n) | O(n) | O(n) |
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.