Έννοιες κατακερματισμού


Εισαγωγή

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

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

Το παραπάνω διάγραμμα απεικονίζει διεύθυνση μπλοκ δεδομένων ίδια με την τιμή πρωτεύοντος κλειδιού. Αυτή η συνάρτηση κατακερματισμού μπορεί επίσης να είναι απλή μαθηματική συνάρτηση όπως mod, sin, cos, εκθετική κ.λπ. Φανταστείτε ότι έχουμε συνάρτηση hash ως mod (5) για να προσδιορίσουμε τη διεύθυνση του μπλοκ δεδομένων. Τι συμβαίνει λοιπόν στην παραπάνω περίπτωση; Εφαρμόζει mod (5) σε πρωτεύοντα κλειδιά και παράγει 3,3,1,4 και 2 αντίστοιχα και οι εγγραφές αποθηκεύονται σε αυτές τις διευθύνσεις μπλοκ δεδομένων.

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

Υπάρχουν δύο τύποι οργανώσεων κατακερματισμού αρχείων - Στατικός Δυναμικός Κατακερματισμός.

Στατικό κατακερματισμό

Σε αυτήν τη μέθοδο κατακερματισμού, η προκύπτουσα διεύθυνση κάδου δεδομένων θα είναι πάντα ίδια. Αυτό σημαίνει, εάν θέλουμε να δημιουργήσουμε διεύθυνση για EMP_ID = 103 χρησιμοποιώντας τη συνάρτηση κατακερματισμού mod (5), οδηγεί πάντα στην ίδια διεύθυνση κάδου 3. Δεν θα υπάρξουν αλλαγές στη διεύθυνση κάδου εδώ. Ως εκ τούτου, ο αριθμός των κάδων δεδομένων στη μνήμη για αυτό το στατικό κατακερματισμό παραμένει σταθερός καθ 'όλη τη διάρκεια. Στο παράδειγμά μας, θα έχουμε πέντε κάδους δεδομένων στη μνήμη που χρησιμοποιούνται για την αποθήκευση των δεδομένων.

Αναζήτηση μιας εγγραφής

Χρησιμοποιώντας τη συνάρτηση κατακερματισμού, δημιουργείται διεύθυνση κάδου δεδομένων για το κλειδί κατακερματισμού. Στη συνέχεια, η εγγραφή ανακτάται από αυτήν τη θέση. δηλ. αν θέλουμε να ανακτήσουμε ολόκληρη την εγγραφή για το ID 104, και αν η συνάρτηση κατακερματισμού είναι mod (5) στο ID, η διεύθυνση που θα δημιουργηθεί θα ήταν 4. Στη συνέχεια, θα φτάσουμε απευθείας στη διεύθυνση 4 και θα ανακτήσουμε ολόκληρη την εγγραφή για το ID 104. Εδώ ID ενεργεί ως κλειδί κατακερματισμού.

Εισαγωγή εγγραφής

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

Διαγράψτε μια εγγραφή

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

Ενημέρωση εγγραφής

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

 

Ας υποθέσουμε ότι πρέπει να εισαγάγουμε κάποιες εγγραφές στο αρχείο. Αλλά η διεύθυνση κάδου δεδομένων που δημιουργείται από τη συνάρτηση κατακερματισμού είναι πλήρης ή τα δεδομένα υπάρχουν ήδη σε αυτήν τη διεύθυνση. Πώς εισάγουμε τα δεδομένα; Αυτή η κατάσταση στο στατικό κατακερματισμό ονομάζεται υπερχείλιση κουβά. Αυτή είναι μια από τις κρίσιμες καταστάσεις / μειονέκτημα αυτής της μεθόδου. Πού θα αποθηκεύσουμε τα δεδομένα σε αυτήν την περίπτωση; Δεν μπορούμε να χάσουμε τα δεδομένα. Υπάρχουν διάφορες μέθοδοι για να ξεπεραστεί αυτή η κατάσταση. Οι πιο συχνά χρησιμοποιούμενες μέθοδοι παρατίθενται παρακάτω:

Κλειστό κατακερματισμό

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

Σκεφτείτε ότι πρέπει να εισάγουμε μια νέα εγγραφή R2 στους πίνακες. Η στατική συνάρτηση κατακερματισμού δημιουργεί τη διεύθυνση κάδου δεδομένων ως «AACDBF». Αλλά αυτός ο κάδος είναι γεμάτος για την αποθήκευση των νέων δεδομένων. Αυτό που γίνεται σε αυτήν την περίπτωση είναι ένας νέος κάδος δεδομένων που προστίθεται στο τέλος του κάδου δεδομένων "AACDBF" και συνδέεται με αυτόν. Στη συνέχεια εισάγεται νέα εγγραφή R2 στον νέο κάδο. Έτσι διατηρεί τη στατική διεύθυνση κατακερματισμού. Μπορεί να προσθέσει οποιονδήποτε αριθμό νέων κάδων δεδομένων, όταν είναι γεμάτος.

Άνοιγμα κατακερματισμού

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

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

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

Τετραγωνική ανίχνευση

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

Διπλό κατακερματισμό

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

Δυναμική κατακερματισμός

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

Σκεφτείτε ότι υπάρχουν τρεις εγγραφές R1, R2 και R4 στον πίνακα. Αυτές οι εγγραφές δημιουργούν διευθύνσεις 100100, 010110 και 110110 αντίστοιχα. Αυτή η μέθοδος αποθήκευσης λαμβάνει υπόψη μόνο μέρος αυτής της διεύθυνσης - ειδικά μόνο το πρώτο bit για την αποθήκευση των δεδομένων. Έτσι προσπαθεί να φορτώσει τρία από αυτά στη διεύθυνση 0 και 1.

Τι θα συμβεί στο R3 εδώ; Δεν υπάρχει χώρος για κουβά για R3. Ο κάδος πρέπει να αναπτυχθεί δυναμικά για να φιλοξενήσει το R3. Έτσι αλλάζει η διεύθυνση να έχει 2 bit αντί για 1 bit και στη συνέχεια ενημερώνει τα υπάρχοντα δεδομένα για να έχει διεύθυνση 2 bit. Στη συνέχεια προσπαθεί να φιλοξενήσει το R3.

Τώρα μπορούμε να δούμε ότι η διεύθυνση των R1 και R2 αλλάζει για να αντικατοπτρίζει τη νέα διεύθυνση και R3 έχει εισαχθεί επίσης. Καθώς το μέγεθος των δεδομένων αυξάνεται, προσπαθεί να εισαγάγει στους υπάρχοντες κάδους. Εάν δεν υπάρχουν διαθέσιμοι κάδοι, ο αριθμός των bit αυξάνεται για να εξετάσει τη μεγαλύτερη διεύθυνση και, συνεπώς, την αύξηση των κάδων. Εάν διαγράψουμε οποιαδήποτε εγγραφή και αν τα δεδομένα μπορούν να αποθηκευτούν με λιγότερους κάδους, μειώνεται το μέγεθος του κάδου. Κάνει το αντίθετο από αυτό που έχουμε δει παραπάνω. Έτσι λειτουργεί μια δυναμική κατακερματισμό. Αρχικά μόνο μερικό ευρετήριο / διεύθυνση που δημιουργείται από τη συνάρτηση κατακερματισμού θεωρείται ότι αποθηκεύει τα δεδομένα. Καθώς ο αριθμός των δεδομένων αυξάνεται και υπάρχει ανάγκη για περισσότερους κάδους, μεγαλύτερο μέρος του ευρετηρίου θεωρείται ότι αποθηκεύει τα δεδομένα.

Πλεονεκτήματα της δυναμικής κατακερματισμού

  • Η απόδοση δεν μειώνεται καθώς τα δεδομένα αυξάνονται στο σύστημα. Αυξάνει απλώς το μέγεθος της μνήμης για να χωρέσει τα δεδομένα.
  • Δεδομένου ότι μεγαλώνει και συρρικνώνεται με τα δεδομένα, η μνήμη χρησιμοποιείται καλά. Δεν θα υπάρχει ψευδή μνήμη που δεν χρησιμοποιείται.
  • Καλό για δυναμικές βάσεις δεδομένων όπου τα δεδομένα αυξάνονται και συρρικνώνονται συχνά.

 

Μειονεκτήματα της δυναμικής κατακερματισμού

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

Σύγκριση της ταξινομημένης ευρετηρίασης και κατακερματισμού

Ταξινόμηση ευρετηρίου

Hashing

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

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

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

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

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