[Παίζει μουσική]
>> DOUG LLOYD: Μέχρι τώρα σας Γνωρίζουμε πολλά για τους πίνακες,
και ξέρετε πολλά για συνδεδεμένες λίστες.
Και έχουμε συζητήσει το πλεονεκτήματα και τα μειονεκτήματα, έχουμε
Συζητήθηκε ότι συνδεδεμένες λίστες μπορούν να πάρουν μεγαλύτερα και μικρότερα,
αλλά καταλαμβάνουν περισσότερο το μέγεθος.
Οι πίνακες είναι πολύ πιο εύκολο να χρήση, αλλά είναι περιοριστική, στο βαθμό
καθώς πρέπει να ορίσετε το μέγεθος της η συστοιχία στην αρχή
και στη συνέχεια να είμαστε κολλημένοι με αυτό.
>> Αλλά αυτό είναι, έχουμε λίγο πολύ εξαντλήσει όλα τα θέματα μας
για συνδεδεμένες λίστες και πίνακες.
Ή έχουμε;
Ίσως μπορούμε να κάνουμε κάτι ακόμα πιο δημιουργική.
Και αυτό το είδος της δανείζει η ιδέα ενός πίνακα κατακερματισμού.
>> Έτσι, σε έναν πίνακα κατακερματισμού θα πάμε να προσπαθήσουμε συνδυάζουν μια σειρά με μια συνδεδεμένη λίστα.
Εμείς πάμε για να πάρει τα πλεονεκτήματα της συστοιχίας, όπως τυχαία πρόσβαση,
να είναι σε θέση να πήγαινε σε συστοιχία στοιχείο 4 ή σειρά στοιχείων 8
χωρίς να χρειάζεται να επαναλάβει ολόκληρη.
Αυτό είναι αρκετά γρήγορα, σωστά;
>> Αλλά θέλουμε επίσης να έχουν τα δεδομένα μας δομή είναι σε θέση να αναπτυχθεί και να συρρικνωθεί.
Δεν χρειαζόμαστε, δεν το κάνουμε Θέλετε να περιοριστεί.
Και θέλουμε να είναι σε θέση για να προσθέσετε και να αφαιρέσετε τα πράγματα
πολύ εύκολα, η οποία αν θυμάστε, είναι πολύ σύνθετη με μία συστοιχία.
Και μπορούμε να ονομάσουμε αυτό νέο πράγμα ένα πίνακα κατακερματισμού.
>> Και αν εφαρμοστεί σωστά, είμαστε το είδος της λήψης
τα πλεονεκτήματα και των δύο στοιχείων δομές που έχετε ήδη δει,
πίνακες και συνδεδεμένες λίστες.
Η εισαγωγή μπορεί να αρχίσει να τείνουν προς θήτα 1.
Theta δεν έχουμε πραγματικά συζητηθεί, αλλά θήτα είναι μόνο η μέση περίπτωση,
τι πραγματικά πρόκειται να συμβεί.
Δεν πρόκειται πάντα για να έχουν το χειρότερο σενάριο,
και δεν είστε πάντα θα έχουν το καλύτερο σενάριο, έτσι ώστε ό, τι είναι
η μέση σενάριο;
>> Λοιπόν ένα μέσο εισαγωγής σε ένα πίνακα κατακερματισμού
μπορεί να αρχίσει να πάρει κοντά σε σταθερό χρόνο.
Και μπορεί να πάρει διαγραφή κοντά στο σταθερό χρόνο.
Και μπορεί να πάρει αναζήτησης κοντά στο σταθερό χρόνο.
That's-- δεν έχουν δεδομένων δομή ακόμη ότι μπορεί να το κάνει αυτό,
και έτσι αυτό ακούγεται ήδη σαν μια πολύ μεγάλο πράγμα.
Έχουμε πραγματικά μετριάζεται η τα μειονεκτήματα του καθενός από μόνη της.
>> Για να έχετε αυτήν την απόδοση αναβάθμιση όμως,
Πρέπει να ξανασκεφτούμε πώς θα προσθέσουμε στοιχεία στη δομή.
Συγκεκριμένα θέλουμε η ίδια τα δεδομένα για να μας πείτε
πού πρέπει να πάει στη δομή.
Και αν πρέπει στη συνέχεια να δούμε αν είναι σε η δομή, αν πρέπει να το βρείτε,
θέλουμε να εξετάσουμε τα δεδομένα και πάλι και να είναι σε θέση να αποτελεσματικά,
χρησιμοποιώντας τα στοιχεία, τυχαία πρόσβαση σε αυτό.
Απλά κοιτάζοντας το τα δεδομένα θα πρέπει να έχουμε
μια ιδέα για το πού ακριβώς είμαστε Θα το βρείτε στον πίνακα κατακερματισμού.
>> Τώρα το μειονέκτημα του κατακερματισμού πίνακα είναι ότι είναι πραγματικά
αρκετά κακό σε παραγγελία ή την ταξινόμηση δεδομένων.
Και στην πραγματικότητα, αν ξεκινήσετε να τα χρησιμοποιούν για να παραγγείλετε ή είδος
δεδομένα θα χάσετε όλα τα πλεονεκτήματα που προηγουμένως
είχε την άποψη της εισαγωγής και διαγραφής.
Ο χρόνος γίνεται πιο κοντά στο θήτα n, και έχουμε ουσιαστικά
υποχώρησε σε μια συνδεδεμένη λίστα.
Και έτσι θέλουμε μόνο να χρησιμοποιήσετε hash πίνακες, αν εμείς δεν ενδιαφερόμαστε για
εάν τα δεδομένα είναι ταξινομημένο.
Για το πλαίσιο στο οποίο θα τις χρησιμοποιείτε σε CS50
τότε μάλλον δεν με νοιάζει ότι τα δεδομένα είναι ταξινομημένο.
>> Έτσι, ένας πίνακας κατακερματισμού είναι ένας συνδυασμός από δύο διακριτά κομμάτια
με την οποία είμαστε εξοικειωμένοι.
Το πρώτο είναι μια λειτουργία, η οποία συνήθως καλούμε μια συνάρτηση κατακερματισμού.
Και ότι η λειτουργία hash πρόκειται να να επιστρέψει κάποια μη αρνητικός ακέραιος, η οποία
που συνήθως ονομάζουμε μια hashCode, εντάξει;
Το δεύτερο κομμάτι είναι μια συστοιχία, η οποία είναι ικανό να αποθηκεύει στοιχεία του τύπου που
θέλετε να τοποθετήσετε στη δομή των δεδομένων.
Θα κρατήσει μακριά στην συνδεδεμένη λίστα στοιχείο για την επιχείρηση
και μόλις αρχίσουμε με τα βασικά ενός hash πίνακα για να πάρει το κεφάλι σας γύρω από αυτό,
και στη συνέχεια θα φυσήξει ίσως το μυαλό σας λίγο όταν εμείς
συνδυάζουν πίνακες και καταλόγους σύνδεση μαζί.
>> Η βασική ιδέα αν είναι να πάρουμε κάποια δεδομένα.
Τρέχουμε ότι τα δεδομένα μέσω η συνάρτηση κατακερματισμού.
Και έτσι η επεξεργασία των δεδομένων είναι και φτύνει έναν αριθμό, εντάξει;
Και τότε με αυτόν τον αριθμό εμείς απλά την αποθήκευση των δεδομένων
θέλουμε να αποθηκεύσουμε στην συστοιχία σε αυτή τη θέση.
Έτσι, για παράδειγμα, έχουμε ίσως ο πίνακας κατακερματισμού της χορδές.
Είναι πήρε 10 στοιχεία σε αυτό, έτσι μπορούμε να χωρέσουν 10 χορδές σε αυτό.
>> Ας πούμε ότι θέλουμε να hash Ιωάννη.
Έτσι ο Ιωάννης όσο και τα δεδομένα που θέλετε να εισάγετε σε αυτό τον πίνακα hash κάπου.
Πού θα το πω;
Καλά συνήθως με ένα σειρά μέχρι τώρα πιθανώς
θα το θέσει σε θέση πίνακα 0.
Αλλά τώρα έχουμε αυτή τη νέα συνάρτηση κατακερματισμού.
>> Και ας πούμε ότι διατρέχουμε τον John μέσω αυτής της συνάρτησης κατακερματισμού
και είναι φτύσει 4.
Λοιπόν αυτό είναι όπου είμαστε πρόκειται να θέλουν να βάλουν τον Ιωάννη.
Θέλουμε να βάλουμε Ιωάννη στην θέση πίνακα 4, γιατί αν hash John again--
ας πούμε αργότερα θέλετε να αναζητήσετε και να δείτε
Γιάννης αν υπάρχει σε αυτό το hash table-- το μόνο που χρειάζεται να κάνουμε
είναι αυτό που τρέχει μέσα από το ίδιο hash λειτουργία, να πάρει τον αριθμό 4 έξω,
και να είναι σε θέση να βρείτε τον John αμέσως στη δομή των δεδομένων μας.
Αυτό είναι πολύ καλό.
>> Ας πούμε ότι το κάνουμε τώρα αυτό και πάλι, θέλουμε να hash Παύλου.
Θέλουμε ο Παύλος για να προσθέσετε σε αυτό τον πίνακα κατακερματισμού.
Ας πούμε ότι αυτή τη φορά τρέχει Ο Παύλος μέσω της συνάρτησης κατακερματισμού,
ο hashCode που δημιουργείται είναι 6.
Καλά τώρα μπορούμε να βάλουμε Παύλου στη θέση 6 συστοιχία.
Και αν πρέπει να κοιτάζω προς τα πάνω αν Ο Παύλος είναι σε αυτόν τον πίνακα κατακερματισμού,
το μόνο που χρειάζεται να κάνετε είναι να εκτελέσετε Παύλου μέσω της συνάρτησης κατακερματισμού και πάλι
και θα πάμε για να πάρει 6 πάλι.
>> Και τότε θα εξετάσουμε μόνο σε θέση πίνακα 6.
Είναι ο Παύλος εκεί;
Αν ναι, αυτός είναι στον πίνακα κατακερματισμού.
Ο Παύλος δεν είναι εκεί;
Δεν είναι στον πίνακα κατακερματισμού.
Είναι αρκετά απλό.
>> Τώρα πώς ορίζουμε μια συνάρτηση κατακερματισμού;
Καλά πραγματικά δεν υπάρχει όριο για το αριθμός των πιθανών συναρτήσεις κατακερματισμού.
Στην πραγματικότητα υπάρχει ένας αριθμός πραγματικά, πραγματικά καλοί στο διαδίκτυο.
Υπάρχει ένας αριθμός από πραγματικά, πραγματικά κακοί στο διαδίκτυο.
Είναι επίσης αρκετά εύκολο να γράψει ένα κακό.
>> Έτσι, αυτό που κάνει ένα καλό hash λειτουργία, σωστά;
Λοιπόν μια καλή συνάρτηση κατακερματισμού θα πρέπει να Χρησιμοποιούμε μόνο τα δεδομένα που κατακερματισμένο,
και όλα τα δεδομένα που κατακερματίζεται.
Γι 'αυτό και δεν θέλετε να χρησιμοποιήσετε anything-- εμείς δεν περιλαμβάνουν τίποτα
άλλο εκτός από τα δεδομένα.
Και θέλουμε να χρησιμοποιήσουμε όλα τα δεδομένα.
Δεν θέλουμε να χρησιμοποιήσετε μόνο ένα κομμάτι από αυτό, θέλουμε να χρησιμοποιήσουμε όλα αυτά.
Μια συνάρτηση κατακερματισμού θα πρέπει να επίσης να είναι οριστικός.
Τι σημαίνει αυτό?
Λοιπόν αυτό σημαίνει ότι κάθε φορά που περνούν ακριβώς το ίδιο κομμάτι δεδομένων
στη συνάρτηση κατακερματισμού που πάντα πάρετε την ίδια hashCode έξω.
Αν έχω περάσει Ιωάννη σε η hash λειτουργία βγω 4.
Θα πρέπει να είναι σε θέση να το κάνουμε αυτό 10.000 φορές και θα πάρω πάντα 4.
Έτσι, δεν τυχαίων αριθμών αποτελεσματικά μπορούν να συμμετέχουν σε hash μας tables--
συναρτήσεις hash μας.
>> Μια συνάρτηση κατακερματισμού θα πρέπει επίσης να ομοιόμορφη κατανομή των δεδομένων.
Εάν κάθε φορά που τρέχετε δεδομένων μέσω του hash λειτουργία μπορείτε να πάρετε το hashCode 0,
ότι δεν είναι πιθανώς τόσο μεγάλη, έτσι δεν είναι;
Θέλετε πιθανώς σε μεγάλες μια σειρά από κωδικούς hash.
Επίσης, τα πράγματα μπορεί να εξαπλωθεί καθ 'όλη τη τραπέζι.
Και επίσης θα ήταν μεγάλη, αν πραγματικά παρόμοια στοιχεία, όπως ο John και του Jonathan,
ίσως απλώθηκαν για να ζυγίσει διαφορετικές θέσεις στον πίνακα κατακερματισμού.
Αυτό θα ήταν ένα ωραίο πλεονέκτημα.
>> Εδώ είναι ένα παράδειγμα μιας συνάρτησης κατακερματισμού.
Έγραψα αυτό το ένα επάνω νωρίτερα.
Δεν είναι ένα ιδιαίτερα καλή λειτουργία του κατακερματισμού
για λόγους που δεν κάνουν πραγματικά φέρουν υπεισέλθω σε αυτή τη στιγμή.
Αλλά βλέπετε τι συμβαίνει εδώ;
Φαίνεται σαν να είμαστε δηλώνοντας μια μεταβλητή κάλεσε ποσό και ότι αυτό ισούται με 0.
Και τότε προφανώς κάνω κάτι εφ 'όσον strstr [ι] δεν είναι ίσο
με ανάστροφη κάθετο 0.
Τι κάνω εκεί;
>> Αυτό είναι βασικά ακριβώς ένα άλλο τρόπος εφαρμογής [? STRL?]
και την ανίχνευση όταν έχετε φθάσει στο τέλος του string.
Έτσι, δεν έχω πραγματικά να υπολογίσει το μήκος της συμβολοσειράς,
Είμαι απλά με τη χρήση όταν χτύπησα το ανάστροφη κάθετο 0 χαρακτήρας γνωρίζω
Έχω φτάσει στο τέλος του string.
Και τότε θα πάω για να κρατήσει επανάληψη μέσω αυτής της σειράς,
προσθήκη strstr [ι] για να συνοψίσω, και στη συνέχεια στο τέλος της ημέρας πρόκειται να επιστρέψει ποσό mod
HASH_MAX.
>> Βασικά όλα αυτά κατακερματισμού λειτουργία που κάνει είναι να την πρόσθεση
όλες οι τιμές ASCII του χορδή μου, και τότε είναι
επιστρέφοντας κάποια hashCode modded από HASH_MAX.
Είναι ίσως το μέγεθος της συστοιχίας μου, σωστά;
Δεν θέλω να πάρει hash κωδικούς εφόσον σειρά μου είναι μεγέθους 10,
Δεν θέλω να πάρει από τους κωδικούς hash 11, 12,
13, δεν μπορώ να βάλει τα πράγματα σε εκείνα τα σημεία της συστοιχίας,
ότι θα ήταν παράνομη.
Θα υποφέρουν σφάλμα κατάτμησης.
>> Τώρα εδώ είναι μια άλλη γρήγορη άκρη.
Γενικά είστε κατά πάσα πιθανότητα δεν πρόκειται να Θέλετε να γράψετε τη δική σας συναρτήσεις κατακερματισμού.
Είναι πραγματικά ένα κομμάτι της μια τέχνη, όχι επιστήμη.
Και υπάρχουν πολλά που πηγαίνει σε αυτά.
Το διαδίκτυο, όπως είπα, είναι πλήρης πραγματικά καλό συναρτήσεις κατακερματισμού,
και θα πρέπει να χρησιμοποιούν το διαδίκτυο για να βρείτε συναρτήσεις κατακερματισμού, γιατί είναι πραγματικά
ακριβώς το είδος της μια περιττή χάσιμο χρόνου για να δημιουργήσετε το δικό σας.
>> Μπορείτε να γράψετε απλές για τους σκοπούς της δοκιμής.
Αλλά, όταν στην πραγματικότητα πρόκειται για ξεκινήστε κατακερματισμός των δεδομένων και την αποθήκευσή του
σε έναν πίνακα κατακερματισμού είστε κατά πάσα πιθανότητα πρόκειται να θέλουν
για να χρησιμοποιήσετε κάποια λειτουργία που δημιουργήθηκε για σας, ότι υπάρχει στο διαδίκτυο.
Αν δεν το κάνετε απλά φροντίστε να αναφέρετε τις πηγές σας.
Δεν υπάρχει λόγος να λογοκλοπή τίποτα εδώ.
>> Η κοινότητα της επιστήμης των υπολογιστών είναι σίγουρα αυξάνεται, και πραγματικά τις αξίες
ανοιχτού κώδικα, και αυτό είναι πολύ σημαντικό να αναφέρετε τις πηγές σας, έτσι ώστε οι άνθρωποι
μπορούν να πάρουν για την απόδοση η εργασία που είναι
κάνει προς όφελος της κοινότητας.
Έτσι, πάντα να sure-- και όχι μόνο για hash
λειτουργίες, αλλά γενικά όταν χρησιμοποιήσετε κώδικα από μια εξωτερική πηγή,
αναφέρουν πάντα την πηγή σας.
Δώστε πίστωσης για το πρόσωπο που έκανε ορισμένες από τις εργασίες, ώστε να μην χρειάζεται να.
>> Εντάξει έτσι ας επανεξετάσουμε αυτό hash πίνακα για ένα δευτερόλεπτο.
Αυτό είναι όπου αφήσαμε μακριά αφού τοποθετηθεί
Ιωάννη και Παύλου σε αυτό τον πίνακα κατακερματισμού.
Βλέπετε ένα πρόβλημα εδώ;
Μπορείτε να δείτε δύο.
Αλλά κυρίως, να κάνετε δείτε αυτό το πιθανό πρόβλημα;
>> Τι θα συμβεί αν χασίς Ringo, και Αποδεικνύεται ότι μετά την επεξεργασία
ότι τα δεδομένα μέσω της συνάρτησης κατακερματισμού Ringo παράγεται επίσης το hashCode 6.
Έχω ήδη δεδομένα σε hashcode-- θέση πίνακα 6.
Έτσι, πρόκειται πιθανώς να είναι λίγο ένα πρόβλημα για μένα τώρα, έτσι δεν είναι;
>> Καλούμε αυτή η σύγκρουση.
Και η σύγκρουση συμβαίνει όταν δύο κομμάτια των δεδομένων που τρέχει μέσα από το ίδιο hash
λειτουργία αποδώσει το ίδιο hashCode.
Πιθανώς θα εξακολουθούν να θέλουν να πάρουν και οι δύο κομμάτια των δεδομένων στον πίνακα hash,
αλλιώς δεν θα έτρεχαν Ringo αυθαίρετα μέσω της συνάρτησης κατακερματισμού.
Εμείς προφανώς θέλουν να πάρουν Ringo σε αυτή την σειρά.
>> Πώς μπορούμε να το κάνουμε όμως, αν αυτός και ο Paul τόσο απόδοση hashCode 6;
Δεν θέλουμε να αντικαταστήσετε Παύλου, θέλουμε να είναι ο Παύλος εκεί.
Γι 'αυτό πρέπει να βρούμε έναν τρόπο για να πάρει τα στοιχεία στον πίνακα κατακερματισμού που
εξακολουθεί να διατηρεί γρήγορη μας εισαγωγής και γρήγορη ματιά πάνω.
Και ένας τρόπος για να ασχοληθεί με το θέμα είναι να κάνει κάτι που ονομάζεται γραμμική σχολαστικά.
>> Χρησιμοποιώντας αυτή τη μέθοδο, εάν έχουμε ένα σύγκρουσης, καλά, τι θα κάνουμε;
Καλά δεν μπορούμε να τον βάλουν στη θέση συστοιχία 6, ή ό, τι hashCode δημιουργήθηκε,
ας τον έβαλε σε hashCode συν 1.
Και αν αυτό είναι πλήρες ας έβαλε σε hashCode συν 2.
Το πλεονέκτημα αυτής της ύπαρξης, αν αυτός είναι δεν είναι ακριβώς εκεί που νομίζει ότι είναι,
και θα πρέπει να ξεκινήσει η αναζήτηση, Ίσως δεν έχουμε να πάμε πολύ μακριά.
Ίσως δεν έχουμε να αναζητήσετε όλα τα n στοιχεία του πίνακα κατακερματισμού.
Ίσως πρέπει να ψάξουμε ένα ζευγάρι από αυτά.
>> Και έτσι είμαστε ακόμα τείνουν προς ότι η μέση περίπτωση είναι κοντά στο 1 vs
κοντά στο n, οπότε ίσως αυτό θα λειτουργήσει.
Ας δούμε πώς αυτό θα μπορούσε να λειτουργήσει στην πραγματικότητα.
Και ας δούμε αν ίσως μπορούμε να ανιχνεύσουμε το πρόβλημα που θα μπορούσε να συμβεί εδώ.
>> Ας πούμε ότι έχουμε hash Bart.
Έτσι, τώρα θα πάμε να τρέξει ένα νέο σύνολο των χορδών μέσω της συνάρτησης κατακερματισμού,
και τρέχουμε Bart μέσω του κατακερματισμού λειτουργία, θα έχουμε hashCode 6.
Θα ρίξουμε μια ματιά, βλέπουμε 6 άδειο, έτσι μπορούμε να βάλουμε εκεί Bart.
>> Τώρα έχουμε hash Λίζα και ότι δημιουργεί επίσης hashCode 6.
Καλά τώρα που είμαστε χρησιμοποιώντας αυτό γραμμική μέθοδο ανίχνευσης που ξεκινούν από 6,
βλέπουμε ότι το 6 είναι πλήρης.
Εμείς δεν μπορούμε να βάλουμε Lisa σε 6.
Έτσι, πού πάμε;
Ας πάμε στο 7.
7 είναι άδειο, έτσι που να λειτουργεί.
Οπότε ας βάλουμε Λίζα εκεί.
>> Τώρα έχουμε hash Όμηρο και παίρνουμε 7.
Εντάξει καλά γνωρίζουμε ότι το 7 είναι πλήρης τώρα, έτσι δεν μπορούμε να βάλουμε εκεί ο Όμηρος.
Έτσι, ας πάμε σε 8.
Είναι διαθέσιμη 8;
Ναι, και έτσι αν 8, κοντά στο 7, θα πρέπει να αρχίσει να ψάχνει είμαστε
Δεν πρόκειται να πρέπει να πάει πολύ μακριά.
Και έτσι ας βάλουμε Ομήρου 8.
>> Τώρα έχουμε hash Μάγκι και 3 επιστρέφει, δόξα τω Θεώ
είμαστε σε θέση να τεθεί μόνο Μάγκι εκεί.
Δεν έχουμε να κάνουμε οποιοδήποτε είδος σχολαστικά για αυτό.
Τώρα έχουμε hash Μαρτζ, και Marge επιστρέφει επίσης 6.
>> Λοιπόν 6 είναι πλήρης, 7 είναι πλήρης, 8 είναι πλήρης, 9, εντάξει δόξα τω Θεώ, 9 είναι άδειο.
Μπορώ να βάλω Marge στο 9.
Ήδη μπορούμε να δούμε ότι αρχίζουμε να έχουν αυτό το πρόβλημα, όπου τώρα είμαστε
αρχίζουν να τεντώσει τα πράγματα είδος του μακριά από τους κώδικες hash τους.
Και αυτό θήτα του 1, ότι η μέση περίπτωση να είναι σταθερά χρόνου,
έχει αρχίσει να πάρετε μια μικρή more-- αρχίζουν να τείνουν λίγο περισσότερο
προς θήτα του ν.
Αρχίζουμε να χάσει ότι πλεονέκτημα των πινάκων κατακερματισμού.
>> Αυτό το πρόβλημα που μόλις είδατε Είναι κάτι που ονομάζεται ομαδοποίηση.
Και τι είναι πραγματικά κακό για ομαδοποίησης είναι ότι μόλις τώρα
έχουν δύο στοιχεία που βρίσκονται δίπλα- πλευρά καθιστά ακόμη πιο πιθανό,
έχετε το διπλό ευκαιρία, που θα πάμε
να έχουμε μια άλλη σύγκρουση με το εν λόγω σύμπλεγμα,
και το σύμπλεγμα θα αυξηθεί κατά μία μονάδα.
Και θα συνεχίσει να αυξάνεται και αυξάνεται πιθανότητα σας να έχουν μια σύγκρουση.
Και τελικά αυτό είναι εξίσου κακό ως μη διαλογή των δεδομένων σε όλα.
>> Το άλλο πρόβλημα είναι αν και ακόμη, και μέχρι στιγμής μέχρι αυτό το σημείο,
έχουμε μόλις το είδος του την κατανόηση του τι ένας πίνακας κατακερματισμού,
εξακολουθούμε να έχουμε μόνο δωματίου για 10 έγχορδα.
Αν θέλουμε να συνεχίσουμε να hash οι πολίτες του Σπρίνγκφιλντ,
μπορούμε να πάρουμε μόνο 10 από αυτούς εκεί.
Και αν προσπαθήσουμε και πρόσθεσε ένα 11ο ή 12ο, δεν έχουμε ένα μέρος για να τους βάλει.
Θα μπορούσαμε απλά να περιστρέφεται γύρω από το κύκλοι προσπαθούν να βρουν ένα κενό σημείο,
και ίσως να κολλήσουν σε ένα άπειρο βρόχο.
>> Έτσι, αυτό το είδος του προσφέρεται για την ιδέα κάτι που ονομάζεται αλυσιδωτή σύνδεση.
Και αυτό είναι που θα πάμε να φέρει συνδεδεμένες λίστες πίσω στην εικόνα.
Τι θα συμβεί αν αντί για την αποθήκευση μόνο τα ίδια τα δεδομένα του πίνακα,
κάθε στοιχείο του πίνακα θα μπορούσε να κατέχει πολλά κομμάτια των δεδομένων;
Καλά αυτό δεν έχει νόημα, σωστά;
Γνωρίζουμε ότι ένας πίνακας μπορεί μόνο να hold-- κάθε στοιχείο ενός πίνακα
μπορεί να κρατήσει μόνο ένα κομμάτι των δεδομένων αυτού του τύπου δεδομένων.
>> Τι γίνεται όμως αν αυτός ο τύπος δεδομένων είναι μια συνδεδεμένη λίστα, σωστά;
Έτσι τι εάν κάθε στοιχείο του πίνακα ήταν
ένας δείκτης για το κεφάλι του μία συνδεδεμένη λίστα;
Και τότε θα μπορούσαμε να οικοδομήσουμε οι εν λόγω συνδεδεμένες λίστες
και να αναπτυχθούν αυθαίρετα, γιατί συνδεδεμένες λίστες επιτρέπουν
μας να αναπτυχθεί και να συρρικνωθεί πολύ περισσότερο ευέλικτα από ό, τι ένας πίνακας κάνει.
Τι κι αν χρησιμοποιούμε τώρα, αξιοποιούμε αυτό, σωστά;
Αρχίζουμε να μεγαλώσουν αυτά τα αλυσίδες έξω από αυτές τις θέσεις πίνακα.
>> Τώρα μπορούμε να χωρέσει έναν άπειρο ποσότητα των δεδομένων, ή όχι άπειρη,
μια αυθαίρετη ποσότητα δεδομένα, σε πίνακα κατακερματισμού μας
χωρίς ποτέ να τρέχει σε το πρόβλημα της σύγκρουσης.
Έχουμε, επίσης απαλείφονται, ομαδοποίηση με τον τρόπο αυτό.
Και καλά γνωρίζουμε ότι όταν εισάγουμε σε μια συνδεδεμένη λίστα, αν θυμάστε
από το βίντεο για συνδεδεμένες λίστες, μεμονωμένα συνδεδεμένες λίστες και διπλά συνδεδεμένες λίστες,
είναι μια διαρκής λειτουργία του χρόνου.
Είμαστε προσθέτοντας απλώς προς τα εμπρός.
>> Και για το βλέμμα επάνω, αλλά ξέρουμε ότι κοιτάζω προς τα πάνω σε μια συνδεδεμένη λίστα
μπορεί να είναι ένα πρόβλημα, σωστά;
Πρέπει να ψάξετε μέσα αυτό από την αρχή μέχρι το τέλος.
Δεν υπάρχει καμία τυχαία πρόσβαση σε μία συνδεδεμένη λίστα.
Αλλά εάν αντί να έχουν ένα συνδεδεμένο κατάλογο όπου η αναζήτηση θα είναι O Ν,
τώρα έχουμε 10 συνδεδεμένες λίστες, ή 1.000 συνδεδεμένες λίστες,
τώρα είναι O Ν διαιρούμενο με το 10, ή O Ν διαιρείται με 1.000.
>> Και ενώ μιλούσαμε θεωρητικά σχετικά με την πολυπλοκότητα
αγνοήσουμε σταθερές, στον πραγματικό κόσμο αυτά τα πράγματα στην πραγματικότητα σημασία,
έτσι δεν είναι;
Στην πραγματικότητα, θα παρατηρήσετε ότι αυτό συμβαίνει
να τρέχει 10 φορές γρηγορότερα, ή 1.000 φορές πιο γρήγορα,
επειδή είμαστε διανέμουν ένα μακρύ αλυσίδας σε όλη 1.000 μικρότερες αλυσίδες.
Και έτσι κάθε φορά που θα πρέπει να αναζητήσετε μέσω ενός από αυτές τις αλυσίδες μπορούμε
αγνοούν τις αλυσίδες 999 δεν με νοιάζει περίπου, και μόλις κάνετε το ένα.
>> Ποια είναι κατά μέσο όρο να είναι 1.000 φορές μικρότερη.
Και έτσι είμαστε ακόμα είδος τείνει προς το μέσο όρο υπόθεση
του είναι σταθερή χρόνου, αλλά μόνο και μόνο επειδή είμαστε μόχλευση
διαιρώντας με κάποιο μεγάλο σταθερό παράγοντα.
Ας δούμε πώς αυτό μπορεί να φαίνονται πραγματικά όμως.
Έτσι, αυτό ήταν το πίνακα κατακερματισμού είχαμε πριν δηλωθεί ένας πίνακας κατακερματισμού που
ήταν ικανή να αποθηκεύσει 10 χορδές.
Εμείς δεν πρόκειται να το κάνουμε αυτό πια.
Γνωρίζουμε ήδη η περιορισμοί αυτής της μεθόδου.
Τώρα πίνακα hash μας πρόκειται να είναι μια σειρά από 10 κόμβους, δείκτες
στους αρχηγούς συνδεδεμένες λίστες.
>> Και τώρα είναι άκυρη.
Κάθε ένα από αυτά τα 10 δείκτες είναι άκυρη.
Δεν υπάρχει τίποτα σε μας hash πίνακα τώρα.
>> Τώρα, ας αρχίσουμε να βάλουν κάποια τα πράγματα σε αυτό τον πίνακα κατακερματισμού.
Και ας δούμε πώς αυτή η μέθοδος είναι Θα μας ωφελήσει λίγο.
Ας τώρα hash Joey.
Θα θα τρέξει το κορδόνι μέσα από Joey μια συνάρτηση κατακερματισμού και επιστρέφουμε 6.
Λοιπόν, τι κάνουμε τώρα;
>> Καλά τώρα εργάζονται με συνδεδεμένες λίστες, δεν είμαστε σε συνεργασία με συστοιχίες.
Και όταν δουλεύουμε με συνδεδεμένες λίστες μας
Ξέρουμε ότι πρέπει να ξεκινήσει δυναμικά κατανομή χώρου και τη δημιουργία αλυσίδων.
Αυτό είναι το είδος της how-- αυτά είναι ο πυρήνας στοιχεία της οικοδόμησης μιας συνδεδεμένης λίστας.
Ας δυναμικά διατεθεί χώρος για τον Joey,
και, στη συνέχεια, ας τον προσθέσετε στην αλυσίδα.
>> Έτσι τώρα κοίτα τι έχουμε κάνει.
Όταν hash Joey πήραμε το hashCode 6.
Τώρα ο δείκτης σε θέση πίνακα 6 επισημαίνει στο κεφάλι του μια συνδεδεμένη λίστα,
και αυτή τη στιγμή είναι το μόνο στοιχείο μιας συνδεδεμένης λίστας.
Και ο κόμβος στο ότι συνδεδεμένη λίστα είναι ο Joey.
>> Έτσι, αν θα πρέπει να κοιτάζω προς τα πάνω τον Joey αργότερα, εμείς απλά χασίς και πάλι Joey,
έχουμε 6 και πάλι, επειδή μας hash λειτουργία είναι αιτιοκρατική.
Και τότε θα ξεκινήσει στην κορυφή της συνδεδεμένη λίστα επισήμανε
με βάση την τοποθεσία συστοιχία 6, και μπορούμε να επαναλάβει
σε όλη ότι προσπαθεί να βρει τον Joey.
Και αν χτίσουμε μας hash πίνακα αποτελεσματικά,
συνάρτηση κατακερματισμού και μας αποτελεσματικά για τη διανομή των δεδομένων και,
κατά μέσο όρο, κάθε μία από εκείνες που συνδέονται καταλόγους σε κάθε θέση πίνακα
θα είναι το 1/10 του μεγέθους του, αν ακριβώς είχε ως ενιαίο τεράστιο
συνδεδεμένη λίστα με τα πάντα σε αυτό.
>> Αν διανείμετε αυτή την τεράστια συνδέεται λίστα σε 10 συνδεδεμένες λίστες
κάθε λίστα θα είναι το 1/10 του μεγέθους.
Και έτσι 10 φορές πιο γρήγορα να ψάξετε μέσα.
Ας κάνουμε αυτό και πάλι.
Ας τώρα hash Ross.
>> Και ας πούμε Ross, όταν το κάνουμε αυτό ο κώδικας κατακερματισμού παίρνουμε πίσω είναι 2.
Καλά τώρα διαθέτουμε ένα δυναμικά νέος κόμβος, βάζουμε Ross σε αυτόν τον κόμβο,
και λέμε τώρα θέση πίνακα 2, αντί να δείχνουν σε null,
επισημαίνει στο κεφάλι ενός συνδεδεμένου κατάλογος των οποίων μόνο ο κόμβος είναι ο Ross.
Και μπορούμε να το κάνουμε μία ακόμη φορά, εμείς μπορεί hash Rachel και να πάρει hashCode 4.
malloc ένα νέο κόμβο, βάλτε σε Rachel ο κόμβος, και να πω μια θέση πίνακα
4 σημεία τώρα στο κεφάλι του οποίου η συνδεδεμένη λίστα
μόνο στοιχείο που συμβαίνει να είναι Rachel.
>> ΟΚ, αλλά τι θα συμβεί αν έχουμε μια σύγκρουση;
Ας δούμε πώς μπορούμε να χειριστεί συγκρούσεις χρησιμοποιώντας τη μέθοδο ξεχωριστά αλύσωσης.
Ας hash Φοίβη.
Παίρνουμε την hashCode 6.
Στο προηγούμενο παράδειγμα μας ήταν απλά αποθήκευση των χορδών στη συστοιχία.
Αυτό ήταν ένα πρόβλημα.
>> Δεν θέλουμε να κοπανάω Joey, και έχουμε ήδη
φαίνεται ότι μπορούμε να πάρουμε κάποια ομαδοποίηση προβλήματα αν προσπαθήσουμε και βήμα
μέσω και του ανιχνευτή.
Αλλά τι γίνεται αν έχουμε ακριβώς το είδος του αντιμετωπίσει αυτό με τον ίδιο τρόπο, σωστά;
Είναι ακριβώς όπως την προσθήκη ενός στοιχείου στο κεφάλι μιας συνδεδεμένης λίστας.
Ας malloc χώρο για Φοίβη.
>> Θα πω στη συνέχεια τα σημεία του δείκτη Φοίβη στην παλιά επικεφαλής της συνδεδεμένης λίστας,
και στη συνέχεια 6 σημεία ακριβώς στην νέος επικεφαλής της συνδεδεμένης λίστας.
Και τώρα να δείτε, έχουμε αλλάξει σε Φοίβη.
Μπορούμε τώρα να αποθηκεύσει δύο στοιχεία με hashCode 6,
και δεν έχουμε κανένα πρόβλημα.
>> Αυτό είναι λίγο πολύ όλα Είναι εκεί για να αλύσωσης.
Και της σύνδεσης είναι σίγουρα η μέθοδος που είναι
πρόκειται να είναι πιο αποτελεσματικό για σας εάν η αποθήκευση δεδομένων σε έναν πίνακα κατακερματισμού.
Αλλά αυτός ο συνδυασμός του πίνακες και συνδεδεμένες λίστες
μαζί για να σχηματίσουν έναν πίνακα hash πραγματικά βελτιώνει δραματικά την ικανότητα σας
να αποθηκεύουν μεγάλες ποσότητες δεδομένων, και πολύ γρήγορα και αποτελεσματικά αναζήτηση
μέσω της εν λόγω δεδομένα.
>> Υπάρχει μία ακόμη δομή δεδομένων εκεί έξω
ότι θα μπορούσε ακόμη και να είναι λίγο καλύτερη από την άποψη της διασφάλισης
ότι μας εισαγωγή, διαγραφή, και κοιτάζω προς τα πάνω οι χρόνοι είναι ακόμη πιο γρήγορα.
Και θα δούμε ότι σε ένα βίντεο σχετικά με προσπάθειες.
Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.