Tablas hash

¿Qué es una tabla hash?

Una tabla hash (también llamada hash map) es una estructura de datos que implementa un arreglo asociativo, mapeando claves a valores. Usa una función hash para calcular un índice en un arreglo de buckets donde se almacena el valor. ¡Las tablas hash ofrecen O(1) promedio para buscar, insertar y eliminar!

Cómo funcionan las tablas hash

Una tabla hash funciona convirtiendo cada clave en un índice numérico mediante una función hash. Ese índice determina en qué posición del arreglo interno se almacena el valor, permitiendo acceso directo en tiempo constante.

// Simple hash table example
Key: "apple"  → Hash Function → Index: 3
Key: "banana" → Hash Function → Index: 7
Key: "orange" → Hash Function → Index: 2

Array:
[0] → null
[1] → null
[2] → "orange" = 5
[3] → "apple" = 10
[4] → null
[5] → null
[6] → null
[7] → "banana" = 3

Funciones hash

Una buena función hash debe:

• Ser determinista (la misma entrada da la misma salida)
• Distribuir claves uniformemente en la tabla
• Ser rápida de calcular
• Minimizar colisiones

Función hash simple

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

console.log(simpleHash("apple", 10));   // Index in 0-9
console.log(simpleHash("banana", 10));  // Index in 0-9

Mejor función hash (djb2)

function djb2Hash(key, tableSize) {
  let hash = 5381;
  
  for (let i = 0; i < key.length; i++) {
    // hash * 33 + char
    hash = ((hash << 5) + hash) + key.charCodeAt(i);
  }
  
  return Math.abs(hash % tableSize);
}

Manejo de colisiones

Las colisiones ocurren cuando dos claves hashean al mismo índice. Dos métodos principales:

1. Encadenamiento (chaining separado)

Cada bucket almacena una lista de elementos que colisionan.

class HashTableChaining {
  constructor(size = 53) {
    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) * 31) % this.size;
    }
    return hash;
  }

  set(key, value) {
    const index = this._hash(key);
    
    // Initialize bucket if empty
    if (!this.table[index]) {
      this.table[index] = [];
    }
    
    // Check if key exists and update
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    
    // Add new key-value pair
    this.table[index].push([key, value]);
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.table[index];
    
    if (!bucket) return undefined;
    
    // Search in bucket
    for (let pair of bucket) {
      if (pair[0] === key) {
        return pair[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;
  }

  keys() {
    const keys = [];
    for (let bucket of this.table) {
      if (bucket) {
        for (let pair of bucket) {
          keys.push(pair[0]);
        }
      }
    }
    return keys;
  }

  values() {
    const values = [];
    for (let bucket of this.table) {
      if (bucket) {
        for (let pair of bucket) {
          values.push(pair[1]);
        }
      }
    }
    return values;
  }
}

// Usage
const ht = new HashTableChaining();
ht.set("apple", 10);
ht.set("banana", 5);
ht.set("orange", 8);
console.log(ht.get("apple"));    // 10
console.log(ht.keys());          // ['apple', 'banana', 'orange']

2. Direccionamiento abierto (sondeo lineal)

Si ocurre una colisión, se busca el siguiente slot libre.

class HashTableOpenAddressing {
  constructor(size = 53) {
    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) * 31) % this.size;
    }
    return hash;
  }

  set(key, value) {
    if (this.count / this.size > 0.7) {
      this._resize();
    }
    
    let index = this._hash(key);
    
    // Linear probing - find next empty slot
    while (this.table[index] !== undefined) {
      // Update if key exists
      if (this.table[index][0] === key) {
        this.table[index][1] = value;
        return;
      }
      index = (index + 1) % this.size;
    }
    
    this.table[index] = [key, value];
    this.count++;
  }

  get(key) {
    let index = this._hash(key);
    const startIndex = index;
    
    while (this.table[index] !== undefined) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.size;
      
      // Wrapped around - not found
      if (index === startIndex) break;
    }
    
    return undefined;
  }

  _resize() {
    const oldTable = this.table;
    this.size = this.size * 2;
    this.table = new Array(this.size);
    this.count = 0;
    
    for (let item of oldTable) {
      if (item !== undefined) {
        this.set(item[0], item[1]);
      }
    }
  }
}

Problemas comunes con tablas hash

1. Two Sum (usando hash map)

El problema Two Sum busca dos números en un arreglo que sumen un objetivo dado. Usando un hash map, se puede resolver en O(n) almacenando cada número y verificando si su complemento ya fue visto.

function twoSum(nums, target) {
  const map = new Map();
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    
    map.set(nums[i], i);
  }
  
  return null;
}

console.log(twoSum([2, 7, 11, 15], 9));  // [0, 1]

2. Agrupar anagramas

Para agrupar anagramas, se ordena alfabéticamente cada cadena y se usa como clave del hash map. Todas las palabras con las mismas letras comparten la misma clave ordenada.

function groupAnagrams(strs) {
  const map = new Map();
  
  for (let str of strs) {
    // Sort string as key
    const sorted = str.split('').sort().join('');
    
    if (!map.has(sorted)) {
      map.set(sorted, []);
    }
    
    map.get(sorted).push(str);
  }
  
  return Array.from(map.values());
}

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

3. Primer carácter no repetido

Se cuentan las ocurrencias de cada carácter en un hash map y luego se recorre la cadena nuevamente para encontrar el primer carácter con frecuencia uno.

function firstNonRepeating(str) {
  const charCount = new Map();
  
  // Count frequencies
  for (let char of str) {
    charCount.set(char, (charCount.get(char) || 0) + 1);
  }
  
  // Find first with count 1
  for (let char of str) {
    if (charCount.get(char) === 1) {
      return char;
    }
  }
  
  return null;
}

console.log(firstNonRepeating("leetcode"));  // 'l'

4. Subarray sum igual a K

Este problema usa sumas acumuladas y un hash map para contar cuántos subarreglos suman exactamente K. Se almacena cada suma parcial y se verifica si la diferencia con K ya apareció.

function subarraySum(nums, k) {
  const map = new Map([[0, 1]]);
  let sum = 0;
  let count = 0;
  
  for (let num of nums) {
    sum += num;
    
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }
    
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  
  return count;
}

console.log(subarraySum([1, 1, 1], 2));  // 2

Map de JavaScript vs Object

Complejidad temporal