> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# Tablas hash: función hash, colisiones, sondeo y factor de carga

> Tablas hash en Java paso a paso: función hash, colisiones, tabla cerrada con sondeo lineal y cuadrático, tabla abierta con listas, borrado con marcas, factor de carga y redimensionado.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/tablas-hash">
  Inserta, busca y borra en una tabla hash cerrada o abierta y mira cada sondeo.
</Card>

Buscar un elemento en una lista obliga a recorrerla. En un árbol equilibrado, unos $\log_2 n$ pasos. Una **tabla hash** lo hace, de media, en **tiempo constante**: calcula directamente en qué casilla debería estar. Es lo que hay detrás de `HashMap` y `HashSet` en Java, de los diccionarios de Python y de los índices de las bases de datos.

## Lo que vas a aprender

* Qué es una función hash y por qué hay colisiones.
* La tabla cerrada con sondeo lineal y cuadrático.
* La tabla abierta con listas (encadenamiento).
* Por qué no se puede vaciar una casilla al borrar en una tabla cerrada.
* El factor de carga y el redimensionado.

## Cómo se usa el simulador

* Elige **Cerrada (sondeo)** o **Abierta (listas)** y, en la cerrada, sondeo **lineal** o **cuadrático**.
* Inserta, busca y borra valores. El simulador marca cada casilla que se **sondea**, cuáles están **ocupadas** y cuáles **borradas**, y resalta la línea del **código Java**.
* Prueba a **borrar un elemento y buscar otro que chocó con él**.

## Fundamentos teóricos

### Función hash

Convierte cada elemento en una posición de la tabla de tamaño $B$:

$$
h(e) = e.\text{hashCode()} \bmod B
$$

Con enteros, en el simulador, $h(e) = e \bmod B$. Una buena función hash reparte los elementos de forma uniforme.

### Colisiones

Dos elementos distintos pueden caer en la misma posición: es una **colisión**. Son inevitables, y hay dos formas de resolverlas.

### Tabla cerrada (direccionamiento abierto)

Todo se guarda en el propio array. Si la casilla está ocupada, se **sondea** otra:

* **Lineal**: $h, h + 1, h + 2, \dots$ (módulo $B$). Sencillo, pero forma **agrupamientos**.
* **Cuadrático**: $h, h + 1, h + 4, h + 9, \dots$. Reduce los agrupamientos.

Cada casilla tiene un estado: **VACÍA**, **OCUPADA** o **BORRADA**.

### Borrar en una tabla cerrada

Una búsqueda se detiene 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.

### Tabla abierta (encadenamiento)

Cada posición guarda una **lista** con todos los elementos que caen en ella. Borrar es quitar de la lista. Admite más elementos que casillas.

### Factor de carga y redimensionado

$$
\alpha = \frac{n}{B}
$$

Cuanto más llena, más colisiones y más lento. Cuando $\alpha$ supera un límite (por ejemplo 0,5 en la cerrada o 0,75 en `HashMap`), se crea una tabla mayor, normalmente de tamaño **primo** mayor que el doble, y se **reinsertan** todos los elementos.

### ¿Por qué primo?

Con un tamaño primo, los múltiplos de un mismo número se reparten por toda la tabla y el sondeo cuadrático recorre más casillas distintas.

## Ejemplos resueltos

<AccordionGroup>
  <Accordion title="Ejemplo 1 · Colisiones y borrado" defaultOpen>
    $B = 11$, sondeo lineal. Se insertan 14, 25 y 36: los tres tienen $h = 3$.

    14 → casilla 3. 25 → 3 ocupada, va a la 4. 36 → 3 y 4 ocupadas, va a la 5.

    Se borra 25: la casilla 4 queda **BORRADA**. Al buscar 36: 3 (14), 4 (borrada, se sigue), 5 (encontrado).
  </Accordion>

  <Accordion title="Ejemplo 2 · Tabla abierta">
    Con los mismos datos y encadenamiento, la posición 3 guarda la lista 14 → 25 → 36. Borrar 25 es quitarlo de la lista.
  </Accordion>

  <Accordion title="Ejemplo 3 · Sondeo cuadrático">
    Si $h = 3$ y está ocupada, se prueban 4, 7, 12 mod 11 = 1, 19 mod 11 = 8…
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="Agrupamiento">
    Con sondeo lineal, inserta varios números con el mismo resto. Repite con sondeo cuadrático.
  </Step>

  <Step title="La marca de borrado">
    Reproduce el ejemplo 1 y busca 36 tras borrar 25.
  </Step>

  <Step title="Redimensionar">
    Inserta elementos hasta superar el factor de carga máximo. ¿Qué tamaño tiene la nueva tabla?
  </Step>
</Steps>

## Errores frecuentes

* **Vaciar la casilla** al borrar en una tabla cerrada.
* **Olvidar el módulo** al sondear y salirse del array.
* **Implementar `equals` sin `hashCode`** en Java: dos objetos iguales deben tener el mismo hash.

## Herramientas relacionadas

<CardGroup cols={3}>
  <Card title="ArrayList y lista enlazada" icon="list" href="/programacion/java/listas">
    Listas en Java.
  </Card>

  <Card title="Estructuras de datos" icon="layer-group" href="/programacion/algoritmos/estructuras-datos">
    Árbol binario de búsqueda.
  </Card>

  <Card title="Factores primos" icon="calculator" href="/matematicas/numeros/factorizacion">
    Números primos.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.