O tempo de busca de um elemento na HashMap é garantido como constante ao usar a chave?

Em HashMap em Java, o tempo de pesquisa de um elemento por chave é considerado em média constante — O(1). Isso é alcançado através do uso de uma função hash para calcular o índice do balde (bucket) onde o elemento é armazenado.

No entanto, no pior caso, quando todas as chaves caem em um único balde (devido a colisões), a pesquisa pode degradar para O(n), pois os elementos no balde são armazenados na forma de uma lista ligada ou árvore (a partir do Java 8).

Assim, o tempo constante de pesquisa é garantido apenas em média, com uma distribuição uniforme dos hashes e sem um grande número de colisões.