Quando você escolheria um hash map em vez de uma árvore binária de busca balanceada?

Escolha um hash map quando você só precisa de buscas, inserções e remoções por chave, e quer tempo constante em média. Escolha uma árvore balanceada quando precisa de ordenação: varreduras por faixa, chave mais próxima ou iteração em ordem, tudo em tempo logarítmico. Árvores também dão comportamento previsível no pior caso, enquanto um hash map pode degradar feio com hashing ruim ou travar num resize na hora errada.

Meu padrão é hash map, porque na maior parte do tempo eu estou fazendo busca pontual por id e tempo constante em média é difícil de bater. No momento em que o requisito envolve ordenação, porém, eu mudo. Qualquer coisa do tipo me dê todos os eventos entre dois timestamps, ou ache a próxima chave depois desta, é uma consulta por faixa, e um hash map não consegue fazer isso sem varrer tudo. Isso pede uma árvore, ou na prática uma estrutura ordenada com busca binária. Eu também penso na cauda. Buscas de hash são constantes em média, mas uma função de hash ruim ou um rehash podem dar pico, e dentro de um orçamento de latência isso me importa. Numa funcionalidade de leaderboard que construí a gente começou com um dicionário de usuário para pontuação e depois tinha que ordenar tudo a cada leitura. Quando migramos para um sorted set no Redis, as leituras viraram logarítmicas e o endpoint parou de cair no pico. Mesmos dados, padrão de acesso diferente, estrutura diferente.