Tablas hash: el arma secreta que hace que tu código sea 1000 veces más rápido

¿Qué es una tabla hash y por qué es necesaria?

Una tabla hash (hash table o hash map) es una estructura de datos que almacena pares de clave-valor y proporciona un acceso muy rápido a los datos. En promedio, las operaciones de búsqueda, inserción y eliminación se realizan en O(1) - tiempo constante. Esto significa que, independientemente de si se almacenan 10 o 10 millones de elementos en la tabla, el acceso a cualquiera de ellos tardará aproximadamente el mismo tiempo.

Un ejemplo sencillo de la vida:

const userAges = {
    "Alexey": 28,
    "Maria": 25,
    "Dmitry": 32
};

console.log(userAges["Maria"]); // 25 - ¡acceso instantáneo!

En la mayoría de los lenguajes de programación modernos, las tablas hash están integradas: dict en Python, Map en JavaScript, HashMap en Java, map en Go.

Cómo funciona una tabla hash

Bajo el capó, una tabla hash es una matriz normal. La magia sucede gracias a funciones hash, que convierte una clave (cadena, número u objeto) en un índice de matriz.

Proceso de trabajo:

1. Hash de la clave: La clave (por ejemplo, "Alexey") se pasa a través de una función hash que devuelve un número (por ejemplo, 42)

2. Cálculo del índice: El resultado del hash se convierte en un índice de matriz mediante la operación de resto de división: index = hash % array.length

3. Guardar valor: El valor se almacena en la celda de la matriz con este índice

"Alexey" → hash("Alexey") → 1892374 → 1892374 % 10 → índice 4 Matriz: [_, _, _, _, {key: "Alexey", value: 28}, _, _, _, _, _]

Funciones hash: el corazón del sistema

Una buena función hash debe tener varias propiedades:

• Determinación - la misma clave siempre da el mismo hash

• Uniformidad — los hashes deben distribuirse uniformemente en todo el rango de valores

• Velocidad - el cálculo del hash debe ser rápido

• Minimización de colisiones - diferentes claves deben dar diferentes hashes

Ejemplo de una función hash simple para cadenas:

function simpleHash(str, tableSize) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash + str.charCodeAt(i) * (i + 1)) % tableSize;
    }
    return hash;
}

console.log(simpleHash("Alexey", 100)); // por ejemplo, 67
console.log(simpleHash("Maria", 100));   // por ejemplo, 23

En sistemas reales, se utilizan funciones más complejas, como MurmurHash, CityHash o funciones criptográficas como SHA-256 (para casos especiales).

Colisiones: cuando dos claves quieren un lugar

Colisión ocurre cuando dos claves diferentes reciben el mismo índice después del hash. Este es un problema inevitable, porque el número de claves posibles suele ser mayor que el tamaño de la matriz.

"Alexey" → índice 4 "Dmitry" → índice 4 ← ¡Colisión!

Método de encadenamiento (Chaining)

La forma más popular de resolver colisiones. Cada celda de la matriz almacena no un valor, sino una lista (cadena) de todos los valores con el mismo índice.

class HashTable {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        const index = this._hash(key);
        
        if (!this.table[index]) {
            this.table[index] = [];
        }
        
        // Comprobamos si ya existe una clave de este tipo
        for (let item of this.table[index]) {
            if (item[0] === key) {
                item[1] = value; // Actualizando el valor
                return;
            }
        }
        
        // Añadimos un nuevo par clave-valor
        this.table[index].push([key, value]);
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return undefined;
        
        for (let item of bucket) {
            if (item[0] === key) {
                return item[1];
            }
        }
        
        return undefined;
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.table[index];
        
        if (!bucket) return false;
        
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1);
                return true;
            }
        }
        
        return false;
    }
}

// Uso
const users = new HashTable();
users.set("Alexey", { age: 28, city: "Moscow" });
users.set("Maria", { age: 25, city: "St. Petersburg" });
users.set("Dmitry", { age: 32, city: "Novosibirsk" });

console.log(users.get("Maria")); // { age: 25, city: "San Petersburgo" }users.remove("Alexey");
console.log(users.get("Alexey")); // undefined

Direccionamiento abierto (Open Addressing)

En lugar de crear cadenas, en caso de colisión buscamos otra celda libre en la matriz según un algoritmo específico:

Perforación lineal — comprobamos las siguientes celdas seguidas: index, index+1, index+2...

class HashTableOpenAddressing {
    constructor(size = 50) {
        this.table = new Array(size);
        this.size = size;
        this.count = 0;
    }

    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash = (hash + key.charCodeAt(i) * (i + 1)) % this.size;
        }
        return hash;
    }

    set(key, value) {
        if (this.count / this.size > 0.7) {
            this._resize(); // Aumentamos el tamaño al llenar >70 %
        }

        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined && this.table[index].key !== key) {
            i++;
            index = (this._hash(key) + i) % this.size; // Perforación lineal
        }

        if (this.table[index] === undefined) {
            this.count++;
        }

        this.table[index] = { key, value };
    }

    get(key) {
        let index = this._hash(key);
        let i = 0;

        while (this.table[index] !== undefined) {
            if (this.table[index].key === key) {
                return this.table[index].value;
            }
            i++;
            index = (this._hash(key) + i) % this.size;
        }

        return undefined;
    }

    _resize() {
        const oldTable = this.table;
        this.size *= 2;
        this.table = new Array(this.size);
        this.count = 0;

        for (let item of oldTable) {
            if (item !== undefined) {
                this.set(item.key, item.value);
            }
        }
    }
}

Perforación cuadrática — comprobamos: index, index+1², index+2², index+3²...

Hash doble — usamos la segunda función hash para calcular el paso.

Rendimiento y complejidad

Load Factor (coeficiente de llenado) = número de elementos / tamaño de la matriz

Con un factor de carga > 0,7, generalmente se realiza rehashing — crear una nueva matriz más grande y mover todos los elementos.

Casos de uso reales

1. Almacenamiento en caché de los resultados

class Cache {
    constructor() {
        this.cache = new Map();
    }

    async fetchUser(userId) {
        // Comprobando caché
        if (this.cache.has(userId)) {
            console.log('Received from cache');
            return this.cache.get(userId);
        }

        // Cargando datos
        const user = await api.getUser(userId);
        
        // Guardando en caché
        this.cache.set(userId, user);
        
        return user;
    }
}

2. Cálculo de la frecuencia de los elementos

function countWords(text) {
    const wordCount = new Map();
    const words = text.toLowerCase().split(/\s+/);

    for (let word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }

    return wordCount;
}

const text = "JavaScript is a programming language JavaScript is popular";
console.log(countWords(text));
// Map { 'javascript' => 2, 'es' => 1, 'lenguaje' => 1, ... }... }

3. Búsqueda de duplicados

function hasDuplicates(arr) {
    const seen = new Set();
    
    for (let item of arr) {
        if (seen.has(item)) {
            return true;
        }
        seen.add(item);
    }
    
    return false;
}

console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 2, 5])); // true

4. Indexación en bases de datos

Las bases de datos utilizan índices hash para buscar rápidamente registros por clave:

-- В PostgreSQL
CREATE INDEX users_email_hash ON users USING HASH (email);

-- Теперь поиск по email молниеносный
SELECT * FROM users WHERE email = 'alex@example.com';

5. Identificadores únicos de usuarios

class Session {
    constructor() {
        this.sessions = new Map();
    }

    createSession(userId) {
        const sessionId = this.generateSessionId();
        this.sessions.set(sessionId, {
            userId,
            createdAt: Date.now(),
            data: {}
        });
        return sessionId;
    }

    getSession(sessionId) {
        return this.sessions.get(sessionId);
    }

    destroySession(sessionId) {
        this.sessions.delete(sessionId);
    }

    generateSessionId() {
        return Math.random().toString(36).substring(2);
    }
}

6. Enrutamiento en marcos web

class Router {
    constructor() {
        this.routes = new Map();
    }

    addRoute(path, handler) {
        this.routes.set(path, handler);
    }

    handleRequest(path) {
        const handler = this.routes.get(path);
        
        if (handler) {
            return handler();
        }
        
        return 'Not Found';
    }
}

const router = new Router();
router.addRoute('/home', () => 'Home Page');
router.addRoute('/about', () => 'About Page');

console.log(router.handleRequest('/home')); // Home Page - O(1)!

7. Anagramas y agrupación de líneas

function groupAnagrams(words) {
    const groups = new Map();

    for (let word of words) {
        // Ordenamos las letras como una llave
        const key = word.split('').sort().join('');
        
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        
        groups.get(key).push(word);
    }

    return Array.from(groups.values());
}

console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Map vs Object en JavaScript: ¿qué elegir?

JavaScript ofrece dos formas de trabajar con tablas hash:

Object:

const obj = {};
obj.name = "Alexey";
obj['age'] = 28;

Map:

const map = new Map();
map.set('name', 'Alexey');
map.set('age', 28);

Cuándo usar Map:

• Claves no son cadenas (objetos, números, funciones)

• Se necesita iteración en orden de adición

• Adiciones/eliminaciones frecuentes de elementos

• Necesito saber el número exacto de elementos (map.size)

Cuándo usar Object:

• Las claves son siempre cadenas

• Necesito JSON.stringify/parse

• Estructura de configuración simple

Consejos prácticos

1. Elige el tamaño inicial correcto

// Si sabes que habrá ~1000 elementos
const map = new Map(); // Tamaño pequeño por defecto
// vs
const users = new HashTable(2000); // Evitar el rehashing

2. Ten cuidado con los objetos como las llaves

const map = new Map();
const key1 = { id: 1 };
const key2 = { id: 1 };

map.set(key1, 'value1');
console.log(map.get(key2)); // ¡indefinido! Diferentes objetos

3. Limpia los datos no utilizados

// Utiliza WeakMap para la limpieza automática
const cache = new WeakMap();
let user = { name: 'Alexey' };

cache.set(user, 'some data');
user = null; // Los datos se eliminarán automáticamente de WeakMap

Conclusión

Las tablas hash son una estructura de datos fundamental que se utiliza en todas partes: desde bases de datos hasta marcos web, desde compiladores hasta motores de búsqueda. Comprender su diseño, la resolución de conflictos y el rendimiento te convierte en un desarrollador más eficiente.

En Codice no solo analizamos las tablas hash, sino también decenas de otros temas importantes para los desarrolladores: desde los conceptos básicos hasta las técnicas avanzadas. Nuestros cursos incluyen tareas prácticas y casos reales de la industria.

Únete a nuestro canal de Telegram — aquí encontrarás una comunidad amigable de desarrolladores, materiales útiles cada semana, análisis de tareas interesantes y respuestas a preguntas.

¡Crezcamos juntos! 🚀