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

Ο πίνακας κατακερματισμού είναι μια δομή δεδομένων που υλοποιεί έναν συσχετιστικό πίνακα (λεξικό). Αποθηκεύει ζεύγη "κλειδί-τιμή", όπου τα κλειδιά είναι μοναδικά.

Βασικές αρχές:

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

Λύση στις συγκρούσεις:

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

Χαρακτηριστικά:

• Γρήγορη πρόσβαση: Στην ιδανική περίπτωση O(1) για ενέργειες εισαγωγής, αναζήτησης και διαγραφής.
• Εξάρτηση από τη συνάρτηση κατακερματισμού: Η ποιότητα της συνάρτησης και η στρατηγική επίλυσης συγκρούσεων επηρεάζουν σημαντικά την απόδοση.
• Χρήση μνήμης: Απαιτεί επιπλέον μνήμη για τον πίνακα των καλαθιών.

Χρήση στο QA:

• Αποθήκευση δοκιμαστικών δεδομένων (κλειδί - όνομα παραμέτρου, τιμή - αναμενόμενη ή πραγματική τιμή).
• Έλεγχος μοναδικότητας στοιχείων (π.χ., ID χρηστών).
• Υλοποίηση cache.