¿Que son las tablas hash? - 10/05/2024

Introducción

El primer concepto que he encontrado en mi aventura en LeetCode son las tablas hash. Ya me había topado con ellas anteriormente durante el primer año del grado superior, donde la asignatura de programación era en Java. Sin embargo, había pasado bastante tiempo desde la última vez que las había utilizado, y he tenido que refrescar mi memoria. Se usan en bastantes algoritmos sobre todo cuando hay que hacer búsquedas rápidas en bastante información.

¿Cuando tenemos que usarlas?

Para explicar por qué es útil vamos a tomar el enunciado de un ejemplo muy típico en internet. Dado un conjunto de números en un vector (array) y un número que es el objetivo tienes que encontrar dos elementos en el vector que sumen ese objetivo.

Solucion con fuerza bruta

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        return null;
    }
}

Hasta aquí ningún problema este código está correcto resuelve el problema que teníamos pero queda bastante lejos de ser la solución más eficiente. Cuando LeetCode marco mi solución con complejidad 0(n2) dije, esto que es.

0(n2) —> Significa que por cada elemento del vector tengo que recorrer el vector entero. Si el vector tiene 100 elementos tengo que recorrer 100 * 100 = 10000 elementos. Si el vector tiene 1000 elementos tengo que recorrer 1000*1000 = 1000000 elementos. Y así sucesivamente.

Big O Notation: https://medium.com/nowports-tech/introducci%C3%B3n-a-big-o-notation-95ecca8bd866;

Solución con tablas hash

Para solucionar este problema de manera más eficiente, podemos utilizar una tabla hash. La idea es recorrer el vector una sola vez y por cada elemento que recorramos, comprobar si el complemento de ese elemento (target - nums[i]) está en la tabla hash. Si está, hemos encontrado la solución. Si no está, añadimos el elemento a la tabla hash y seguimos recorriendo el vector.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int aux = target - nums[i];
            if (map.containsKey(aux)) {
                return new int[]{map.get(aux), i};
            }
            map.put(nums[i], i);
        } 
        return null;
    }
   
}

En resumen con la tabla hash el coste de encontrar la solución siempre es constante, no varía en función del tamaño del vector.