Qual é a complexidade temporal da operação de busca de um elemento numa HashMap no caso médio?

Na média, a operação de busca de um elemento em HashMap em Java tem uma complexidade de tempo de O(1) — tempo constante.

Isto é alcançado através do uso de uma função hash que calcula o índice do balde (bucket) para armazenar o par chave-valor. Com uma distribuição ideal dos elementos pelos baldes, a busca ocorre diretamente.

No entanto, no pior caso (por exemplo, com muitas colisões), a complexidade pode degradar para O(n), onde n é o número de elementos no HashMap, se todos os elementos caírem em um único balde. As implementações modernas de Java (a partir do Java 8) usam árvores balanceadas (TreeNodes) dentro dos baldes em caso de muitas colisões, o que reduz o pior cenário para O(log n).

Assim, na maioria dos casos práticos, pode-se considerar que a busca no HashMap é uma operação com complexidade amortizada de O(1).