Como é avaliada a eficiência da busca de um elemento por chave em um HashMap na presença de colisões?

No HashMap, a pesquisa de um elemento por chave geralmente ocorre em tempo O(1), mas na presença de colisões, a eficiência depende do método de tratamento dessas colisões.

Anteriormente, as colisões eram tratadas com cadeias (listas ligadas), e no pior caso (quando todas as chaves caem na mesma caixa), a pesquisa tornava-se O(n).

A partir do Java 8, se o número de elementos numa caixa exceder um determinado limite, a lista ligada é transformada numa árvore balanceada (por exemplo, uma árvore vermelho-preto). Isto melhora o pior caso de pesquisa para O(log n) para essa caixa.

Assim:

• Com poucas colisões, a pesquisa permanece próxima de O(1).
• Com muitas colisões numa caixa, a pesquisa será O(log n).

Esta melhoria aumenta significativamente o desempenho do HashMap em cenários adversos.