Sob quais condições as operações em HashMap têm uma complexidade de tempo proporcional ao tamanho da coleção?

As operações em HashMap (por exemplo, get, put) geralmente têm uma complexidade de tempo amortizada de O(1). No entanto, em alguns casos, a complexidade pode aumentar para O(n), onde n é o tamanho da coleção. Isso ocorre se:

• Todas as chaves caírem em um único balde devido a uma má função de hash, levando a uma lista longa ou a uma árvore em uma única célula.
• As colisões não forem distribuídas uniformemente, e a estrutura de dados dentro do balde se degradar.

No Java 8 e versões superiores, se houver muitos elementos em um balde, HashMap converte a lista ligada em uma árvore balanceada (TreeNode), o que reduz o pior caso para O(log n), mas não para O(1).

Assim, as operações tornam-se proporcionais ao tamanho da coleção em caso de colisões fortes e má distribuição de hashes.