Teoría: Tablas hash

Cuando trabajamos con datos en programación, a menudo necesitamos estructuras que nos ayuden a organizarlos de manera eficiente.

En esta lección, hablaremos sobre los arrays asociativos, un tipo de estructura que nos permite almacenar pares clave-valor, y veremos cómo funcionan internamente en JavaScript mediante el uso de tablas hash.

¿Qué es un array asociativo?

Dependiendo del lenguaje de programación, los arrays asociativos reciben distintos nombres:

En JavaScript, los arrays asociativos se representan mediante objetos (Object).

Uso de los arrays asociativos

Los arrays asociativos son muy utilizados en programación para almacenar datos estructurados. Son esenciales cuando trabajamos con información que incluye múltiples parámetros diferentes, como:

• Representación de un usuario en una aplicación:

  const usuario = {
    nombre: 'Carlos',
    edad: 30,
    correo: 'carlos@gmail.com'
  };

  Expand code

• Configuración de una aplicación:

  const configuracion = {
    tema: 'oscuro',
    idioma: 'es',
    notificaciones: true
  };

  Expand code

A diferencia de los arrays indexados:

const numeros = [10, 20, 30];  
console.log(numeros[0]); // 10 (accede por índice)

En un array asociativo usamos claves descriptivas:

const persona = { nombre: 'Ana', edad: 25 };
console.log(persona['nombre']); // Ana
console.log(persona.edad); // 25

¿Cómo funcionan los arrays asociativos internamente?

Internamente, los arrays asociativos en JavaScript no se almacenan simplemente como listas de pares clave-valor. En su lugar, se utiliza una estructura llamada tabla hash.

¿Cómo se almacena un valor en un array asociativo?

Cuando escribimos:

const data = {};
data['key'] = 'value';

El motor de JavaScript sigue estos pasos internamente:

1. Se inicializa un array indexado interno para almacenar los datos.

2. Se genera un hash a partir de la clave 'key'.

3. El hash se convierte en un índice del array.

4. Se almacena el valor en ese índice:

   internal[index] = ['key', 'value'];

   Expand code

De esta manera, cuando posteriormente hacemos:

console.log(data['key']); // "value"

El motor de JavaScript encuentra el valor correspondiente a 'key' rápidamente utilizando su hash.

¿Qué es el hashing?

Un hash es el resultado de aplicar una función de hashing a una clave. Algunos algoritmos de hashing conocidos son CRC32, MD5 y SHA.

JavaScript no cuenta con un algoritmo de hashing incorporado, así que usamos una biblioteca de terceros:

import crc32 from 'crc-32';

const data = '¡Hola, mundo!'; 
const hash = crc32.str(data);

console.log(hash); // Siempre genera el mismo hash para el mismo dato

Este hash luego se convierte en un índice dentro de la tabla, por ejemplo:

const index = Math.abs(hash) % 1000; 
console.log(index); // => 338

De esta manera, las claves no ocupan espacios innecesarios en memoria y se pueden localizar eficientemente.

¿Qué es una colisión?

crc32.str('aaaaa0.462031558722291'); // 1938556049
crc32.str('aaaaa0.0585754039730588'); // 1938556049 (mismo hash, colisión)

Las colisiones pueden ser un problema porque dos valores diferentes terminan "chocando" en el mismo lugar dentro de la tabla.

Métodos para resolver colisiones

Existen diferentes estrategias para manejar estas colisiones. Un método común es el direccionamiento abierto, que busca la siguiente posición libre en la tabla hash. Otro método es el encadenamiento, donde cada índice almacena una lista de elementos que comparten el mismo hash.