Quartz 4

Hash Tables

3 min read

Hash Tables

Relacionado: Ver Dictionaries para abstracción. HashCat usa hash tables para cracking. Tabla de símbolos en compiladores. Big-Oh-Notation para complejidad.

¿Qué es una Hash Table?

Una tabla hash es una estructura que permite almacenar pares clave → valor, y acceder a ellos rápidamente (en tiempo promedio O(1)), usando una función hash que transforma la clave en un índice.

Estructura de una Hash Table

  1. Una función hash h(k) que transforma la clave k en un índice numérico.

  2. Una tabla (array) que almacena los datos en la posición h(k).

Ejemplo básico:

Clave     → Hash     → Índice en array
"ana"     → h("ana") → 3
"luis"    → h("luis") → 7

Operaciones básicas

OperaciónDescripciónComplejidad (promedio)
insert(k, v)Inserta o actualiza el valor v asociado a kO(1)
lookup(k)Devuelve el valor asociado a la clave kO(1)
delete(k)Elimina la entrada con clave kO(1)

️ En el peor caso (muchas colisiones mal gestionadas), puede llegar a O(n)

¿Qué es una función hash?

Es una función h(k) que convierte una clave (entero, string, objeto…) en un número entero, dentro del rango del tamaño del array.

Ejemplo simple:

function h(k):
  return k mod 10

Para strings:

function h(s):
  hash := 0
  for cada c en s:
    hash := hash * 31 + ASCII(c)
  return hash mod B

️ Colisiones y cómo resolverlas

¿Qué pasa si dos claves caen en la misma posición? → Colisión

Métodos para resolver colisiones:

1. Open Hashing (Encadenamiento)

Cada celda del array tiene una lista enlazada de elementos con el mismo hash.

tabla[3] → [ ("ana", 5), ("mario", 8) ]

  • Fácil de implementar.

  • No hay límite superior en la cantidad de elementos.

2. Closed Hashing (Hashing abierto o direccionamiento abierto)

Todos los datos se almacenan dentro del array. Si una celda está ocupada, se busca otra:

Estrategias:

  • Linear probing:

    h(k) = (hash(k) + i) mod B

  • Quadratic probing

  • Double hashing (usa segunda función hash)

Más eficiente en memoria, pero más difícil de implementar.

Diseño de tamaño y carga

️ Load factor (factor de carga)

α = n / B  // número de elementos dividido entre tamaño de la tabla

  • Ideal mantener α ≤ 0.7 para mantener rendimiento en O(1)

  • Si α crece demasiado → rehashing (doblar tamaño y reinsertar todos los elementos)

Complejidad temporal

OperaciónPromedioPeor caso (mala hash o carga)
InsertO(1)O(n)
LookupO(1)O(n)
DeleteO(1)O(n)

Con buena función hash y factor de carga bajo, el comportamiento es cercano a O(1).

Ejemplo en pseudocódigo (open hashing)

const B := 10
tabla := array[0..B-1] of lista
 
function insert(k, v):
  i := h(k)
  agregar (k, v) a tabla[i]
 
function lookup(k):
  i := h(k)
  buscar en tabla[i] el par con clave k

Ejemplo en Python (usando dict)

d = {}
d["ana"] = 42
d["luis"] = 55
print(d["ana"])  # → 42
del d["luis"]

Bajo el capó, dict usa hash tables con open addressing y hashing perfecto adaptativo.

Usos reales de Hash Tables

  • Dictionaries / Maps en lenguajes modernos (dict, Map, HashMap, Hashtable)

  • Bases de datos: índices hash (no ordenados)

  • Compiladores: tablas de símbolos

  • Caches: acceso rápido a datos temporales

  • Firewalls y redes: lookup de IPs o sesiones

  • Contadores: conteo de ocurrencias (Counter en Python)

Conclusión

Las hash tables son la estructura por excelencia cuando necesitas acceso ultra-rápido por clave, sin importar el orden.
El secreto está en una buena función hash, el manejo correcto de colisiones y mantener bajo el load factor.

¿Quieres que te prepare una implementación completa de una hash table desde cero (con encadenamiento o probing) en C, Java o Python? ¿O te interesa ver cómo se usa en un caso real, como una tabla de símbolos o un sistema de caché?

Graph View

Backlinks