Una tabla hash es una estructura de datos que asocia claves únicas con valores, permitiendo una búsqueda, inserción y eliminación eficiente. Su eficiencia proviene del uso de una función hash, que convierte una clave en un índice en una tabla interna. Gracias a esta función, las operaciones básicas tienen una complejidad promedio de O(1), lo que la convierte en una herramienta fundamental en programación.

Estructura de una Tabla Hash

La tabla hash utiliza una función hash para mapear claves a índices de una tabla interna. Su estructura básica incluye:

Claves y Valores: Cada entrada en la tabla tiene una clave única y un valor asociado.
Función Hash: Una función matemática que transforma la clave en un índice dentro de un rango fijo (el tamaño de la tabla).
Resolución de Colisiones: Si dos claves generan el mismo índice (colisión), se necesita una estrategia para almacenar ambas. Las técnicas comunes son:

Encadenamiento: Cada índice apunta a una lista enlazada de entradas.
Dirección Abierta: Busca un índice alternativo en la tabla.

Tipos de Tablas Hash

Hashing Cerrado (Encadenamiento): Las colisiones se manejan mediante listas enlazadas. Es flexible, pero puede consumir más memoria.
Hashing Abierto (Dirección Abierta):

Linear Probing: Busca el siguiente índice disponible de forma lineal.
Quadratic Probing: Usa una función cuadrática para encontrar índices alternativos.
Hash Doble: Aplica una segunda función hash para resolver colisiones.

Tablas Hash Perfectas: No tienen colisiones, pero requieren una función hash diseñada específicamente para el conjunto de claves.

Ejemplos de Tablas Hash en Diferentes Lenguajes

JavaScript
En JavaScript, los objetos y mapas son implementaciones nativas de tablas hash.

const tablaHash = new Map();
tablaHash.set("clave1", "valor1");
tablaHash.set("clave2", "valor2");

console.log(tablaHash.get("clave1")); // Muestra "valor1"
console.log(tablaHash.has("clave2")); // Muestra true

tablaHash.delete("clave2");

console.log(tablaHash.has("clave2")); // Muestra false

PHP
Los arrays asociativos funcionan como tablas hash.

$tablaHash = [
    "clave1" => "valor1",
    "clave2" => "valor2"
];

echo $tablaHash["clave1"]; // Muestra "valor1"

unset($tablaHash["clave2"]);

var_dump(array_key_exists("clave2", $tablaHash)); // Muestra false

C#
Dictionary<TKey, TValue> implementa una tabla hash eficiente.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        Dictionary<string, string> tablaHash = new Dictionary<string, string>();
        tablaHash["clave1"] = "valor1";
        tablaHash["clave2"] = "valor2";

        Console.WriteLine(tablaHash["clave1"]); // Muestra "valor1"

        tablaHash.Remove("clave2");

        Console.WriteLine(tablaHash.ContainsKey("clave2")); // Muestra false
    }
}

Java
La clase HashMap implementa una tabla hash.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, String> tablaHash = new HashMap<>();
        tablaHash.put("clave1", "valor1");
        tablaHash.put("clave2", "valor2");

        System.out.println(tablaHash.get("clave1")); // Muestra "valor1"
        tablaHash.remove("clave2");
        System.out.println(tablaHash.containsKey("clave2")); // Muestra false
    }
}

C
Las tablas hash se implementan usando arrays y listas enlazadas.

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>

// Definimos el tamaño de la tabla hash
#define TAMANO_TABLA 10

// Estructura del nodo de la lista enlazada
typedef struct Nodo {
    char* clave;            // Almacena la clave
    char* valor;            // Almacena el valor asociado a la clave
    struct Nodo* siguiente; // Apunta al siguiente nodo (para manejar colisiones)
} Nodo;

// Declaramos una tabla hash como un array de punteros a nodos
Nodo* tabla[TAMANO_TABLA];

// Función hash: convierte una clave en un índice de la tabla hash
unsigned int funcionHash(const char* clave) {
    unsigned int hash = 0;
    // Calcula el hash sumando desplazamientos de bits y valores ASCII de cada carácter
    while (*clave) {
        hash = (hash << 5) + *clave++;
    }
    // Devuelve el índice correspondiente al tamaño de la tabla
    return hash % TAMANO_TABLA;
}

// Función para insertar un par clave-valor en la tabla hash
void insertar(const char* clave, const char* valor) {
    unsigned int indice = funcionHash(clave); // Calcula el índice para la clave

    // Crea un nuevo nodo para almacenar el par clave-valor
    Nodo* nuevoNodo = (Nodo*)malloc(sizeof(Nodo));
    nuevoNodo->clave = strdup(clave);         // Copia la clave
    nuevoNodo->valor = strdup(valor);         // Copia el valor
    nuevoNodo->siguiente = tabla[indice];     // Apunta al nodo actual en el índice (manejo de colisiones)
    tabla[indice] = nuevoNodo;                // Actualiza la tabla hash con el nuevo nodo
}

// Función para buscar un valor dado su clave
char* buscar(const char* clave) {
    unsigned int indice = funcionHash(clave); // Calcula el índice para la clave
    Nodo* actual = tabla[indice];             // Obtiene el nodo en el índice

    // Recorre la lista enlazada en busca de la clave
    while (actual) {
        if (strcmp(actual->clave, clave) == 0) { // Si encuentra la clave
            return actual->valor;               // Devuelve el valor asociado
        }
        actual = actual->siguiente;             // Avanza al siguiente nodo
    }
    return NULL; // Devuelve NULL si no encuentra la clave
}

// Función principal
int main() {
    // Inserta pares clave-valor en la tabla hash
    insertar("clave1", "valor1");
    insertar("clave2", "valor2");

    // Busca e imprime el valor asociado a "clave1"
    printf("%s\n", buscar("clave1")); // Muestra "valor1"
    return 0; // Finaliza el programa
}

C++
En C++ std::unordered_map es una implementación eficiente de tablas hash.

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, string> tablaHash;
    tablaHash["clave1"] = "valor1";
    tablaHash["clave2"] = "valor2";

    cout << tablaHash["clave1"] << endl; // Muestra "valor1"
    tablaHash.erase("clave2");

    cout << (tablaHash.find("clave2") != tablaHash.end()) << endl; // Muestra 0 (false)
    return 0;
}

Las tablas hash son una herramienta poderosa en la programación moderna. Su capacidad para realizar operaciones en tiempo constante las hace ideales para casos en los que el rendimiento es crítico. Entender cómo funcionan, sus variantes y cómo implementarlas en diferentes lenguajes te ayudará a diseñar soluciones eficientes y escalables para manejar datos.