¿Cómo está estructurada una tabla hash en el…

unordered_map en C++ se implementa como una tabla hash.

Principio de funcionamiento:

Hashing: La clave se transforma en un número entero — código hash — mediante una función hash.
Indexación: El código hash se usa para determinar el índice (cesta o bucket) en un array de punteros o listas.
Almacenamiento: En cada cesta se almacenan pares clave-valor.

Características:

Cestas: La tabla hash consiste en un array de cestas. La cantidad de cestas puede cambiar dinámicamente (rehashing) cuando se alcanza un cierto factor de carga.
Colisiones: Diferentes claves pueden dar el mismo código hash. Esto se llama colisión. Para resolver colisiones, unordered_map usa el método encadenamiento: los elementos con el mismo hash se añaden a una lista enlazada (o estructura de datos similar) en la cesta correspondiente.
Función hash y función de comparación: Para un funcionamiento correcto se necesitan dos cosas:
- Una buena función hash, que distribuya uniformemente las claves entre las cestas, minimizando colisiones.
- Una función de igualdad (el operador ==), para distinguir claves con el mismo código hash en una misma cesta.
Rendimiento: En promedio, las operaciones de inserción, eliminación y búsqueda tienen una complejidad temporal O(1). En el peor caso (por ejemplo, muchas colisiones o una función hash mal elegida), el rendimiento puede degradarse a O(n), donde n es el número de elementos.

Ejemplo de estructura (simplificado):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Para lista enlazada en la cesta
};

struct Bucket {
  Node* head; // Puntero al inicio de la lista
};

Bucket* buckets; // Array de cestas
size_t num_buckets;

Proceso de añadir un elemento:

Se calcula el código hash de la clave.
Se determina el índice de la cesta: bucket_index = hash(key) % num_buckets.
El par clave-valor se añade a la lista de elementos en esa cesta. Si la clave ya existe, se actualiza el valor.

Proceso de búsqueda de un elemento:

Se calcula el código hash de la clave.
Se determina el índice de la cesta.
Se recorre la lista de elementos en esa cesta, comparando las claves con la clave buscada usando el operador ==.

El rehashing ocurre cuando la cantidad de elementos en relación con el número de cestas supera un umbral (factor de carga). Durante el rehashing, se crea un nuevo array de cestas más grande, y todos los elementos de las cestas antiguas se vuelven a hash y se mueven a las nuevas.

¿Cómo está estructurada una tabla hash en el contenedor unordered_map?