Tabla Hash
Última actualización
Una tabla hash almacena elementos en un arreglo de cubetas. Para colocar o encontrar una clave, la pasa por una función hash y toma el resultado módulo el número de cubetas: eso da el índice de la cubeta en O(1). Pulsa reproducir arriba para ver cómo cada clave se convierte en hash hacia una cubeta y se almacena, y luego una búsqueda que salta directamente a la cubeta correcta.
Cuando dos claves caen en la misma cubeta -una colisión- esta visualización usa encadenamiento separado: cada cubeta contiene una pequeña lista y las claves que colisionan se añaden a ella. Mientras la tabla no esté demasiado llena (un factor de carga bajo) y el hash distribuya bien las claves, las cadenas permanecen cortas y la inserción, la búsqueda y el borrado son O(1) en promedio.
Complejidad temporal
| Operación | Promedio | Peor caso |
|---|---|---|
| Insertar | O(1) | O(n) (todas las claves colisionan) |
| Búsqueda | O(1) | O(n) |
| Borrar | O(1) | O(n) |
| Espacio | O(n) | O(n) |
Conceptos clave
| Término | Significado |
|---|---|
| Función hash | Asigna una clave a un índice de cubeta |
| Colisión | Dos claves caen en la misma cubeta |
| Encadenamiento separado | Cada cubeta contiene una lista de entradas que colisionan |
| Direccionamiento abierto | Alternativa: sondear la siguiente ranura libre |
| Factor de carga | entradas / cubetas: determina el redimensionamiento |
Ejemplo resuelto
Insertando las claves 20, 34, 9, 13 en una tabla con 7 cubetas, usando hash(k) = k % 7:
| Paso | Estructura | Acción |
|---|---|---|
Insertar 20 | cubeta 6: [20] | 20 % 7 = 6, cubeta 6 vacía, almacenar 20 |
Insertar 34 | cubeta 6: [20, 34] | 34 % 7 = 6, colisión con 20, añadir 34 a la cadena |
Insertar 9 | cubeta 2: [9] | 9 % 7 = 2, cubeta 2 vacía, almacenar 9 |
Insertar 13 | cubeta 6: [20, 34, 13] | 13 % 7 = 6, colisión, añadir 13 a la cadena de la cubeta 6 |
Buscar 34 | cubeta 6: [20, 34, 13] | 34 % 7 = 6, recorrer cadena: 20 no, 34 coincide - encontrado |
Cuándo usar una tabla hash
| Úsala cuando | Evítala cuando |
|---|---|
Necesitas inserción, búsqueda y borrado por clave en O(1) promedio | Necesitas mantener las claves ordenadas - usa un BST balanceado |
| Las claves no tienen un orden útil y solo compruebas pertenencia por coincidencia exacta | Necesitas consultas por rango o búsquedas de la clave más cercana |
| Puedes permitirte algo de memoria extra para cubetas y un factor de carga bajo | La memoria es extremadamente limitada y cada byte cuenta |
| Existe una buena función hash para tu tipo de clave | La latencia del peor caso debe estar acotada - las colisiones la hacen O(n) |
Código de Hash Table
Una implementación limpia y ejecutable de Hash Table en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Hash Table en Python
Python
1class HashTable:2 def __init__(self, size=8):3 self.size = size4 self.buckets = [[] for _ in range(size)]5
6 def _index(self, key):7 # Hash the key to a bucket; different keys can collide8 return sum(ord(ch) for ch in key) % self.size9
10 def set(self, key, value):11 bucket = self.buckets[self._index(key)]12 for i, (k, _) in enumerate(bucket):13 if k == key:14 bucket[i] = (key, value) # update existing key15 return16 bucket.append((key, value)) # chain on collision17
18 def get(self, key):19 for k, v in self.buckets[self._index(key)]:20 if k == key:21 return v22 raise KeyError(key)23
24 def delete(self, key):25 bucket = self.buckets[self._index(key)]26 for i, (k, _) in enumerate(bucket):27 if k == key:28 del bucket[i]29 return30 raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])Código de Hash Table en JavaScript
JavaScript
1class HashTable {2 constructor(size = 8) {3 this.size = size;4 this.buckets = Array.from({ length: size }, () => []);5 }6
7 // Fold character codes into a bucket index8 hash(key) {9 let h = 0;10 for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11 return h;12 }13
14 set(key, value) {15 const bucket = this.buckets[this.hash(key)];16 const pair = bucket.find(([k]) => k === key);17 if (pair) pair[1] = value;18 else bucket.push([key, value]); // Separate chaining on collision19 }20
21 get(key) {22 const bucket = this.buckets[this.hash(key)];23 const pair = bucket.find(([k]) => k === key);24 return pair ? pair[1] : undefined;25 }26
27 delete(key) {28 const bucket = this.buckets[this.hash(key)];29 const index = bucket.findIndex(([k]) => k === key);30 if (index === -1) return false;31 bucket.splice(index, 1);32 return true;33 }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));Código de Hash Table en Java
Java
1public class Main {2 static class Entry {3 String key; int value;4 Entry next; // chain for keys sharing a bucket5 Entry(String key, int value) { this.key = key; this.value = value; }6 }7
8 static final int CAPACITY = 8;9 static Entry[] buckets = new Entry[CAPACITY];10
11 static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13 static void put(String key, int value) {14 int i = index(key);15 for (Entry e = buckets[i]; e != null; e = e.next) {16 if (e.key.equals(key)) { e.value = value; return; }17 }18 Entry entry = new Entry(key, value);19 entry.next = buckets[i]; // prepend to the chain20 buckets[i] = entry;21 }22
23 static Integer get(String key) {24 for (Entry e = buckets[index(key)]; e != null; e = e.next) {25 if (e.key.equals(key)) return e.value;26 }27 return null;28 }29
30 static void remove(String key) {31 int i = index(key);32 Entry prev = null;33 for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34 if (e.key.equals(key)) {35 if (prev == null) buckets[i] = e.next;36 else prev.next = e.next;37 return;38 }39 }40 }41
42 public static void main(String[] args) {43 put("apple", 3); put("banana", 7); put("cherry", 5);44 System.out.println("apple -> " + get("apple"));45 put("apple", 10); // update in place46 System.out.println("apple -> " + get("apple"));47 remove("banana");48 System.out.println("banana -> " + get("banana"));49 }50}Código de Hash Table en C++
C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6 static constexpr int CAPACITY = 8;7 // Separate chaining: each bucket holds (key, value) pairs8 std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10 size_t hash(const std::string& key) const {11 size_t h = 0;12 for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13 return h % CAPACITY;14 }15
16 void set(const std::string& key, int value) {17 auto& bucket = buckets[hash(key)];18 for (auto& entry : bucket) {19 if (entry.first == key) {20 entry.second = value; // update existing key21 return;22 }23 }24 bucket.push_back({key, value});25 }26
27 const int* get(const std::string& key) const {28 for (const auto& entry : buckets[hash(key)]) {29 if (entry.first == key) return &entry.second;30 }31 return nullptr;32 }33
34 void erase(const std::string& key) {35 auto& bucket = buckets[hash(key)];36 for (size_t i = 0; i < bucket.size(); ++i) {37 if (bucket[i].first == key) {38 bucket.erase(bucket.begin() + i);39 return;40 }41 }42 }43};44
45int main() {46 HashTable table;47 table.set("apple", 3);48 table.set("banana", 7);49 table.set("apple", 4); // overwrites the old value50 for (const std::string& key : {"apple", "banana", "grape"}) {51 const int* value = table.get(key);52 if (value != nullptr) std::cout << key << " = " << *value << "\n";53 else std::cout << key << " not found\n";54 }55 table.erase("banana");56 std::cout << "banana after erase: "57 << (table.get("banana") ? "found" : "not found") << "\n";58 return 0;59}Código de Hash Table en C
C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9 char key[16];10 int value;11 struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17 unsigned int h = 5381; // djb2, then modulo the bucket count18 for (; *key; key++) h = h * 33 + (unsigned char)*key;19 return h % CAPACITY;20}21
22void set(const char* key, int value) {23 unsigned int i = hash(key);24 for (Entry* e = buckets[i]; e != NULL; e = e->next) {25 if (strcmp(e->key, key) == 0) {26 e->value = value; // update existing key27 return;28 }29 }30 Entry* e = malloc(sizeof(Entry));31 strcpy(e->key, key);32 e->value = value;33 e->next = buckets[i];34 buckets[i] = e;35}36
37int* get(const char* key) {38 for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39 if (strcmp(e->key, key) == 0) return &e->value;40 }41 return NULL;42}43
44void removeKey(const char* key) {45 Entry** link = &buckets[hash(key)];46 while (*link != NULL) {47 if (strcmp((*link)->key, key) == 0) {48 Entry* old = *link;49 *link = old->next;50 free(old);51 return;52 }53 link = &(*link)->next;54 }55}56
57void printBuckets(void) {58 for (int i = 0; i < CAPACITY; i++) {59 printf("bucket %d:", i);60 for (Entry* e = buckets[i]; e != NULL; e = e->next) {61 printf(" (%s=%d)", e->key, e->value);62 }63 printf("\n");64 }65}66
67int main(void) {68 set("apple", 3);69 set("banana", 7);70 set("apple", 4); // overwrites the old value71 set("grape", 9);72 printBuckets();73 int* value = get("apple");74 printf("get(apple): %d\n", value ? *value : -1);75 removeKey("banana");76 printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77 return 0;78}Preguntas frecuentes sobre la tabla hash
¿Qué es una colisión de hash y cómo se resuelve?
Una colisión ocurre cuando dos claves diferentes caen en la misma cubeta. Las dos soluciones comunes son el encadenamiento separado (cada cubeta contiene una lista y las claves que colisionan se añaden - mostrado aquí) y el direccionamiento abierto (sondear la siguiente ranura vacía del arreglo). Ambos mantienen correctas las búsquedas; se diferencian en la disposición de memoria y el rendimiento con carga alta.
¿Cuál es la complejidad temporal de una tabla hash?
La inserción, la búsqueda y el borrado son
O(1) en promedio cuando la función hash distribuye las claves de forma uniforme y el factor de carga se mantiene bajo. En el peor caso -todas las claves colisionando en una sola cubeta- se degradan a O(n), por lo que importan una buena función hash y el redimensionamiento.¿Qué es un factor de carga?
El factor de carga es el número de entradas almacenadas dividido por el número de cubetas. A medida que crece, las cadenas se alargan y las operaciones se ralentizan, por lo que la mayoría de las tablas hash se redimensionan (rehash a un arreglo mayor) cuando supera un umbral como 0.75.
¿Cuándo debo usar una tabla hash en lugar de un árbol binario de búsqueda?
Usa una tabla hash cuando solo necesitas búsquedas por coincidencia exacta y quieres velocidad
O(1) promedio sin requisito de orden. Usa un árbol binario de búsqueda balanceado cuando necesitas claves ordenadas, consultas por rango o búsquedas de predecesor/sucesor, algo que una tabla hash no puede hacer eficientemente. Un BST ofrece operaciones O(log n) garantizadas, mientras que una tabla hash cambia esa garantía por un rendimiento promedio más rápido.¿Cuál es la diferencia entre encadenamiento separado y direccionamiento abierto?
El encadenamiento separado almacena las claves que colisionan en una lista por cubeta, de modo que una cubeta puede contener muchas entradas y la tabla nunca se llena realmente. El direccionamiento abierto mantiene todo en el propio arreglo y sondea la siguiente ranura libre ante una colisión, lo cual es amigable con la caché pero se degrada bruscamente cuando el factor de carga se acerca a 1 y necesita un manejo cuidadoso del borrado. El encadenamiento tolera factores de carga más altos; el direccionamiento abierto usa la memoria de forma más compacta.
¿Por qué no puedo confiar en que una tabla hash mantenga mis claves en orden de inserción o de clasificación?
Una función hash dispersa deliberadamente las claves entre las cubetas para evitar aglomeraciones, por lo que el orden de iteración refleja la disposición de las cubetas, no el orden de inserción o de clasificación. Si necesitas orden, usa un mapa/árbol ordenado o una estructura como un mapa con orden de inserción (por ejemplo, el
dict de Python preserva el orden de inserción, pero eso es una garantía del lenguaje, no una propiedad inherente de la tabla hash). Nunca asumas que el orden de iteración coincide con cómo insertaste las claves a menos que el lenguaje lo prometa explícitamente.Recursos relacionados
Más visualizaciones
