Υπάρχουν συνθήκες υπό τις οποίες οι λειτουργίες σε HashMap έχουν χρονική πολυπλοκότητα ανάλογη με το μέγεθος της συλλογής;

Οι λειτουργίες σε HashMap (π.χ., get, put) έχουν συνήθως μια αθροιστική χρονική πολυπλοκότητα O(1). Ωστόσο, σε ορισμένες περιπτώσεις, η πολυπλοκότητα μπορεί να αυξηθεί έως και O(n), όπου n είναι το μέγεθος της συλλογής. Αυτό συμβαίνει αν:

• Όλες οι κλειδιά καταλήγουν σε ένα καλάθι (bucket) λόγω κακής λειτουργίας κατακερματισμού, οδηγώντας σε μια μεγάλη λίστα ή δέντρο σε ένα κελί.
• Οι συγκρούσεις κατανέμονται άνισα και η δομή δεδομένων μέσα στο καλάθι υποβαθμίζεται.

Στην Java 8 και νεότερες εκδόσεις, αν σε ένα καλάθι υπάρχουν πάρα πολλά στοιχεία, το HashMap μετατρέπει τη συνδεδεμένη λίστα σε ένα ισορροπημένο δέντρο (TreeNode), το οποίο μειώνει την χειρότερη περίπτωση σε O(log n), αλλά όχι σε O(1).

Έτσι, οι λειτουργίες γίνονται ανάλογες με το μέγεθος της συλλογής σε περιπτώσεις ισχυρών συγκρούσεων και κακής κατανομής των κατακερματισμών.