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

Ένα πίνακας κατακερματισμού αποτελείται από έναν σταθερού μεγέθους πίνακα (κουβά ή θέση) και μια συνάρτηση κατακερματισμού.

• Πίνακας (Κουβάδες/Θέσεις): Αντιπροσωπεύει μια ακολουθία κελιών όπου αποθηκεύονται ζεύγη "κλειδί-τιμή". Το μέγεθος του πίνακα καθορίζει τον αριθμό των πιθανών θέσεων για την αποθήκευση στοιχείων.

• Συνάρτηση κατακερματισμού: Μετατρέπει το κλειδί σε μια ακέραια τιμή (κωδικό κατακερματισμού), η οποία χρησιμοποιείται για τον προσδιορισμό του δείκτη του κελιού στον πίνακα (κουβά), όπου θα αποθηκευτεί ή θα εξαχθεί η αντίστοιχη τιμή.

Επιπλέον, μπορεί να υπάρχει:

• Στρατηγική επίλυσης συγκρούσεων: Μηχανισμός για τη διαχείριση καταστάσεων όπου διαφορετικά κλειδιά παράγουν τον ίδιο κωδικό κατακερματισμού και δείχνουν στο ίδιο κελί του πίνακα. Συνηθισμένες στρατηγικές:
  • Αλυσίδωση (Separate Chaining): Κάθε κελί του πίνακα αποθηκεύει έναν δείκτη σε μια συνδεδεμένη λίστα (ή άλλη δομή δεδομένων), που περιέχει όλα τα ζεύγη "κλειδί-τιμή" των οποίων οι κωδικοί κατακερματισμού δείχνουν σε αυτό το κελί.
  • Ανοιχτός προσδιορισμός (Open Addressing): Σε περίπτωση σύγκρουσης, αναζητείται ένα ελεύθερο κελί στον πίνακα σύμφωνα με έναν καθορισμένο κανόνα (π.χ. γραμμική ή τετραγωνική αναζήτηση).