hash table c programs implement hash table
Αυτό το σεμινάριο εξηγεί τους πίνακες κατακερματισμού C ++ και τους χάρτες κατακερματισμού. Θα μάθετε επίσης για τις εφαρμογές και την εφαρμογή Hash Table στο C ++:
Το κατακερματισμό είναι μια τεχνική με την οποία μπορούμε να αντιστοιχίσουμε μεγάλο αριθμό δεδομένων σε έναν μικρότερο πίνακα χρησιμοποιώντας μια «συνάρτηση κατακερματισμού».
Χρησιμοποιώντας την τεχνική κατακερματισμού, μπορούμε να αναζητήσουμε τα δεδομένα πιο γρήγορα και αποτελεσματικά σε σύγκριση με άλλες τεχνικές αναζήτησης όπως γραμμική και δυαδική αναζήτηση.
Ας καταλάβουμε την τεχνική κατακερματισμού με ένα παράδειγμα σε αυτό το σεμινάριο.
=> Διαβάστε το The Easy C ++ Training Series.
Τι θα μάθετε:
Κατακερματισμός στο C ++
Ας πάρουμε ένα παράδειγμα βιβλιοθήκης κολεγίου που στεγάζει χιλιάδες βιβλία. Τα βιβλία είναι διατεταγμένα σύμφωνα με θέματα, τμήματα, κ.λπ. Ωστόσο, κάθε ενότητα θα έχει πολλά βιβλία που καθιστούν έτσι δύσκολη την αναζήτηση βιβλίων.
το καλύτερο λογισμικό φωνής προς κείμενο
Έτσι, για να ξεπεράσουμε αυτήν τη δυσκολία, εκχωρούμε έναν μοναδικό αριθμό ή κλειδί σε κάθε βιβλίο, έτσι ώστε να γνωρίζουμε αμέσως τη θέση του βιβλίου. Αυτό επιτυγχάνεται πράγματι μέσω κατακερματισμού.
Συνεχίζοντας το παράδειγμα της βιβλιοθήκης μας, αντί να αναγνωρίζουμε κάθε βιβλίο με βάση το τμήμα, το θέμα, την ενότητα κ.λπ. που μπορεί να οδηγήσει σε μια πολύ μεγάλη συμβολοσειρά, υπολογίζουμε μια μοναδική ακέραια τιμή ή κλειδί για κάθε βιβλίο στη βιβλιοθήκη χρησιμοποιώντας μια μοναδική λειτουργία και αποθηκεύστε αυτά τα κλειδιά σε ξεχωριστό πίνακα.
Η μοναδική συνάρτηση που αναφέρεται παραπάνω ονομάζεται 'Συνάρτηση Hash' και ο ξεχωριστός πίνακας ονομάζεται 'Πίνακας Hash'. Μια συνάρτηση κατακερματισμού χρησιμοποιείται για την αντιστοίχιση της δεδομένης τιμής σε ένα συγκεκριμένο μοναδικό κλειδί στον Πίνακα Hash. Αυτό έχει ως αποτέλεσμα ταχύτερη πρόσβαση σε στοιχεία. Όσο πιο αποτελεσματική είναι η λειτουργία κατακερματισμού, τόσο πιο αποτελεσματική θα είναι η χαρτογράφηση κάθε στοιχείου στο μοναδικό κλειδί.
Ας εξετάσουμε μια συνάρτηση κατακερματισμού h (x) που χαρτογραφεί την τιμή ' Χ 'Στο' x% 10 Στον πίνακα. Για τα δεδομένα δεδομένα, μπορούμε να κατασκευάσουμε έναν πίνακα κατακερματισμού που περιέχει κλειδιά ή κωδικούς Hash ή κατακερματισμούς όπως φαίνεται στο παρακάτω διάγραμμα.
Στο παραπάνω διάγραμμα, μπορούμε να δούμε ότι οι καταχωρήσεις στον πίνακα αντιστοιχίζονται στις θέσεις τους στον πίνακα κατακερματισμού χρησιμοποιώντας μια συνάρτηση κατακερματισμού.
Έτσι μπορούμε να πούμε ότι ο κατακερματισμός υλοποιείται χρησιμοποιώντας δύο βήματα όπως αναφέρεται παρακάτω:
# 1) Η τιμή μετατρέπεται σε ένα μοναδικό ακέραιο κλειδί ή κατακερματισμός χρησιμοποιώντας μια συνάρτηση κατακερματισμού. Χρησιμοποιείται ως ευρετήριο για την αποθήκευση του αρχικού στοιχείου, το οποίο εμπίπτει στον πίνακα κατακερματισμού.
Στο παραπάνω διάγραμμα, η τιμή 1 στον πίνακα κατακερματισμού είναι το μοναδικό κλειδί για την αποθήκευση του στοιχείου 1 από τη συστοιχία δεδομένων που δίνεται στο LHS του διαγράμματος.
#δύο) Το στοιχείο από τη συστοιχία δεδομένων αποθηκεύεται στον πίνακα κατακερματισμού όπου μπορεί να ανακτηθεί γρήγορα χρησιμοποιώντας το κατακερματισμένο κλειδί. Στο παραπάνω διάγραμμα, είδαμε ότι έχουμε αποθηκεύσει όλα τα στοιχεία στον πίνακα κατακερματισμού αφού υπολογίσουμε τις αντίστοιχες θέσεις τους χρησιμοποιώντας μια συνάρτηση κατακερματισμού. Μπορούμε να χρησιμοποιήσουμε τις ακόλουθες εκφράσεις για να ανακτήσουμε τιμές κατακερματισμού και ευρετήριο.
hash = hash_func(key) index = hash % array_size
Λειτουργία κατακερματισμού
Αναφέραμε ήδη ότι η αποτελεσματικότητα της χαρτογράφησης εξαρτάται από την αποτελεσματικότητα της λειτουργίας κατακερματισμού που χρησιμοποιούμε.
Μια συνάρτηση κατακερματισμού πρέπει βασικά να πληροί τις ακόλουθες απαιτήσεις:
- Εύκολος υπολογισμός: Μια συνάρτηση κατακερματισμού, πρέπει να είναι εύκολο να υπολογιστεί τα μοναδικά πλήκτρα.
- Λιγότερη σύγκρουση: Όταν τα στοιχεία ισοδυναμούν με τις ίδιες βασικές τιμές, συμβαίνει σύγκρουση. Πρέπει να υπάρχουν όσο το δυνατόν ελάχιστες συγκρούσεις στη συνάρτηση κατακερματισμού που χρησιμοποιείται. Καθώς πρόκειται να συμβούν συγκρούσεις, πρέπει να χρησιμοποιήσουμε τις κατάλληλες τεχνικές επίλυσης σύγκρουσης για να φροντίσουμε τις συγκρούσεις.
- Ομοιόμορφη διανομή: Η συνάρτηση κατακερματισμού θα πρέπει να έχει ως αποτέλεσμα μια ομοιόμορφη κατανομή δεδομένων σε ολόκληρο τον πίνακα κατακερματισμού και, επομένως, να αποτρέπει την ομαδοποίηση.
Hash Πίνακας C ++
Ο πίνακας κατακερματισμού ή ένας χάρτης κατακερματισμού είναι μια δομή δεδομένων που αποθηκεύει δείκτες στα στοιχεία του αρχικού πίνακα δεδομένων.
Στο παράδειγμα της βιβλιοθήκης μας, ο πίνακας κατακερματισμού για τη βιβλιοθήκη θα περιέχει δείκτες σε καθένα από τα βιβλία της βιβλιοθήκης.
Η καταχώριση στον πίνακα κατακερματισμού διευκολύνει την αναζήτηση ενός συγκεκριμένου στοιχείου στον πίνακα.
Όπως έχει ήδη δει, ο πίνακας κατακερματισμού χρησιμοποιεί μια συνάρτηση κατακερματισμού για τον υπολογισμό του ευρετηρίου στη συστοιχία κάδων ή υποδοχών χρησιμοποιώντας την οποία μπορεί να βρεθεί η επιθυμητή τιμή.
Εξετάστε ένα άλλο παράδειγμα με τον ακόλουθο πίνακα δεδομένων:
Ας υποθέσουμε ότι έχουμε έναν πίνακα κατακερματισμού μεγέθους 10 όπως φαίνεται παρακάτω:
Τώρα ας χρησιμοποιήσουμε τη συνάρτηση κατακερματισμού που δίνεται παρακάτω.
Hash_code = Key_value % size_of_hash_table
Αυτό θα ισοδυναμεί με Hash_code = Key_value% 10
Χρησιμοποιώντας την παραπάνω συνάρτηση, χαρτογραφούμε τις βασικές τιμές στις θέσεις του πίνακα κατακερματισμού όπως φαίνεται παρακάτω.
Στοιχείο δεδομένων | Λειτουργία κατακερματισμού | Hash_code |
---|---|---|
22 | 22% 10 = 2 | δύο |
25 | 25% 10 = 5 | 5 |
27 | 27% 10 = 7 | 7 |
46 | 46% 10 = 6 | 6 |
70 | 70% 10 = 0 | 0 |
89 | 89% 10 = 9 | 9 |
31 | 31% 10 = 1 | 1 |
Χρησιμοποιώντας τον παραπάνω πίνακα, μπορούμε να αναπαραστήσουμε τον πίνακα κατακερματισμού ως εξής.
Έτσι, όταν πρέπει να αποκτήσουμε πρόσβαση σε ένα στοιχείο από τον πίνακα κατακερματισμού, θα χρειαστεί μόνο Ο (1) χρόνος για να πραγματοποιήσει την αναζήτηση.
Σύγκρουση
Υπολογίζουμε συνήθως τον κωδικό κατακερματισμού χρησιμοποιώντας τη συνάρτηση κατακερματισμού, ώστε να μπορούμε να αντιστοιχίσουμε την τιμή κλειδιού στον κωδικό κατακερματισμού στον πίνακα κατακερματισμού. Στο παραπάνω παράδειγμα της συστοιχίας δεδομένων, ας εισαγάγουμε μια τιμή 12. Σε αυτήν την περίπτωση, ο κωδικός κατακερματισμού για την τιμή κλειδιού 12 θα είναι 2. (12% 10 = 2).
Αλλά στον πίνακα κατακερματισμού, έχουμε ήδη μια αντιστοίχιση στο κλειδί-τιμή 22 για το hash_code 2 όπως φαίνεται παρακάτω:
Όπως φαίνεται παραπάνω, έχουμε τον ίδιο κωδικό κατακερματισμού για δύο τιμές, 12 και 22, δηλ. 2. Όταν μία ή περισσότερες τιμές-κλειδιά ισοδυναμούν με την ίδια θέση, οδηγεί σε σύγκρουση. Έτσι, η θέση κωδικού κατακερματισμού καταλαμβάνεται ήδη από μια τιμή κλειδιού και υπάρχει μια άλλη τιμή κλειδιού που πρέπει να τοποθετηθεί στην ίδια θέση.
Στην περίπτωση κατακερματισμού, ακόμα και αν έχουμε ένα τραπέζι κατακερματισμού πολύ μεγάλου μεγέθους, τότε πρέπει να υπάρχει σύγκρουση. Αυτό συμβαίνει επειδή βρίσκουμε μια μικρή μοναδική τιμή για ένα μεγάλο κλειδί γενικά, επομένως είναι απολύτως δυνατό για μία ή περισσότερες τιμές να έχουν τον ίδιο κωδικό κατακερματισμού ανά πάσα στιγμή.
Δεδομένου ότι μια σύγκρουση είναι αναπόφευκτη στο κατακερματισμό, πρέπει πάντα να αναζητούμε τρόπους για την πρόληψη ή την επίλυση της σύγκρουσης. Υπάρχουν διάφορες τεχνικές επίλυσης σύγκρουσης που μπορούμε να χρησιμοποιήσουμε για την επίλυση της σύγκρουσης που συμβαίνει κατά τη διάρκεια του κατακερματισμού.
Τεχνικές επίλυσης σύγκρουσης
Ακολουθούν οι τεχνικές που μπορούμε να χρησιμοποιήσουμε για την επίλυση σύγκρουσης στον πίνακα κατακερματισμού.
Ξεχωριστή αλυσίδα (Open Hashing)
Αυτή είναι η πιο κοινή τεχνική επίλυσης σύγκρουσης. Αυτό είναι επίσης γνωστό ως ανοιχτό κατακερματισμό και εφαρμόζεται χρησιμοποιώντας μια συνδεδεμένη λίστα.
μεγάλα δεδομένα ως εταιρείες παροχής υπηρεσιών
Σε ξεχωριστή τεχνική αλυσίδας, κάθε καταχώριση στον πίνακα κατακερματισμού είναι μια συνδεδεμένη λίστα. Όταν το κλειδί ταιριάζει με τον κωδικό κατακερματισμού, εισάγεται σε μια λίστα που αντιστοιχεί στον συγκεκριμένο κωδικό κατακερματισμού. Έτσι, όταν δύο πλήκτρα έχουν τον ίδιο κωδικό κατακερματισμού, τότε και οι δύο καταχωρήσεις καταχωρούνται στη συνδεδεμένη λίστα.
Για το παραπάνω παράδειγμα, η ξεχωριστή αλυσίδα παρουσιάζεται παρακάτω.
Το παραπάνω διάγραμμα αντιπροσωπεύει αλυσίδα. Εδώ χρησιμοποιούμε τη συνάρτηση mod (%). Βλέπουμε ότι όταν δύο βασικές τιμές ισοδυναμούν με τον ίδιο κωδικό κατακερματισμού, τότε συνδέουμε αυτά τα στοιχεία με αυτόν τον κωδικό κατακερματισμού χρησιμοποιώντας μια συνδεδεμένη λίστα.
Εάν τα κλειδιά κατανέμονται ομοιόμορφα σε ολόκληρο τον πίνακα κατακερματισμού, τότε το μέσο κόστος αναζήτησης του συγκεκριμένου κλειδιού εξαρτάται από τον μέσο αριθμό κλειδιών σε αυτήν τη συνδεδεμένη λίστα. Έτσι, η ξεχωριστή αλυσίδα παραμένει αποτελεσματική ακόμη και όταν υπάρχει αύξηση του αριθμού συμμετοχών από τους κουλοχέρηδες.
Η χειρότερη περίπτωση για ξεχωριστή αλυσίδα είναι όταν όλα τα πλήκτρα αντιστοιχούν στον ίδιο κωδικό κατακερματισμού και έτσι εισάγονται μόνο σε μία συνδεδεμένη λίστα. Ως εκ τούτου, πρέπει να αναζητήσουμε όλες τις καταχωρήσεις στον πίνακα κατακερματισμού και το κόστος που είναι ανάλογο με τον αριθμό των κλειδιών στον πίνακα.
Γραμμική διερεύνηση (ανοιχτή διεύθυνση / κλειστή κατακερματισμός)
Στην τεχνική ανοιχτής διευθυνσιοδότησης ή γραμμικής ανίχνευσης, όλες οι εγγραφές καταχώρησης αποθηκεύονται στον ίδιο τον πίνακα κατακερματισμού. Όταν η τιμή κλειδιού αντιστοιχεί σε έναν κωδικό κατακερματισμού και η θέση που υποδεικνύεται από τον κωδικό κατακερματισμού δεν καταλαμβάνεται, τότε η τιμή κλειδιού εισάγεται σε αυτήν τη θέση.
Εάν η θέση είναι ήδη κατειλημμένη, τότε χρησιμοποιώντας μια ακολουθία ανίχνευσης η τιμή κλειδιού εισάγεται στην επόμενη θέση η οποία δεν καταλαμβάνεται στον πίνακα κατακερματισμού.
Για γραμμική ανίχνευση, η συνάρτηση κατακερματισμού μπορεί να αλλάξει όπως φαίνεται παρακάτω:
hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Βλέπουμε ότι σε περίπτωση γραμμικής ανίχνευσης το διάστημα μεταξύ κουλοχέρηδων ή διαδοχικών ανιχνευτών είναι σταθερό, δηλαδή 1.
Στο παραπάνω διάγραμμα, το βλέπουμε στο 0ουθέση που εισάγουμε 10 χρησιμοποιώντας τη συνάρτηση hash “hash = hash% hash_tableSize”.
πώς να γίνετε δοκιμαστής προϊόντος
Τώρα το στοιχείο 70 ισοδυναμεί επίσης με τη θέση 0 στον πίνακα κατακερματισμού. Αλλά αυτή η τοποθεσία είναι ήδη κατειλημμένη. Ως εκ τούτου, χρησιμοποιώντας γραμμική ανίχνευση, θα βρούμε την επόμενη θέση που είναι 1. Καθώς αυτή η θέση είναι άδειη, τοποθετούμε το κλειδί 70 σε αυτή τη θέση όπως φαίνεται χρησιμοποιώντας ένα βέλος.
Ο προκύπτων πίνακας Hash εμφανίζεται παρακάτω.
Η γραμμική ανίχνευση μπορεί να υποφέρει από το πρόβλημα της «Πρωταρχικής Ομαδοποίησης» στο οποίο υπάρχει πιθανότητα τα συνεχόμενα κελιά να καταληφθούν και η πιθανότητα εισαγωγής ενός νέου στοιχείου μειώνεται.
Επίσης, εάν δύο στοιχεία έχουν την ίδια τιμή στην πρώτη συνάρτηση κατακερματισμού, τότε και τα δύο αυτά στοιχεία θα ακολουθήσουν την ίδια ακολουθία ανιχνευτών.
Τετραγωνική διερεύνηση
Η τετραγωνική ανίχνευση είναι η ίδια με τη γραμμική ανίχνευση με τη μόνη διαφορά να είναι το διάστημα που χρησιμοποιείται για την ανίχνευση. Όπως υποδηλώνει το όνομα, αυτή η τεχνική χρησιμοποιεί μη γραμμική ή τετραγωνική απόσταση για να καταλάβει κουλοχέρηδες όταν συμβαίνει σύγκρουση αντί για γραμμική απόσταση.
Στην τετραγωνική ανίχνευση, το διάστημα μεταξύ των αυλακώσεων υπολογίζεται προσθέτοντας μια αυθαίρετη πολυωνυμική τιμή στον ήδη κατακερματισμένο δείκτη. Αυτή η τεχνική μειώνει την πρωτογενή ομαδοποίηση σε σημαντικό βαθμό, αλλά δεν βελτιώνεται κατά τη δευτερογενή ομαδοποίηση.
Διπλό κατακερματισμό
Η τεχνική διπλού κατακερματισμού είναι παρόμοια με τη γραμμική ανίχνευση. Η μόνη διαφορά μεταξύ διπλού κατακερματισμού και γραμμικής ανίχνευσης είναι ότι στην τεχνική διπλού κατακερματισμού το διάστημα που χρησιμοποιείται για την ανίχνευση υπολογίζεται χρησιμοποιώντας δύο συναρτήσεις κατακερματισμού. Δεδομένου ότι εφαρμόζουμε τη συνάρτηση κατακερματισμού στο κλειδί το ένα μετά το άλλο, εξαλείφει την πρωτογενή ομαδοποίηση καθώς και τη δευτερεύουσα ομαδοποίηση.
Διαφορά μεταξύ αλυσίδας (Open Hashing) και Linear Probing (Open Address)
Αλυσίδα (Open Hashing) | Γραμμική διερεύνηση (ανοιχτή διεύθυνση) |
---|---|
Οι βασικές τιμές μπορούν να αποθηκευτούν έξω από τον πίνακα χρησιμοποιώντας μια ξεχωριστή συνδεδεμένη λίστα. | Οι βασικές τιμές πρέπει να αποθηκεύονται μόνο στον πίνακα. |
Ο αριθμός των στοιχείων στον πίνακα κατακερματισμού μπορεί να υπερβαίνει το μέγεθος του πίνακα κατακερματισμού. | Ο αριθμός των στοιχείων που υπάρχουν στον πίνακα κατακερματισμού δεν θα υπερβαίνει τον αριθμό των δεικτών στον πίνακα κατακερματισμού. |
Η διαγραφή είναι αποτελεσματική στην τεχνική αλυσίδας. | Η διαγραφή μπορεί να είναι δυσκίνητη. Μπορεί να αποφευχθεί εάν δεν απαιτείται. |
Δεδομένου ότι διατηρείται μια ξεχωριστή συνδεδεμένη λίστα για κάθε τοποθεσία, ο χώρος που λαμβάνεται είναι μεγάλος. | Δεδομένου ότι όλες οι καταχωρήσεις φιλοξενούνται στον ίδιο πίνακα, ο χώρος που λαμβάνεται είναι μικρότερος. |
Εφαρμογή πίνακα C ++ Hash
Μπορούμε να εφαρμόσουμε κατακερματισμό χρησιμοποιώντας πίνακες ή συνδεδεμένες λίστες για να προγραμματίσουμε τους πίνακες κατακερματισμού. Στο C ++ έχουμε επίσης ένα χαρακτηριστικό που ονομάζεται 'χασίς χάρτης' που είναι μια δομή παρόμοια με έναν πίνακα κατακερματισμού, αλλά κάθε καταχώρηση είναι ένα ζεύγος κλειδιού-τιμής. Στο C ++ ονομάζεται χασίς χάρτης ή απλά ένας χάρτης. Ο χάρτης κατακερματισμού στο C ++ είναι συνήθως μη ταξινομημένος.
Υπάρχει μια κεφαλίδα που ορίζεται στην τυπική βιβλιοθήκη προτύπων (STL) του C ++ η οποία εφαρμόζει τη λειτουργικότητα των χαρτών. Έχουμε καλύψει Χάρτες STL λεπτομερώς στο σεμινάριό μας για STL.
Η ακόλουθη εφαρμογή είναι για κατακερματισμό χρησιμοποιώντας τις συνδεδεμένες λίστες ως δομή δεδομένων για τον πίνακα κατακερματισμού. Χρησιμοποιούμε επίσης το 'Chaining' ως τεχνική επίλυσης σύγκρουσης σε αυτήν την υλοποίηση.
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list [hash_bucket]; } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable[index].push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable[index].begin(); i != hashtable[index].end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable[index].end()) hashtable[index].erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array[] = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array[0]); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array[i]); // display the Hash table cout<<'Hash table created:'< Παραγωγή:
Ο πίνακας Hash δημιουργήθηκε:
0 -> 21 -> 14
1 -> 15
δύο
3
4 -> 11
5 -> 12
6
Πίνακας κατακερματισμού μετά τη διαγραφή του κλειδιού 12:
0 -> 21 -> 14
1 -> 15
δύο
3
4 -> 11
5
6
Η έξοδος δείχνει έναν πίνακα κατακερματισμού που έχει δημιουργηθεί με μέγεθος 7. Χρησιμοποιούμε αλυσίδα για να επιλύσουμε τη σύγκρουση. Εμφανίζουμε τον πίνακα κατακερματισμού μετά τη διαγραφή ενός από τα πλήκτρα.
Εφαρμογές κατακερματισμού
# 1) Επαλήθευση κωδικών πρόσβασης: Η επαλήθευση των κωδικών πρόσβασης γίνεται συνήθως με τη χρήση κρυπτογραφικών συναρτήσεων κατακερματισμού. Όταν εισαχθεί ο κωδικός πρόσβασης, το σύστημα υπολογίζει τον κατακερματισμό του κωδικού πρόσβασης και στη συνέχεια αποστέλλεται στον διακομιστή για επαλήθευση. Στον διακομιστή, αποθηκεύονται οι τιμές κατακερματισμού των αρχικών κωδικών πρόσβασης.
# 2) Δομές δεδομένων: Διαφορετικές δομές δεδομένων όπως unordered_set και unordered_map σε C ++, λεξικά σε python ή C #, HashSet και hash map στην Java χρησιμοποιούν ζεύγος κλειδιών-τιμών όπου τα κλειδιά είναι μοναδικές τιμές. Οι τιμές μπορεί να είναι ίδιες για διαφορετικά πλήκτρα. Το κατακερματισμό χρησιμοποιείται για την εφαρμογή αυτών των δομών δεδομένων.
# 3) Ανασκόπηση μηνυμάτων: Αυτή είναι μια ακόμη εφαρμογή που χρησιμοποιεί κρυπτογραφικό κατακερματισμό. Στο σύμπλεγμα μηνυμάτων, υπολογίζουμε ένα κατακερματισμό για την αποστολή και λήψη δεδομένων ή ακόμη και τα αρχεία και τα συγκρίνουμε με τις αποθηκευμένες τιμές για να διασφαλίσουμε ότι δεν θα παραβιαστούν τα αρχεία δεδομένων. Ο πιο κοινός αλγόριθμος εδώ είναι 'SHA 256'.
# 4) Λειτουργία μεταγλωττιστή: Όταν ο μεταγλωττιστής συντάσσει ένα πρόγραμμα, οι λέξεις-κλειδιά για τη γλώσσα προγραμματισμού αποθηκεύονται διαφορετικά από τα άλλα αναγνωριστικά. Ο μεταγλωττιστής χρησιμοποιεί έναν πίνακα κατακερματισμού για την αποθήκευση αυτών των λέξεων-κλειδιών.
# 5) Ευρετηρίαση βάσης δεδομένων: Οι πίνακες Hash χρησιμοποιούνται για ευρετηρίαση βάσης δεδομένων και δομές δεδομένων βάσει δίσκου.
# 6) Συνεργατικοί πίνακες: Οι συσχετισμένοι πίνακες είναι πίνακες των οποίων οι δείκτες είναι τύπου δεδομένων εκτός από ακέραιες συμβολοσειρές ή άλλους τύπους αντικειμένων. Οι πίνακες κατακερματισμού μπορούν να χρησιμοποιηθούν για την εφαρμογή συσχετισμένων πινάκων.
συμπέρασμα
Το κατακερματισμό είναι η πιο ευρέως χρησιμοποιούμενη δομή δεδομένων καθώς χρειάζεται σταθερός χρόνος O (1) για εργασίες εισαγωγής, διαγραφής και αναζήτησης. Το κατακερματισμό εφαρμόζεται κυρίως χρησιμοποιώντας μια συνάρτηση κατακερματισμού που υπολογίζει μια μοναδική τιμή μικρότερου κλειδιού για μεγάλες καταχωρήσεις δεδομένων. Μπορούμε να εφαρμόσουμε κατακερματισμό χρησιμοποιώντας πίνακες και συνδεδεμένες λίστες.
Κάθε φορά που μία ή περισσότερες καταχωρήσεις δεδομένων ισοδυναμούν με τις ίδιες τιμές των κλειδιών, οδηγεί σε σύγκρουση. Έχουμε δει διάφορες τεχνικές ανάλυσης σύγκρουσης, όπως γραμμική ανίχνευση, αλυσίδα, κ.λπ. Έχουμε επίσης δει την εφαρμογή κατακερματισμού στο C ++.
Εν κατακλείδι, μπορούμε να πούμε ότι ο κατακερματισμός είναι μακράν η πιο αποτελεσματική δομή δεδομένων στον κόσμο του προγραμματισμού.
=> Αναζητήστε ολόκληρη τη σειρά προπόνησης C ++ εδώ.
Συνιστώμενη ανάγνωση
- Πώς να γράψετε σύνθετα σενάρια επιχειρησιακής λογικής χρησιμοποιώντας τεχνική πίνακα αποφάσεων
- Πίνακας επικύρωσης πεδίου (FVT): Τεχνική σχεδιασμού δοκιμής για επικύρωση πεδίου
- Tutorial QTP # 15 - Χρήση σημείων ελέγχου περιοχής, πίνακα και σελίδας στο QTP
- ΧΑΡΤΕΣ σε STL
- Όλα για δρομολογητές: Τύποι δρομολογητών, πίνακας δρομολόγησης και δρομολόγηση IP
- Κορυφαίες 40 καλύτερες ερωτήσεις συνέντευξης MySQL και απαντήσεις (2021 ερωτήσεις)
- Top 90 ερωτήσεις και απαντήσεις συνέντευξης SQL (ΝΕΟΤΕΡΑ)
- Εντολές προγραμμάτων Unix Utilities: Which, Man, Find Su, Sudo (Part D)