[NOISE].
Πριν από την κατάδυση σε πίνακες κατακερματισμού, ας
πρώτα μια ανασκόπηση των πλεονεκτημάτων και μειονεκτημάτων κάποιων
απλούστερες δομές δεδομένων, ξεκινώντας με
συστοιχίες.
Υπενθυμίζουμε ότι οι πίνακες που μας επιτρέπουν να αποθηκεύσετε
στοιχεία ενός μόνο τύπου δεδομένων
συνεχόμενα στη μνήμη.
, Διότι κάθε στοιχείο συνδέεται με
ένα δείκτη, ή τοποθεσία,
έχουμε τυχαία πρόσβαση σε όλες τις
στοιχεία σε μια σειρά.
Με άλλα λόγια, μπορούμε να έχουμε πρόσβαση κάθε στοιχείο
σε ένα μόνο βήμα από την ευρετηρίαση εντός της
array.
Αυτό είναι μια μεγάλη υπόθεση, διότι οι αλγόριθμοι
όπως δυαδική αναζήτηση εξαρτάται από τυχαία
πρόσβαση.
Ένα μειονέκτημα των πινάκων είναι ότι το μέγεθός τους
είναι σταθερό.
Επειδή οι πίνακες δεδομένων κατάστημα συνεχόμενα σε
μνήμης, θα πρέπει να καθορίσετε ένα μέγεθος του πίνακα
όταν δηλώνετε τη σειρά.
Μπορείτε αποτελεσματικά ζητώντας από το λειτουργικό
σύστημα να διατηρήσει την κατάλληλη ποσότητα
της μνήμης για τα στοιχεία της συστοιχίας.
Δεν υπάρχει καμία εγγύηση ότι η περισσότερη μνήμη,
δίπλα στην σειρά σας, θα είναι διαθέσιμο
για χρήση αργότερα.
Έτσι, οι πίνακες δεν είναι εύκολα μπορεί να αναπτυχθεί.
Υπενθυμίζουμε ότι μάθαμε επίσης σχετικά με τα συνδεδεμένα
λίστες, οι οποίες μπορούν να αναπτυχθούν, επειδή τους
στοιχεία δεν είναι όμορες στη μνήμη.
Κάθε κόμβος σε ένα συνδεδεμένο λίστα περιέχει το
στοιχείο που θέλουμε να αποθηκεύουν, καθώς
ένας δείκτης προς τη μεταγενέστερη στοιχείο
ο κατάλογος.
Δυστυχώς, η τιμή που έχετε πληρώσει για
δυναμική μέγεθος είναι τυχαία πρόσβαση σε
στοιχεία.
Για να αποκτήσετε πρόσβαση σε ένα συγκεκριμένο στοιχείο,
είναι απαραίτητο να διασχίσει ολόκληρο
κατάλογο έως ότου η επιθυμητή στοιχείο είναι
επιτευχθεί.
Έτσι, αν ψάχνω για τον αριθμό 9, είχα
ακολουθούν τις υποδείξεις από κόμβο σε κόμβο,
ελέγχοντας αν η τιμή του κάθε κόμβου
είναι ίσο με 9.
Ως εκ τούτου, στη χειρότερη περίπτωση, κοιτάζω προς τα πάνω είναι
O (n), η οποία είναι μακριά από την αποτελεσματική.
Μπορούμε να το κάνουμε καλύτερα από O (n), ενώ εξακολουθεί να
επιτρέποντας δομή δεδομένων μας για να αυξηθεί με την πάροδο
χρόνο;
Hash πίνακες προσφέρουν μια λύση.
Hash πίνακες χρησιμοποιούνται όταν ταχεία
εισαγωγή, διαγραφή και αναζήτηση των
στοιχεία είναι η προτεραιότητα.
Στη θεωρία, εισαγωγή, διαγραφή και αναζήτηση
μπορεί να επιτευχθεί ακόμη και σε συνεχή
χρόνο.
Έτσι, τι είναι ένας πίνακας κατακερματισμού ούτως ή άλλως;
Ένας πίνακας κατακερματισμού είναι απλά ένας πίνακας σε συνδυασμό
με μια λειτουργία, η οποία θα καλέσει το hash
λειτουργία.
Η συνάρτηση hash παίρνει ένα κομμάτι των δεδομένων
ως πρώτη ύλη, θα ονομάσουμε αυτό το κλειδί, και
εξάγει έναν ακέραιο, που συνήθως αναφέρονται
ως τιμή κατακερματισμού.
Η τιμή κατακερματισμού χάρτες κλειδί για την α
συγκεκριμένο δείκτη στον πίνακα κατακερματισμού.
Θα ήθελα αρχικά να χρησιμοποιήσετε τη συνάρτηση κατακερματισμού
προσδιοριστεί ο τόπος όπου στον πίνακα κατακερματισμού για να
αποθήκευση ενός δεδομένου κλειδί.
Αργότερα, θα χρησιμοποιούσατε την ίδια συνάρτηση κατακερματισμού
για να προσδιοριστεί ο τόπος όπου στον πίνακα κατακερματισμού για να
αναζήτηση για ένα συγκεκριμένο κλειδί.
Για το λόγο αυτό, είναι σημαντικό ότι ένα hash
λειτουργία συμπεριφέρεται με συνέπεια και εξόδους
η ίδια τιμή κατακερματισμού για όμοια κλειδιά.
Να ξέρετε ότι πίνακες κατακερματισμού μπορεί να χρησιμοποιηθεί για να
αποθηκεύουν τα δεδομένα όλων των τύπων.
Αλλά για να απλοποιήσει τα πράγματα, θα επικεντρωθεί στην
χορδές για τώρα.
Εδώ είναι μια απλή συνάρτηση κατακερματισμού για έγχορδα.
Αυτή η συνάρτηση κατακερματισμού υπολογίζει ένα hash
λειτουργία με βάση το πρώτο γράμμα του
κλειδί.
"Μήλο" αρχίζει με το γράμμα «Α», γι 'αυτό είναι
αντιστοιχίζονται με δείκτη 0 στον πίνακα κατακερματισμού.
Ομοίως, "μπανάνα" αντιστοιχίζεται στο δείκτη 1,
και «γάτα» αντιστοιχίζεται στο δείκτη 2.
Εάν ένας φίλος ρωτάει αν η λέξη "dog" είναι
ο πίνακας, θα εισόδου "σκύλος" στο hash
λειτουργία, η οποία θα βγάζει μια τιμή κατακερματισμού
3.
Από το "σκύλος" δεν αποθηκεύεται στο δείκτη 3, θα
μπορούμε να πούμε με σιγουριά ότι "σκύλος" δεν είναι
στον πίνακα,
ακόμα κι αν έχουμε ελέγχεται μόνο από το
hash 26 δείκτες του πίνακα.
Ώρα να ρίξει ένα γαλλικό κλειδί στα πράγματα.
Τι γίνεται αν θέλουμε να αποθηκεύσουμε "μυρμήγκι" στο πεδίο
τραπέζι, καθώς;
"Ant" hashes στο δείκτη 0, όπως ακριβώς «μήλο» έκανε.
Αυτό είναι ένα παράδειγμα μιας σύγκρουσης, το
αποτέλεσμα δύο κλειδιά κατακερματισμού στον ίδιο
δείκτη.
Ακόμη και αν πίνακα κατακερματισμού σας είναι μεγαλύτερη από ό, τι
σύνολο των δεδομένων σας, και έχετε επιλέξει ένα καλό
hash λειτουργία,
θα πρέπει ακόμα ένα σχέδιο για την αντιμετώπιση
συγκρούσεις, εάν και όταν αυτά προκύψουν.
Ας συζητήσουμε τα πλεονεκτήματα και τα μειονεκτήματα των δύο
κοινών μεθόδων για την επίλυση των συγκρούσεων
γραμμική ανίχνευση και Ξεχωριστές αλυσίδες.
Με γραμμική ανίχνευση, εάν ένα βασικό hashes να
ο ίδιος δείκτης όπως προηγουμένως αποθηκευμένο
κλειδί, εκχωρείται το επόμενο διαθέσιμο
σχισμή στον πίνακα.
Έτσι, "μυρμήγκι" είναι πλέον αποθηκευμένα στον δείκτη 3, δεδομένου
δείκτες 0, 1, και 2 ήταν ήδη σε χρήση.
Και αν προσπαθήσουμε να αποθηκεύσει μια τρίτη λέξη που
ξεκινά με το γράμμα "Α", είναι ανατεθεί
στο δείκτη 4, δεδομένου ότι οι δείκτες 0, 1, 2, και 3
είναι πλήρης.
Όπως μπορείτε να δείτε ακόμη και από αυτό το απλό
παράδειγμα, μόλις συμβεί μια σύγκρουση, μπορείτε
αυξήσει σημαντικά τις πιθανότητες ότι
άλλη σύγκρουση θα συμβεί στην ίδια
περιοχή.
Αυτό ονομάζεται ομαδοποίηση, και αυτό είναι ένα
σοβαρό μειονέκτημα στη γραμμική σχολαστικά.
Επιπλέον, στη χειρότερη περίπτωση εισαγωγής, διαγραφής,
και οι χρόνοι αναζήτησης έχουν ανατεθεί σε O (n),
ως το επόμενο διαθέσιμο slot θα μπορούσε να έχει
δυνητικά ήταν η τελευταία εγκοπή στον πίνακα.
Ίσως Ξεχωριστές αλυσίδες θα προσφέρει μια πιο
επιτακτική λύση.
Στο ξεχωριστό μοντέλο της αλυσιδωτής εκτέλεσης, το hash
πίνακας είναι στην πραγματικότητα μια σειρά από δείκτες σε
συνδεδεμένες λίστες.
Όταν συμβεί μια σύγκρουση, το κλειδί μπορεί να είναι
εισάγεται σε σταθερό χρόνο στο κεφάλι του
η κατάλληλη συνδεδεμένη λίστα.
Τι συμβαίνει τώρα όταν ψάχνουμε για το "μήλο"
στον πίνακα κατακερματισμού;
Στη χειρότερη περίπτωση, θα πρέπει να διασχίσει το
ολόκληρη η συνδεδεμένη λίστα, ξεκινώντας από το δείκτη 0.
Ο χρόνος αναζήτησης χειρότερης περίπτωσης για ένα hash
πίνακα που χρησιμοποιεί ξεχωριστά αλυσοποίησης είναι
Ως εκ τούτου, O (n / k), όπου k είναι ο
το μέγεθος του πίνακα κατακερματισμού.
Περιμένετε ένα δεύτερο, k είναι μια σταθερά.
Έτσι O (n / k) είναι πραγματικά μόνο O (n),
η οποία ήταν η χειρότερη περίπτωση χρόνο αναζήτησης για
μια συνδεδεμένη λίστα.
Έχουμε πραγματικά περάσει από όλα τα
πρόβλημα της μάθησης για τους πίνακες κατακερματισμού
για να καταλήξει πίσω εκεί που ξεκινήσαμε;
Αυτό μπορεί να συμβεί από μια θεωρητική
προοπτική, αλλά στον πραγματικό κόσμο,
O (n / k) θα μπορούσε να είναι μια τεράστια βελτίωση σε σχέση με
O (n).
Σκεφτείτε το αυτό τον τρόπο: υποθέσουμε ότι k είναι
10 - θα προτιμούσατε να περιμένετε 100 δευτερόλεπτα
ή 100 / k;
10 δευτερόλεπτα από το Microsoft Word για να ολοκληρώσετε
ορθογραφικό έλεγχο του εγγράφου σας.
Όπως μόλις είδατε, την επίλυση συγκρούσεων
συνεπάγεται ένα είδος γραμμικής αναζήτησης ή
άλλη, η οποία επιβραδύνει τα πράγματα
σημαντικά.
Ως εκ τούτου, θα θελήσετε να επιλέξετε μια hash
λειτουργία που ελαχιστοποιεί την πιθανότητα
συγκρούσεις συμβαίνουν στην πρώτη θέση.
Εδώ είναι μερικές ιδιότητες του καλού hash
λειτουργίες που πρέπει να θυμάστε.
Μια καλή συνάρτηση κατακερματισμού πρέπει να κάνουν χρήση των
όλες τις πληροφορίες που παρέχονται από ένα συγκεκριμένο κλειδί
προκειμένου να μεγιστοποιηθεί ο αριθμός των
πιθανές τιμές hash.
Για παράδειγμα, αν είχαμε δύο χορδές, "cat"
και «κάμπια», θα θέλαμε να hash
σε διαφορετικές θέσεις στο τραπέζι.
Αν μια συνάρτηση κατακερματισμού έλαβε υπόψη μόνο
το πρώτο ένα, δύο, ή ακόμα και τρία γράμματα
των χορδών, μια σύγκρουση θα συμβεί,
δεδομένου ότι και οι δύο λέξεις αρχίζουν με το ίδιο
τρία γράμματα.
Τιμές κατακερματισμού πρέπει να κατανέμεται ομοιόμορφα
πέρα από τον πίνακα κατακερματισμού.
Αυτό θα μειώσει το μήκος της που συνδέονται
κατάλογοι θα πρέπει να συμβεί συγκρούσεις.
Είναι επίσης ένα καλό σημάδι, αν η τιμή κατακερματισμού σας
είναι σε θέση να παράγει πολύ διαφορετικές
hash τιμές για παρόμοιες κλειδιά,
καθιστώντας συγκρούσεις πολύ λιγότερο πιθανό.
Στόχος μας είναι η ταχεία εισαγωγή, διαγραφή,
και αναζήτησης.
Η συνάρτηση κατακερματισμού διαδραματίζει έναν κρίσιμο ρόλο στην
κάθε μία από αυτές τις διαδικασίες και θα είναι
καλείται πολύ συχνά.
Ως εκ τούτου, βεβαιωθείτε ότι απασχολεί μόνο πολύ
απλές, γρήγορες ενέργειες για την ελαχιστοποίηση κίνηση
χρόνο.
Ελπίζω ότι έχετε απολαύσει αυτό το σύντομο
εισαγωγή στον hash πίνακες.
Το όνομά μου είναι Lauren, και αυτό είναι CS50.