Tablas hash
Inserta, busca y borra y mira cada sondeo en la tabla y en el código. Prueba a borrar un elemento y buscar otro que chocó con él.
Sondeo: 3 → 4 → 5 → 6
1// Tabla hash cerrada: E[] tabla, Estado[] estado2// con los estados VACIA, OCUPADA y BORRADA3private int buscarPos(E e) {4 int pos = hash(e); // e.hashCode() % B5 int i = 0, borrada = -1;6 while (i < B && estado[pos] != VACIA) {7 if (estado[pos] == OCUPADA && tabla[pos].equals(e))8 return pos; // encontrado9 if (estado[pos] == BORRADA && borrada == -1)10 borrada = pos; // primer hueco reutilizable11 i++;12 pos = (hash(e) + i) % B; // colisión: siguiente13 }14 return borrada != -1 ? borrada : pos;15}16 17public boolean add(E e) {18 int pos = buscarPos(e);19 if (estado[pos] == OCUPADA)20 return false; // ya estaba21 tabla[pos] = e;22 estado[pos] = OCUPADA;23 n++;24 if ((double) n / B > fcMax)25 redimensionar(); // B primo >= 2B26 return true;27}28 29public boolean contains(Object o) {30 int pos = buscarPos((E) o);31 return estado[pos] == OCUPADA;32}33 34public boolean remove(Object o) {35 int pos = buscarPos((E) o);36 if (estado[pos] != OCUPADA)37 return false;38 estado[pos] = BORRADA; // no VACIA: cortaría39 n--; // otras búsquedas40 return true;41}true: 36 está en la casilla 6.
Una tabla hash guarda elementos en un array de B posiciones y decide la posición de cada uno con una función hash, aquí hash(e) = e % B. Así añadir, buscar y borrar cuestan O(1) de media, sin recorrer todo.
Cuando dos elementos caen en la misma posición hay una colisión. En la tabla cerrada (direccionamiento abierto) se busca otra casilla con un sondeo: lineal (h + 1, h + 2…) o cuadrático (h + 1, h + 4, h + 9…). En la tabla abierta (encadenamiento) cada posición guarda una lista con todos los que caen ahí.
El factor de carga n/B mide lo llena que está la tabla. Cuando supera el límite, se crea una tabla de tamaño primo mayor que el doble y se reinsertan todos los elementos. Prueba las operaciones y mira cada sondeo en la tabla y en el código Java.
En una tabla cerrada con B = 11 y sondeo lineal se insertan 14, 25 y 36, se borra 25 y se busca 36. ¿Qué pasa?
- hash(14) = 3: va a la casilla 3.
- hash(25) = 3: colisión. Pruebo la 4, que está libre.
- hash(36) = 3: la 3 y la 4 están ocupadas, así que va a la 5.
- Al borrar 25, la casilla 4 queda BORRADA, no VACIA.
- Buscando 36: la 3 tiene 14, la 4 está borrada (se sigue buscando) y en la 5 está 36.
36 se encuentra en la casilla 5 gracias a la marca de borrado
Preguntas frecuentes
¿Por qué no se deja la casilla vacía al borrar en una tabla cerrada?
Porque las búsquedas paran al llegar a una casilla vacía. Si al borrar se vaciara la casilla, los elementos que chocaron allí y se guardaron más adelante ya no se encontrarían. Por eso se marca como BORRADA: las búsquedas la saltan y las inserciones pueden reutilizarla.
¿Por qué el tamaño de la tabla suele ser un número primo?
Porque reparte mejor los elementos cuando las claves siguen algún patrón, como ser todas múltiplos de un número. Además, con sondeo cuadrático y B primo se garantiza encontrar hueco si la tabla está como mucho medio llena.
¿Qué diferencia hay entre tabla hash abierta y cerrada?
En la cerrada todos los elementos están dentro del array y las colisiones se resuelven buscando otra casilla. En la abierta cada casilla es una lista y los que colisionan se añaden a ella. La abierta admite un factor de carga mayor que 1; la cerrada no.
¿Qué es el agrupamiento primario?
Con sondeo lineal, los elementos que colisionan forman bloques seguidos que crecen y hacen cada vez más largos los sondeos. El sondeo cuadrático salta más lejos y reduce ese efecto.