Tabla hash

Guarda pares clave-valor y aprende cómo se resuelven las colisiones. Con direccionamiento abierto, la clave sondea casillas hasta hallar un hueco; con encadenamiento, cada casilla es una lista. Elige método y función hash, observa el sondeo paso a paso, elimina (con lápida) y redimensiona cuando la tabla se llena.

Velocidad
Escribe una clave y un valor, e inserta. Cada paso muestra la casilla y el sondeo.
Resultado—

Casillas

índice 0 … 6 · 7 casillas
  • 0
    vacío
  • 1
    eva30
  • 2
    vacío
  • 3
    ana10
  • 4
    luis20
  • 5
    sol40
  • 6
    vacío

Entradas (4)

  • eva30
  • ana10
  • luis20
  • sol40

Métricas

Casillas
7
Entradas
4
Factor de carga
0.571
Ocupadas
4
Lápidas
0
Colisiones
0
Sondeos medidos
0.00
Sondeos teóricos
1.67
Racimos
2
Racimo mayor
3

Los sondeos medidos (0.00) frente a los que predice la fórmula (1.67).

Método

Sondeo lineal: si la casilla está ocupada, prueba la siguiente. Sencillo, pero forma racimos que alargan las búsquedas.

Leyenda

  • Libre
  • Ocupada
  • Casilla en curso
  • Colisión / encontrada
  • Lápida ⋈ (borrado)

Colisiones, lápidas y crecimiento

Colisión: dos claves quieren la misma casilla. Se resuelve sondeando otra (abierto) o añadiendo a la lista (encadenamiento).

Factor de carga α = n/m: cuánto de llena está. Al acercarse a 1, el sondeo se dispara, por eso se redimensiona antes (aquí, al pasar de 0.75).

Lápida: al borrar en abierto no se deja la casilla vacía —eso cortaría las cadenas de sondeo— sino una marca; se puede reutilizar al insertar y desaparece al redimensionar.

Redimensionar: el índice depende del tamaño, así que al crecer hay que recolocar todas las entradas. El nuevo tamaño es primo, para repartir mejor.