In quali condizioni le operazioni in HashMap hanno una complessità temporale proporzionale alla dimensione della collezione?

Le operazioni in HashMap (ad esempio, get, put) hanno generalmente una complessità temporale ammortizzata di O(1). Tuttavia, in alcuni casi, la complessità può aumentare fino a O(n), dove n è la dimensione della collezione. Ciò accade se:

• Tutte le chiavi finiscono in un unico contenitore (bucket) a causa di una funzione di hash scadente, portando a una lunga lista o a un albero in una singola cella.
• Le collisioni non sono distribuite uniformemente e la struttura dati all’interno del contenitore si degrada.

In Java 8 e versioni successive, se ci sono troppi elementi in un contenitore, HashMap trasforma la lista collegata in un albero bilanciato (TreeNode), riducendo il caso peggiore a O(log n), ma non a O(1).

Pertanto, le operazioni diventano proporzionali alla dimensione della collezione in presenza di collisioni forti e cattiva distribuzione degli hash.