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

Η αποτελεσματικότητα της λειτουργίας εισαγωγής ενός στοιχείου σε έναν πίνακα κατακερματισμού εξαρτάται από πολλούς παράγοντες:

1. Ο δείκτης φόρτωσης του πίνακα (load factor) — η αναλογία μεταξύ του αριθμού των στοιχείων και του μεγέθους του πίνακα. Με χαμηλό φορτίο, η εισαγωγή πραγματοποιείται συνήθως σε χρόνο amortized O(1).

2. Η ποιότητα της συνάρτησης κατακερματισμού — η ομοιόμορφη κατανομή των κλειδιών ελαχιστοποιεί τις συγκρούσεις.

3. Διαχείριση συγκρούσεων:

   • Με chaining, η εισαγωγή γίνεται προσθέτοντας σε μια συνδεδεμένη λίστα ή άλλο δοχείο στον κάδο. Μέσος όρος O(1), αλλά στην χειρότερη περίπτωση O(n) αν όλα τα στοιχεία καταλήξουν στον ίδιο κάδο.
   • Με ανοιχτό προσδιορισμό (linear probing, quadratic probing), η εισαγωγή μπορεί να απαιτεί αναζήτηση ελεύθερου χώρου, αυξάνοντας το χρόνο σε υψηλό φορτίο.

4. Rehashing — όταν φτάσει ένα όριο φόρτωσης, ο πίνακας επεκτείνεται, απαιτώντας την επαναδιάταξη των στοιχείων και προσωρινά αυξάνοντας τον χρόνο εισαγωγής.

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