Que estratégias são usadas para lidar com colisões de hash no container unordered_map?

Num recipiente unordered_map para lidar com colisões de hash, geralmente é utilizado o método de encadeamento. Isso significa que todos os elementos cujo valor hash retorna o mesmo índice são armazenados numa lista ligada ou outra estrutura de dados num mesmo balde (bucket).

Quando ocorre uma colisão, o novo elemento é adicionado à lista correspondente ao balde. Na busca, percorrem-se os elementos nesse balde para encontrar a chave desejada.

Assim, as estratégias principais são:

• Encadeamento (chaining) — armazenamento de colisões em listas em cada balde.
• Em algumas implementações, podem ser usadas outras estruturas para os baldes, como árvores balanceadas, para acelerar a busca em caso de muitas colisões.

É assim que aproximadamente é implementado o unordered_map padrão em C++.