ROB BOWDEN: Hi. Είμαι Rob, και hash ας Αυτό το διάλυμα έξω. Έτσι, εδώ θα πάμε να εφαρμόσει ένα γενικό πίνακα κατακερματισμού. Βλέπουμε ότι ο κόμβος struct του κατακερματισμού μας πίνακας πρόκειται να μοιάζει με αυτό. Έτσι πρόκειται να έχουν μια λέξη char πίνακας μήκους συν μέγεθος 1. Μην ξεχνάτε το 1, εφόσον η μέγιστη λέξη στο λεξικό είναι 45 χαρακτήρες, και στη συνέχεια θα πάμε να χρειάζονται ένα επιπλέον χαρακτήρα για την backslash 0. 

Και στη συνέχεια τον πίνακα hash μας σε κάθε κάδος πρόκειται να αποθηκεύσετε ένα συνδεδεμένη λίστα των κόμβων. Εμείς δεν κάνουμε γραμμική σχολαστικά εδώ. Και έτσι, ώστε να συνδεθεί με την επόμενη στοιχείο στον κάδο, χρειαζόμαστε μια struct node * επόμενο. Έτσι, αυτό είναι ένας κόμβος μοιάζει. Τώρα, εδώ είναι η δήλωση του πίνακα κατακερματισμού μας. Είναι πρόκειται να έχει 16.384 κάδους, αλλά ο αριθμός αυτός δεν έχει τόση σημασία. Και τέλος, θα πάμε να έχουν το καθολική μεταβλητή hashtable_size, η οποία πρόκειται να ξεκινήσει ως 0, και είναι πρόκειται να παρακολουθείτε πόσες λέξεις ήταν στο λεξικό μας. Εντάξει. 

Έτσι, ας ρίξουμε μια ματιά στο φορτίο. Έτσι, παρατηρούμε ότι το φορτίο, επιστρέφει ένα bool. Θα επιστρέψει true αν ήταν επιτυχία φορτωμένο και false διαφορετικά. Και παίρνει ένα const char * αστέρων λεξικό, το οποίο είναι το λεξικό ότι θέλουμε να ανοίξουμε. Έτσι, αυτό είναι το πρώτο πράγμα που θα πάμε να κάνουμε. Εμείς πάμε για να fopen το λεξικό για ανάγνωση, και θα πάμε να έχουν για να βεβαιωθείτε ότι πέτυχε έτσι εάν επέστρεψε NULL, στη συνέχεια, δεν είχαμε επιτυχία ανοίξτε το λεξικό και πρέπει να επιστρέψει false. 

Αλλά και αν υποτεθεί ότι το έκανε με επιτυχία ανοιχτό, τότε θα θέλετε να διαβάσετε το λεξικό. Γι 'αυτό κράτα looping μέχρι να βρούμε κάποια λόγος για να ξεφύγει από αυτό το βρόχο που θα δούμε. Γι 'αυτό κράτα looping, και τώρα θα πάμε να malloc έναν μεμονωμένο κόμβο. Και φυσικά, θα πρέπει να ελέγξετε σφάλματος και πάλι, ώστε αν mallocing δεν πετύχει και θέλουμε να ξεφορτώσουν κάθε κόμβο που συνέβη με malloc πριν, κλείστε το λεξικό και επιστρέφει false. 

Αλλά αγνοώντας ότι, αν υποτεθεί ότι καταφέρει, τότε θα θέλετε να χρησιμοποιήσετε fscanf να διαβάσει μια λέξη από μας λεξικό στο κόμβο μας. Έτσι, να θυμάστε ότι η λέξη εισόδου-> είναι ο char ρυθμιστικό λέξη μήκους συν μέγεθος κάτι που εμείς πάμε να αποθηκεύσετε τη λέξη μέσα Έτσι fscanf πρόκειται να επιστρέψει 1, εφόσον καθώς ήταν σε θέση να διαβάσει με επιτυχία μια λέξη από το αρχείο. 

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

Έτσι, δεν πρέπει πραγματικά να το καταλάβουμε αυτό. Και πραγματικά, τράβηξε ακριβώς αυτό hash λειτουργία από το διαδίκτυο. Το μόνο πράγμα που πρέπει να αναγνωρίσουμε είναι ότι αυτό παίρνει const char * λέξη, έτσι ώστε να παίρνει ένα string ως πρώτη ύλη και επιστρέφοντας ένα unsigned int ως έξοδο. Έτσι ώστε να είναι όλα μια συνάρτηση κατακερματισμού, είναι παίρνει σε μια είσοδο, σας δίνει AN δείκτης στον πίνακα κατακερματισμού. Παρατηρήστε ότι είμαστε modding από NUM_BUCKETS έτσι επέστρεψε η τιμή κατακερματισμού στην πραγματικότητα είναι ένας δείκτης στον πίνακα κατακερματισμού και δεν δείκτη πέρα ​​από το όρια της συστοιχίας. 

Έτσι, δεδομένου ότι η συνάρτηση κατακερματισμού, θα πάμε για τον κατακερματισμό της λέξης που διαβάζουμε από το λεξικό και στη συνέχεια θα πάμε στη χρήση που πρέπει να εισάγετε το την έναρξη του πίνακα κατακερματισμού. Τώρα, hashtable hash είναι η τρέχουσα συνδεδεμένη λίστα στον πίνακα κατακερματισμού, και είναι πολύ πιθανό ότι είναι απλά NULL. Θέλουμε να εισάγετε την είσοδό μας κατά τη ξεκινώντας από αυτήν την συνδεδεμένη λίστα, και έτσι θα πάμε να έχουν ρεύμα εισόδου μας σημείο σε ό, τι τον πίνακα κατακερματισμού σήμερα σημεία και στη συνέχεια θα πάμε να αποθηκεύσετε στον πίνακα κατακερματισμού στο hash η τρέχουσα καταχώρηση. 

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

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

Έτσι ελέγχουν τώρα, δίνεται ένα φορτωμένο πίνακα κατακερματισμού, πρόκειται να μοιάζει με αυτό. Έτσι ελέγχετε, επιστρέφει μια bool, η οποία πρόκειται να δείξει εάν η πέρασε στο char * λέξη, αν η πέρασε στο string είναι στο λεξικό μας. Έτσι, αν είναι στο λεξικό, αν είναι στον πίνακα hash μας, εμείς θα επιστρέψει αλήθεια, και αν δεν είναι, θα επιστρέψει false. Λαμβάνοντας υπόψη αυτό μετακυλίεται στα λόγια, είμαστε πρόκειται για τον κατακερματισμό της λέξης. 

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

Έτσι, αυτό είναι το ευρετήριό μας. Είναι ο πίνακας κατακερματισμού για αυτή τη λέξη. Τώρα, αυτό για το βρόχο θα να πάνω από την συνδεδεμένη λίστα ότι ήταν λόγω δείκτη. Έτσι παρατηρούμε εμείς την προετοιμασία εισόδου να οδηγούν σε αυτό το δείκτη. Εμείς πάμε για να συνεχίσει, ενώ κάνει είσοδο δεν είναι ίσες NULL, και να θυμάστε ότι την ενημέρωση του δείκτη στη συνδεδεμένη λίστα μας εισόδου ισοδυναμεί με την είσοδο-> επόμενο, έτσι ώστε να έχουν τρέχον σημείο εισόδου μας στο επόμενο στοιχείο συνδεδεμένη λίστα. Εντάξει. 

Έτσι, για κάθε καταχώρηση στη συνδεδεμένη λίστα, θα πάμε να χρησιμοποιήσετε strcasecmp. Δεν είναι strcmp γιατί για άλλη μια φορά, εμείς θέλουν να κάνουν τα πράγματα περίπτωση insensitively. Έτσι χρησιμοποιούμε strcasecmp να συγκρίνουν τη λέξη η οποία πέρασε σε αυτή τη λειτουργία κατά το λόγο ότι είναι σε αυτή την καταχώρηση. Αν επιστρέψει 0, αυτό σημαίνει ότι δεν υπήρχε έναν αγώνα, οπότε θέλουμε να return true. Βρήκαμε επιτυχώς η λέξη στον πίνακα hash μας. 

Εάν δεν υπάρχει αντιστοιχία, τότε είμαστε πρόκειται να βρόχο και πάλι και να δούμε το επόμενη καταχώρηση. Και θα συνεχίσουμε looping, ενώ υπάρχει είναι καταχωρήσεις σε αυτήν την συνδεδεμένη λίστα. Τι θα συμβεί αν σπάσει έξω από αυτό για βρόχο; Αυτό σημαίνει ότι δεν κατάφερε να βρει μια καταχώρηση που συμφωνημένα αυτή τη λέξη, στην οποία περίπτωση θα επιστρέψει false για να δείξει ότι μας hash πίνακας δεν περιέχει αυτή τη λέξη. Και αυτό είναι για έλεγχο. Εντάξει. 

Έτσι, ας ρίξουμε μια ματιά στο μέγεθος. Τώρα, το μέγεθος θα είναι αρκετά απλή δεδομένου ότι θυμάστε το φορτίο, για κάθε λέξη διαπιστώσαμε ότι αυξάνεται σε παγκόσμιο επίπεδο μεταβλητή hashtable_size. Έτσι, η λειτουργία είναι μόνο το μέγεθος πρόκειται να επιστρέψει ότι η παγκόσμια μεταβλητή, και αυτό είναι όλο. 

Τώρα επιτέλους, θα πρέπει να ξεφορτώσουν το λεξικό φορά κάνει τα πάντα. Λοιπόν, πώς θα πάμε να το κάνουμε αυτό; Ακριβώς εδώ, είμαστε πάνω από όλα looping κουβάδες πίνακα κατακερματισμού μας. Έτσι, υπάρχουν NUM_BUCKETS κουβάδες. Και για κάθε συνδεδεμένη λίστα στην hash μας τραπέζι, θα πάμε να βρόχο πάνω από το σύνολό του συνδεδεμένη λίστα ελευθερώνοντας κάθε στοιχείο. Τώρα, πρέπει να είμαστε προσεκτικοί, κι έτσι εδώ έχουν μια προσωρινή μεταβλητή που είναι αποθήκευση του δείκτη προς την επόμενη στοιχείο στην συνδεδεμένη λίστα. Και μετά θα πάμε στην ελεύθερη το τρέχον στοιχείο. 

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

Θα βρόχο ενώ υπάρχουν στοιχεία σε αυτή την συνδεδεμένη λίστα. Θα το κάνουμε αυτό για όλες τις συνδεδεμένες καταλόγους ο πίνακας κατακερματισμού, και μόλις τελειώσαμε με αυτό, έχουμε εντελώς εκφορτώνονται ο πίνακας κατακερματισμού, και τελειώσαμε. Έτσι είναι αδύνατο για ξεφορτώνει σε όλο return false, και όταν τελειώσουμε, θα μόλις επιστρέψει αλήθεια.