Ποια είναι η πολυπλοκότητα της αναζήτησης ενός στοιχείου με κλειδί σε ένα HashMap;

Η μέση πολυπλοκότητα είναι O(1), στην χειρότερη περίπτωση — O(n).

• Μέση περίπτωση (O(1)): Με μια καλή συνάρτηση κατακερματισμού και ομοιόμορφη κατανομή των στοιχείων στους κάδους (buckets), η αναζήτηση περιορίζεται στον υπολογισμό του hash της κλειδί και την άμεση πρόσβαση στον αντίστοιχο κάδο στον πίνακα. Μέσα στον κάδο, αν δεν υπάρχουν συγκρούσεις, το στοιχείο βρίσκεται σε σταθερό χρόνο.
• Χειρότερη περίπτωση (O(n)): Προκύπτει όταν όλα τα στοιχεία κατακερματίζονται στον ίδιο κάδο. Σε αυτή την περίπτωση, η αναζήτηση γίνεται γραμμική αναζήτηση σε μια συνδεδεμένη λίστα (ή σε ένα ισορροπημένο δέντρο σε Java 8+ για κάδους με πολλά στοιχεία, αλλά ακόμα και η διαδρομή του δέντρου μπορεί να πάρει O(log n), που σε περίπτωση πολλών συγκρούσεων σε έναν κάδο, πλησιάζει το O(n)).

Από την Java 8, για κάδους που περιέχουν περισσότερα από ένα ορισμένο όριο (TREEIFY_THRESHOLD, προεπιλογή 8) στοιχεία, η συνδεδεμένη λίστα μετατρέπεται σε ισορροπημένο δέντρο (Δέντρο Κόκκινο-Μαύρο). Αυτό βελτιώνει την χειρότερη περίπτωση αναζήτησης εντός ενός κάδου σε O(log n), αλλά αν όλες οι κλειδιά έχουν το ίδιο hash, η γενική αναζήτηση μπορεί ακόμα να είναι κοντά στο O(n).