Πίνακας κατακερματισμού — Πώς λειτουργεί το hashing και η επίλυση συγκρούσεων

Ένας πίνακας κατακερματισμού αποθηκεύει ζεύγη κλειδιού-τιμής εφαρμόζοντας κατακερματισμό σε κάθε κλειδί ώστε να το αντιστοιχίσει σε έναν δείκτη πίνακα. Αυτό επιτρέπει στον πίνακα να πηγαίνει κοντά στη σωστή θέση αντί να ελέγχει ένα-ένα όλα τα αποθηκευμένα στοιχεία.

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

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

Ένας πίνακας κατακερματισμού αποθηκεύει ζεύγη κλειδιού-τιμής όπως "name" -> "Ada" ή 42 -> "blue". Έχει δύο βασικά μέρη:

• έναν πίνακα από θέσεις ή κάδους
• μια συνάρτηση κατακερματισμού που αντιστοιχίζει κάθε κλειδί σε μία από αυτές τις θέσεις

Αν ο πίνακας έχει $m$ θέσεις, μπορείς να σκεφτείς τη συνάρτηση κατακερματισμού ως κάτι που παράγει έναν δείκτη από $0$ έως $m-1$.

Για ένα μικρό παράδειγμα με ακεραίους, ο κανόνας μπορεί να είναι

$$h(k) = k \bmod 8$$

Τότε το κλειδί $10$ πηγαίνει στη θέση $2$, επειδή $10 \bmod 8 = 2$.

Οι πραγματικές συναρτήσεις κατακερματισμού σχεδιάζονται πιο προσεκτικά, ειδικά για συμβολοσειρές και μεγαλύτερα σύνολα δεδομένων. Όμως η βασική ιδέα μένει ίδια: υπολόγισε γρήγορα έναν δείκτη και μετά έλεγξε το στοιχείο που είναι αποθηκευμένο εκεί.

Γιατί οι συγκρούσεις κατακερματισμού είναι αναπόφευκτες

Σύγκρουση συμβαίνει όταν δύο διαφορετικά κλειδιά αντιστοιχίζονται στην ίδια θέση.

Αυτό είναι φυσιολογικό, επειδή ο πίνακας συνήθως έχει λιγότερες θέσεις από τον αριθμό των πιθανών κλειδιών. Με

$$h(k) = k \bmod 8$$

τα κλειδιά $10$, $18$ και $26$ αντιστοιχίζονται όλα στη θέση $2$. Άρα, παρόλο που η συνάρτηση λειτουργεί ακριβώς όπως ορίζεται, ο πίνακας εξακολουθεί να έχει μια σύγκρουση που πρέπει να επιλύσει.

Άρα ένας πίνακας κατακερματισμού δεν υπόσχεται μοναδική θέση για κάθε κλειδί. Υπόσχεται έναν γρήγορο τρόπο να περιορίσει την αναζήτηση, αρκεί οι συγκρούσεις να αντιμετωπίζονται σωστά.

Παράδειγμα βήμα προς βήμα: ένας πίνακας, μία σύγκρουση

Έστω ότι ένας πίνακας έχει $8$ θέσεις και χρησιμοποιεί

$$h(k) = k \bmod 8$$

Εισήγαγε τα κλειδιά $10$, $18$ και $7$.

Πρώτα, το $10$ πηγαίνει στη θέση $2$, επειδή $10 \bmod 8 = 2$.

Στη συνέχεια, το $18$ κατακερματίζεται επίσης στη θέση $2$, οπότε προκύπτει σύγκρουση.

Έπειτα, το $7$ πηγαίνει στη θέση $7$, άρα αυτή η εισαγωγή δεν συγκρούεται.

Το χρήσιμο μοτίβο είναι πάντα το ίδιο:

1. Κάνε hash το κλειδί.
2. Πήγαινε στην προτεινόμενη θέση.
3. Αν υπάρχει ήδη εκεί διαφορετικό κλειδί, εφάρμοσε τον κανόνα επίλυσης σύγκρουσης.

Μόλις αυτό το μοτίβο γίνει σαφές, οι δύο βασικές στρατηγικές επίλυσης συγκρούσεων είναι πιο εύκολο να κατανοηθούν.

Chaining έναντι open addressing

Το chaining κρατά έναν κάδο σε κάθε θέση

Στο chaining, κάθε θέση αποθηκεύει μια μικρή συλλογή από εγγραφές αντί για μία μόνο.

Αν τα $10$ και $18$ κατακερματίζονται και τα δύο στη θέση $2$, ο κάδος $2$ μπορεί να αποθηκεύει

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Για να βρει το κλειδί $18$, ο πίνακας πηγαίνει στον κάδο $2$ και συγκρίνει μόνο τις εγγραφές αυτού του κάδου.

Το chaining είναι εννοιολογικά απλό και η διαγραφή είναι συνήθως ευκολότερη από ό,τι στο open addressing. Το μειονέκτημα είναι ότι οι μεγάλοι κάδοι κάνουν τις πράξεις πιο αργές.

Το open addressing μένει μέσα στον πίνακα

Στο open addressing, κάθε θέση του πίνακα κρατά το πολύ μία εγγραφή. Αν η αρχική θέση είναι γεμάτη, ο πίνακας δοκιμάζει άλλες θέσεις σύμφωνα με έναν σταθερό κανόνα.

Ένας συνηθισμένος κανόνας είναι η γραμμική διερεύνηση: αν η θέση $2$ είναι κατειλημμένη, δοκίμασε τη $3$, μετά τη $4$, μετά τη $5$, και συνέχισε κυκλικά αν χρειαστεί.

Αυτό αποφεύγει ξεχωριστές λίστες κάδων, αλλά οι γειτονικές γεμάτες θέσεις μπορούν να σχηματίσουν συσσωματώματα. Μια ακόμη λεπτομέρεια είναι ότι η αναζήτηση και η διαγραφή πρέπει να ακολουθούν τον ίδιο κανόνα διερεύνησης που χρησιμοποιήθηκε κατά την εισαγωγή.

Πότε ο ισχυρισμός $O(1)$ είναι δίκαιος

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

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

Ο συντελεστής φόρτωσης είναι ο λόγος

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Αν ο πίνακας γεμίσει υπερβολικά, οι συγκρούσεις γίνονται συχνότερες και η απόδοση χειροτερεύει. Γι’ αυτό πολλές υλοποιήσεις αλλάζουν το μέγεθος του πίνακα καθώς γεμίζει.

Η απόδοση στη χειρότερη περίπτωση μπορεί παρ’ όλα αυτά να υποβαθμιστεί προς το $O(n)$ αν πάρα πολλά κλειδιά συσσωρευτούν στην ίδια περιοχή.

Συνηθισμένα λάθη με τους πίνακες κατακερματισμού

Να υποθέτεις ότι οι συγκρούσεις σημαίνουν πως απέτυχε η συνάρτηση κατακερματισμού

Δεν σημαίνει αυτό. Οι συγκρούσεις είναι αναμενόμενες. Το πραγματικό ερώτημα είναι αν ο πίνακας τις χειρίζεται αποδοτικά.

Να θεωρείς το $O(1)$ ως άνευ όρων

Το $O(1)$ είναι συνήθως δήλωση για τη μέση περίπτωση, όχι υπόσχεση για κάθε είσοδο και κάθε χρονική στιγμή.

Να συγχέεις το hashing εδώ με την κρυπτογράφηση

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

Να ξεχνάς να συγκρίνεις το πραγματικό κλειδί

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

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

Οι πίνακες κατακερματισμού χρησιμοποιούνται όπου έχει σημασία η γρήγορη αναζήτηση με βάση κλειδί. Συνηθισμένα παραδείγματα είναι τα λεξικά, οι πίνακες συμβόλων, οι cache, η δεικτοδότηση και η καταμέτρηση συχνοτήτων σε δεδομένα.

Είναι πολύ κατάλληλοι όταν η ακριβής αναζήτηση με βάση κλειδί είναι πιο σημαντική από το να διατηρούνται τα στοιχεία σε ταξινομημένη σειρά. Αν χρειάζεσαι διάσχιση με σειρά, ερωτήματα εύρους ή κοντινότερες τιμές, ίσως είναι προτιμότερη μια διαφορετική δομή.

Δοκίμασε ένα παρόμοιο παράδειγμα σύγκρουσης

Πάρε έναν μικρό πίνακα με $8$ θέσεις και χρησιμοποίησε $h(k)=k \bmod 8$. Εισήγαγε μερικά κλειδιά όπως $3$, $11$, $19$ και $27$. Έπειτα επίλυσε τις συγκρούσεις μία φορά με chaining και μία φορά με γραμμική διερεύνηση.

Αυτή η μία άσκηση κάνει τη βασική ιδέα πολύ γρήγορα συγκεκριμένη: οι συγκρούσεις είναι αναπόφευκτες και ο κανόνας επίλυσής τους αλλάζει τη συμπεριφορά του πίνακα. Αν θέλεις ένα χρήσιμο επόμενο βήμα, δοκίμασε τη δική σου εκδοχή με διαφορετικό μέγεθος πίνακα και δες πώς αλλάζουν οι συγκρούσεις.