¿Cómo funciona una tabla hash?

Una tabla hash (hash table) es una estructura de datos que implementa un array asociativo.

Principio de funcionamiento:

1. Hashing. Para cada clave (key) se calcula un código hash (hash code) mediante una función hash (hash function). El código hash es un número entero.
2. Indexación. El código hash se usa para determinar un índice (index) en el array (o vector) de la estructura interna de la tabla hash. Normalmente, el índice se calcula como hash_code % tamaño_del_array, donde tamaño_del_array es el tamaño del array.
3. Almacenamiento. En el índice encontrado, se almacena el valor (value) asociado a la clave.

Problemas y soluciones:

• Colisiones. Diferentes claves pueden dar el mismo código hash y, por lo tanto, el mismo índice en el array. Esto se llama colisión.
  • Métodos para resolver colisiones:
    • Método de encadenamiento (Separate Chaining): En cada celda del array se guarda una lista (lista, vector, etc.) de pares "clave-valor". En caso de colisión, la nueva pareja se añade a esta lista. Para buscar por índice, se recorre la lista correspondiente para encontrar la clave deseada.
    • Método de direccionamiento abierto (Open Addressing): En caso de colisión, se busca otra celda libre en el array siguiendo una regla determinada (sondeo).
      • Sondeo lineal (Linear Probing): Se verifican secuencialmente las celdas index + 1, index + 2, etc., módulo el tamaño del array.
      • Sondeo cuadrático (Quadratic Probing): Se verifican las celdas index + 1^2, index + 2^2, etc., módulo el tamaño del array.
      • Doble hashing (Double Hashing): Se usa una segunda función hash para determinar el paso del sondeo.

Ventajas:

• En promedio, las operaciones de inserción, eliminación y búsqueda se realizan con una complejidad O(1).

Desventajas:

• En el peor caso (por ejemplo, muchas colisiones o mala función hash), la complejidad puede llegar a O(n), donde n es el número de elementos.
• Requiere memoria adicional (por ejemplo, para listas en el método de encadenamiento o para sondeo en direccionamiento abierto).

Ejemplo de uso en C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Creación de la tabla hash (unordered_map)
    std::unordered_map<std::string, int> edades;

    // Inserción de elementos
    edades["Alice"] = 30;
    edades["Bob"] = 25;
    edades["Charlie"] = 35;

    // Obtener valor por clave
    std::cout << "Edad de Alice: " << edades["Alice"] << std::endl;

    // Buscar elemento
    if (edades.count("Bob")) {
        std::cout << "Bob está en el mapa." << std::endl;
    }

    // Eliminar elemento
    edades.erase("Charlie");

    return 0;
}