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

A complexidade média é O(1), no pior caso é O(n).

• Caso médio (O(1)): Com uma boa função hash e distribuição uniforme dos elementos pelas baldes, a busca reduz-se a calcular o hash da chave e aceder diretamente ao balde correspondente do array. Dentro do balde, se não houver colisões, o elemento encontra-se em tempo constante.
• Pior caso (O(n)): Acontece quando todos os elementos são hashados no mesmo balde. Nesse caso, a busca torna-se uma pesquisa linear numa lista ligada (ou numa árvore balanceada em Java 8+ para baldes com muitos elementos, mas mesmo percorrer a árvore pode levar O(log n), o que, com muitas colisões num único balde, ainda se aproxima de O(n) relativamente ao número total de elementos se todos caírem no mesmo balde).

Desde Java 8, para baldes que contêm mais de um limite definido (TREEIFY_THRESHOLD, por padrão 8) elementos, a lista ligada é transformada numa árvore balanceada (Árvore Vermelho-Preto). Isto melhora o pior caso de busca dentro de um balde para O(log n), mas se todas as chaves tiverem o mesmo hash, a busca geral ainda pode estar próxima de O(n).