Ποια είναι η πολυπλοκότητα του ελέγχου της ύπαρξης ενός στοιχείου σε ένα set στην χειρότερη περίπτωση, όταν όλα τα στοιχεία έχουν τον ίδιο hash;

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

Σε αυτήν την περίπτωση, η επαλήθευση της ύπαρξης ενός στοιχείου απαιτεί την περιήγηση σε όλα τα στοιχεία σε αυτό το καλάθι, κάτι που δίνει μια πολυπλοκότητα O(n), όπου n είναι ο αριθμός των στοιχείων στο σύνολο.

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