Hash Table

Una tabla hash mapea claves a un array de cubos mediante una función hash, ofreciendo búsqueda/inserción/borrado promedio O(1); es una de las estructuras de datos más usadas.

Propósito

Proporcionar acceso clave-valor en tiempo constante promedio, implementando eficientemente diccionarios y conjuntos.

Mecanismo

hash(clave) % capacidad localiza el cubo. Manejo de colisiones: encadenamiento separado (el cubo contiene una lista) o direccionamiento abierto (sondeo del siguiente hueco libre). Factor de carga = elementos / cubos; superar el umbral dispara redimensionado y rehash. Una buena función hash distribuye las claves uniformemente.

Casos de uso

Implementaciones de diccionarios y mapas
Índices de bases de datos
Cachés (LRU)
Desduplicación y conjuntos

Ejemplos

entrada

{"name":"Ada"} → hash("name")=5

Output

Value stored in bucket 5

O(1) on average

Errores comunes

A poorly distributed hash function causes collision pile-ups: Use a high-quality hash function and a suitable load factor

Términos relacionados

Un filtro de Bloom aproxima la pertenencia a un conjunto con k funciones hash y un array de bits, ofreciendo eficiencia espacial a cambio de una tasa de falsos positivos.

La notación O grande describe el límite superior asintótico de una función, usada para analizar la complejidad temporal/espacial de los algoritmos ignorando constantes y términos de orden inferior.

Herramientas relacionadas

Djb2 — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor.

Sdbm — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor.

Zobrist — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor.

Pearson — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor.

Elfhash — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor.

References