É garantido um acesso rápido e constante ao longo do tempo aos dados na estrutura HashMap?

Na estrutura de dados HashMap em Java, o acesso rápido aos dados é garantido em média por um tempo constante — O(1). Isto é conseguido através do uso de uma função hash que converte a chave num índice de array onde o valor é armazenado.

No entanto, no pior caso (por exemplo, quando há muitas colisões e todas as chaves caem numa mesma caixa), o tempo de acesso pode degradar-se para O(n), onde n é o número de elementos nessa caixa.

As implementações modernas de HashMap (a partir do Java 8) usam árvores balanceadas (TreeNode) para caixas com muitas colisões, o que melhora o pior caso para O(log n).

Assim, o acesso aos dados em HashMap costuma ser muito rápido e próximo de um tempo constante, mas não garante que seja estritamente constante em todas as situações.