Como é estruturada uma tabela hash no container…

unordered_map em C++ é implementado como uma tabela de dispersão.

Princípio de funcionamento:

Hashing: A chave é transformada num número inteiro — código de hash — usando uma função de hash.
Indexação: O código de hash é usado para determinar o índice (balde ou bucket) numa matriz de ponteiros ou listas.
Armazenamento: Em cada balde, são armazenados pares chave-valor.

Características:

Baldes: A tabela de dispersão consiste numa matriz de baldes. O número de baldes pode mudar dinamicamente (rehashing) quando um determinado fator de carga é atingido.
Colisões: Chaves diferentes podem gerar o mesmo código de hash. Isto é chamado colisão. Para resolver colisões, unordered_map usa o método encadeamento: os elementos com o mesmo hash são adicionados a uma lista ligada (ou outra estrutura de dados) no balde correspondente.
Função de hash e função de comparação: Para um funcionamento correto, são necessárias duas coisas:
- Uma boa função de hash, que distribua uniformemente as chaves pelos baldes, minimizando colisões.
- Uma função de igualdade (o operador ==), para distinguir chaves com o mesmo código de hash no mesmo balde.
Desempenho: Em média, as operações de inserção, remoção e pesquisa têm complexidade temporal O(1). No pior caso (por exemplo, muitas colisões ou uma função de hash mal escolhida), o desempenho pode degradar-se para O(n), onde n é o número de elementos.

Exemplo de estrutura (simplificada):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Para lista ligada no balde
};

struct Bucket {
  Node* head; // Ponteiro para o início da lista
};

Bucket* buckets; // Matriz de baldes
size_t num_buckets;

Processo de adição de elemento:

Calcula-se o código de hash da chave.
Determina-se o índice do balde: bucket_index = hash(key) % num_buckets.
O par chave-valor é adicionado à lista de elementos nesse balde. Se a chave já existir, o valor é atualizado.

Processo de busca de elemento:

Calcula-se o código de hash da chave.
Determina-se o índice do balde.
Percorre-se a lista de elementos nesse balde, comparando as chaves com a chave procurada usando o operador ==.

O rehashing ocorre quando o número de elementos em relação ao número de baldes ultrapassa um limite (fator de carga). Durante o rehashing, é criado um novo array de baldes maior, e todos os elementos dos antigos baldes são re-hashados e movidos para os novos.

Como é estruturada uma tabela hash no container unordered_map?