Ποια είναι η ταχύτητα λειτουργίας του πίνακα κατακερματισμού;

Η ταχύτητα λειτουργίας ενός πίνακα κατακερματισμού, ή ο χρόνος πρόσβασης στα δεδομένα (αναζήτηση, εισαγωγή, διαγραφή), στην ιδανική περίπτωση είναι O(1) — σταθερός.

Αυτό επιτυγχάνεται με τη χρήση μιας συνάρτησης κατακερματισμού που μετατρέπει γρήγορα το κλειδί σε ένα δείκτη πίνακα.

Η πραγματική ταχύτητα εξαρτάται από:

• Την ποιότητα της συνάρτησης κατακερματισμού: Μια καλή συνάρτηση διανέμει ομοιόμορφα τα κλειδιά, ελαχιστοποιώντας τις συγκρούσεις.
• Τις στρατηγικές επίλυσης συγκρούσεων:
  • Αποσπασμένη αλυσίδα (separate chaining): Σε περίπτωση σύγκρουσης, τα στοιχεία με το ίδιο hash αποθηκεύονται σε μια συνδεδεμένη λίστα ή σε έναν άλλο δυναμικό πίνακα. Ο χρόνος πρόσβασης μπορεί να φτάσει το O(N) στην χειρότερη περίπτωση (όλα τα στοιχεία στην ίδια "καλάθι"), όπου N είναι ο αριθμός των στοιχείων.
  • Ανοιχτός προσδιορισμός (open addressing): Σε περίπτωση σύγκρουσης, αναζητείται το επόμενο ελεύθερο κελί στον πίνακα. Ο χρόνος πρόσβασης μπορεί επίσης να επιδεινωθεί με πολλές συγκρούσεις.
• Ο παράγοντας φόρτωσης (load factor): Η αναλογία μεταξύ του αριθμού των στοιχείων και του μεγέθους του πίνακα κατακερματισμού. Ένας υψηλός παράγοντας φόρτωσης αυξάνει την πιθανότητα συγκρούσεων και επιβραδύνει την απόδοση. Όταν φτάσει σε ένα συγκεκριμένο όριο, απαιτείται επανακατασκευή (rehashing), που είναι μια σχετικά δαπανηρή λειτουργία (O(N)).

Έτσι, αν και η θεωρητική ταχύτητα O(1) είναι η καλύτερη περίπτωση, στην πράξη μπορεί να είναι ελαφρώς υψηλότερη λόγω συγκρούσεων και ανάγκης επανακατασκευής, ειδικά με μεγάλο όγκο δεδομένων ή μη βέλτιστες συναρτήσεις κατακερματισμού.