Como é determinado o tempo de acesso a um elemento na estrutura de dados HashMap?

O tempo de acesso a um elemento na estrutura de dados HashMap em Java é geralmente considerado constante — O(1). Isso é alcançado usando uma função hash que converte a chave em um índice de array onde o valor é armazenado.

No entanto, na prática, o tempo de acesso pode aumentar até O(n) no pior caso, se ocorrerem muitas colisões (chaves diferentes com o mesmo hash), e os elementos são armazenados em uma lista ligada ou árvore dentro de uma mesma célula.

Desde o Java 8, para reduzir o tempo de acesso em colisões, a lista ligada é transformada em uma árvore balanceada (TreeMap), o que reduz o tempo de busca para O(log n) nesses casos.

Assim, o tempo médio de acesso é próximo de O(1), mas nos piores casos pode ser O(log n) ou O(n).