Πώς καθορίζεται η χρονική πολυπλοκότητα της λειτουργίας προσθήκης ενός στοιχείου σε έναν πίνακα κατακερματισμού;

Η χρονική πολυπλοκότητα της λειτουργίας προσθήκης ενός στοιχείου σε έναν πίνακα κατακερματισμού θεωρείται γενικά ως αθροιστικά O(1). Αυτό σημαίνει ότι, κατά μέσο όρο, η προσθήκη πραγματοποιείται σε σταθερό χρόνο, καθώς το στοιχείο τοποθετείται άμεσα στο αντίστοιχο καλάθι σύμφωνα με το hash. Ωστόσο, στην χειρότερη περίπτωση, αν προκύψει σύγκρουση (πολλά στοιχεία στο ίδιο καλάθι), ή όταν απαιτείται επέκταση του πίνακα (rehash), η λειτουργία μπορεί να διαρκέσει O(n) χρόνο, όπου n είναι ο αριθμός των στοιχείων στον πίνακα. Αλλά χάρη σε καλό hash και έλεγχο φόρτωσης του πίνακα, τέτοιες περιπτώσεις είναι σπάνιες.