Από ποια στοιχεία αποτελείται ένας πίνακας κατακερματισμού;

Ο πίνακας κατακερματισμού αποτελείται από:

1. Πίνακας (ή λίστα): Η κύρια δομή δεδομένων όπου αποθηκεύονται τα στοιχεία. Μερικές φορές ονομάζονται "κάδοι" (buckets) ή "θέσεις".
2. Συνάρτηση κατακερματισμού: Συνάρτηση που λαμβάνει ένα κλειδί ως είσοδο και επιστρέφει ένα δείκτη (ακέραιο) στον πίνακα. Μια καλή συνάρτηση κατακερματισμού διασφαλίζει ομοιόμορφη κατανομή των κλειδιών στον πίνακα, ελαχιστοποιώντας τις συγκρούσεις.
3. Μηχανισμός διαχείρισης συγκρούσεων: Μέθοδος για την επίλυση της κατάστασης όταν η συνάρτηση κατακερματισμού παράγει τον ίδιο δείκτη για διαφορετικά κλειδιά. Δύο κύριες μέθοδοι:
   • Αποσύνδεση (Separate Chaining): Κάθε στοιχείο του πίνακα διατηρεί έναν δείκτη σε μια λίστα (συνδεδεμένη λίστα, δέντρο B κ.ά.) στοιχείων που έχουν κατακερματιστεί σε αυτόν τον δείκτη.
   • Ανοιχτή διεύθυνση (Open Addressing): Σε περίπτωση σύγκρουσης, αναζητείται άλλη ελεύθερη θέση στον ίδιο τον πίνακα για την τοποθέτηση του στοιχείου. Στρατηγικές αναζήτησης:
     • Γραμμική αναζήτηση (Linear Probing)
     • Τετραγωνική αναζήτηση (Quadratic Probing)
     • Διπλό κατακερματισμό (Double Hashing)
4. Ενέργειες: Υλοποίηση των βασικών ενεργειών: εισαγωγή (insert), αναζήτηση (search), διαγραφή (delete). Αυτές οι ενέργειες χρησιμοποιούν τη συνάρτηση κατακερματισμού για τον προσδιορισμό της θέσης των στοιχείων στον πίνακα και τον μηχανισμό διαχείρισης συγκρούσεων αν χρειάζεται.