Como decides onde inserir uma nova chave-valor na tabela hash?

Num quadro hash, o local para uma nova chave-valor é determinado por uma função hash, que converte a chave num índice do array (bucket).

O algoritmo de inserção geralmente é assim:

1. Calcula-se o valor hash da chave.
2. Converte-se o hash num índice do array (por exemplo, usando módulo do tamanho do array).
3. Se esse bucket não contém elementos, insere-se o par lá.
4. Se há colisão (já existe um elemento com outra chave), aplica-se um método de resolução de colisões:
   • Encadeamento (chaining): mantém-se uma lista no bucket, e o novo elemento é adicionado a essa lista.
   • Endereçamento aberto: procura-se o próximo bucket livre de acordo com uma sequência determinada (sondagem linear, quadrática, etc.).

Exemplo em C++ (encadeamento):

size_t hash = std::hash<KeyType>{}(key) % bucket_count;
// buckets[hash] - lista de pares chave-valor
buckets[hash].push_back({key, value});

Dessa forma, o local de inserção é determinado pela função hash e pela estratégia de resolução de colisões.