Qual é a complexidade de tempo de procurar um elemento em um HashMap por chave?

Na HashMap, a busca de um elemento por chave é geralmente realizada em tempo O(1), ou seja, tempo constante. Isso é alcançado graças à hashificação da chave e ao acesso rápido ao balde correspondente. No entanto, no pior caso, com muitas colisões, a complexidade pode degradar-se para O(n), onde n é o número de elementos no balde.