1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Hi.

3
00:00:13,050 --> 00:00:16,210
Είμαι Rob, και hash ας
Αυτό το διάλυμα έξω.

4
00:00:16,210 --> 00:00:20,070
Έτσι, εδώ θα πάμε να εφαρμόσει
ένα γενικό πίνακα κατακερματισμού.

5
00:00:20,070 --> 00:00:24,090
Βλέπουμε ότι ο κόμβος struct του κατακερματισμού μας
πίνακας πρόκειται να μοιάζει με αυτό.

6
00:00:24,090 --> 00:00:28,710
Έτσι πρόκειται να έχουν μια λέξη char
πίνακας μήκους συν μέγεθος 1.

7
00:00:28,710 --> 00:00:32,259
Μην ξεχνάτε το 1, εφόσον η μέγιστη
λέξη στο λεξικό είναι 45

8
00:00:32,259 --> 00:00:35,110
χαρακτήρες, και στη συνέχεια θα πάμε να
χρειάζονται ένα επιπλέον χαρακτήρα για την

9
00:00:35,110 --> 00:00:37,070
backslash 0.

10
00:00:37,070 --> 00:00:40,870
>> Και στη συνέχεια τον πίνακα hash μας σε κάθε
κάδος πρόκειται να αποθηκεύσετε ένα

11
00:00:40,870 --> 00:00:42,320
συνδεδεμένη λίστα των κόμβων.

12
00:00:42,320 --> 00:00:44,420
Εμείς δεν κάνουμε γραμμική σχολαστικά εδώ.

13
00:00:44,420 --> 00:00:48,430
Και έτσι, ώστε να συνδεθεί με την επόμενη
στοιχείο στον κάδο, χρειαζόμαστε μια

14
00:00:48,430 --> 00:00:51,110
struct node * επόμενο.

15
00:00:51,110 --> 00:00:53,090
Έτσι, αυτό είναι ένας κόμβος μοιάζει.

16
00:00:53,090 --> 00:00:56,180
Τώρα, εδώ είναι η δήλωση
του πίνακα κατακερματισμού μας.

17
00:00:56,180 --> 00:01:01,910
Είναι πρόκειται να έχει 16.384 κάδους, αλλά
ο αριθμός αυτός δεν έχει τόση σημασία.

18
00:01:01,910 --> 00:01:05,450
Και τέλος, θα πάμε να έχουν το
καθολική μεταβλητή hashtable_size, η οποία

19
00:01:05,450 --> 00:01:08,640
πρόκειται να ξεκινήσει ως 0, και είναι
πρόκειται να παρακολουθείτε πόσες λέξεις

20
00:01:08,640 --> 00:01:10,080
ήταν στο λεξικό μας.

21
00:01:10,080 --> 00:01:10,760
Εντάξει.

22
00:01:10,760 --> 00:01:13,190
>> Έτσι, ας ρίξουμε μια ματιά στο φορτίο.

23
00:01:13,190 --> 00:01:16,390
Έτσι, παρατηρούμε ότι το φορτίο,
επιστρέφει ένα bool.

24
00:01:16,390 --> 00:01:20,530
Θα επιστρέψει true αν ήταν επιτυχία
φορτωμένο και false διαφορετικά.

25
00:01:20,530 --> 00:01:23,990
Και παίρνει ένα const char * αστέρων
λεξικό, το οποίο είναι το λεξικό

26
00:01:23,990 --> 00:01:25,280
ότι θέλουμε να ανοίξουμε.

27
00:01:25,280 --> 00:01:27,170
Έτσι, αυτό είναι το πρώτο πράγμα που
θα πάμε να κάνουμε.

28
00:01:27,170 --> 00:01:30,420
Εμείς πάμε για να fopen το λεξικό για
ανάγνωση, και θα πάμε να έχουν

29
00:01:30,420 --> 00:01:34,700
για να βεβαιωθείτε ότι πέτυχε έτσι εάν
επέστρεψε NULL, στη συνέχεια, δεν είχαμε

30
00:01:34,700 --> 00:01:37,440
επιτυχία ανοίξτε το λεξικό
και πρέπει να επιστρέψει false.

31
00:01:37,440 --> 00:01:41,580
>> Αλλά και αν υποτεθεί ότι το έκανε με επιτυχία
ανοιχτό, τότε θα θέλετε να διαβάσετε το

32
00:01:41,580 --> 00:01:42,400
λεξικό.

33
00:01:42,400 --> 00:01:46,210
Γι 'αυτό κράτα looping μέχρι να βρούμε κάποια
λόγος για να ξεφύγει από αυτό το

34
00:01:46,210 --> 00:01:47,570
βρόχο που θα δούμε.

35
00:01:47,570 --> 00:01:51,780
Γι 'αυτό κράτα looping, και τώρα θα πάμε
να malloc έναν μεμονωμένο κόμβο.

36
00:01:51,780 --> 00:01:56,800
Και φυσικά, θα πρέπει να ελέγξετε σφάλματος
και πάλι, ώστε αν mallocing δεν πετύχει

37
00:01:56,800 --> 00:02:00,660
και θέλουμε να ξεφορτώσουν κάθε κόμβο που
συνέβη με malloc πριν, κλείστε το

38
00:02:00,660 --> 00:02:02,590
λεξικό και επιστρέφει false.

39
00:02:02,590 --> 00:02:07,440
>> Αλλά αγνοώντας ότι, αν υποτεθεί ότι
καταφέρει, τότε θα θέλετε να χρησιμοποιήσετε fscanf

40
00:02:07,440 --> 00:02:12,400
να διαβάσει μια λέξη από μας
λεξικό στο κόμβο μας.

41
00:02:12,400 --> 00:02:17,310
Έτσι, να θυμάστε ότι η λέξη εισόδου-> είναι ο char
ρυθμιστικό λέξη μήκους συν μέγεθος

42
00:02:17,310 --> 00:02:20,300
κάτι που εμείς πάμε να
αποθηκεύσετε τη λέξη μέσα

43
00:02:20,300 --> 00:02:25,280
Έτσι fscanf πρόκειται να επιστρέψει 1, εφόσον
καθώς ήταν σε θέση να διαβάσει με επιτυχία μια

44
00:02:25,280 --> 00:02:26,750
λέξη από το αρχείο.

45
00:02:26,750 --> 00:02:31,030
>> Αν είτε ένα λάθος που συμβαίνει ή φτάνουμε
το τέλος του αρχείου, δεν θα

46
00:02:31,030 --> 00:02:34,950
επιστρέφει 1 στην οποία περίπτωση, εάν δεν το κάνει
επιστροφή 1, είμαστε επιτέλους να σπάσει

47
00:02:34,950 --> 00:02:37,280
έξω από αυτό, ενώ βρόχο.

48
00:02:37,280 --> 00:02:42,770
Έτσι, βλέπουμε ότι από τη στιγμή που έχουμε με επιτυχία
διαβάστε μια λέξη σε

49
00:02:42,770 --> 00:02:48,270
entry-> λέξη, τότε θα πάμε να hash
η λέξη χρησιμοποιώντας τη λειτουργία hash μας.

50
00:02:48,270 --> 00:02:49,580
Ας ρίξουμε μια ματιά
η συνάρτηση κατακερματισμού.

51
00:02:49,580 --> 00:02:52,430

52
00:02:52,430 --> 00:02:55,610
>> Έτσι, δεν πρέπει πραγματικά
να το καταλάβουμε αυτό.

53
00:02:55,610 --> 00:02:59,460
Και πραγματικά, τράβηξε ακριβώς αυτό
hash λειτουργία από το διαδίκτυο.

54
00:02:59,460 --> 00:03:04,010
Το μόνο πράγμα που πρέπει να αναγνωρίσουμε είναι
ότι αυτό παίρνει const char * λέξη,

55
00:03:04,010 --> 00:03:08,960
έτσι ώστε να παίρνει ένα string ως πρώτη ύλη και
επιστρέφοντας ένα unsigned int ως έξοδο.

56
00:03:08,960 --> 00:03:12,360
Έτσι ώστε να είναι όλα μια συνάρτηση κατακερματισμού, είναι
παίρνει σε μια είσοδο, σας δίνει AN

57
00:03:12,360 --> 00:03:14,490
δείκτης στον πίνακα κατακερματισμού.

58
00:03:14,490 --> 00:03:18,530
Παρατηρήστε ότι είμαστε modding από NUM_BUCKETS
έτσι επέστρεψε η τιμή κατακερματισμού

59
00:03:18,530 --> 00:03:21,730
στην πραγματικότητα είναι ένας δείκτης στον πίνακα κατακερματισμού
και δεν δείκτη πέρα ​​από το

60
00:03:21,730 --> 00:03:24,320
όρια της συστοιχίας.

61
00:03:24,320 --> 00:03:27,855
>> Έτσι, δεδομένου ότι η συνάρτηση κατακερματισμού, θα πάμε
για τον κατακερματισμό της λέξης που διαβάζουμε

62
00:03:27,855 --> 00:03:31,700
από το λεξικό και στη συνέχεια θα πάμε
στη χρήση που πρέπει να εισάγετε το

63
00:03:31,700 --> 00:03:33,750
την έναρξη του πίνακα κατακερματισμού.

64
00:03:33,750 --> 00:03:38,830
Τώρα, hashtable hash είναι η τρέχουσα
συνδεδεμένη λίστα στον πίνακα κατακερματισμού, και

65
00:03:38,830 --> 00:03:41,410
είναι πολύ πιθανό ότι είναι απλά NULL.

66
00:03:41,410 --> 00:03:45,640
Θέλουμε να εισάγετε την είσοδό μας κατά τη
ξεκινώντας από αυτήν την συνδεδεμένη λίστα, και έτσι

67
00:03:45,640 --> 00:03:48,910
θα πάμε να έχουν ρεύμα εισόδου μας
σημείο σε ό, τι τον πίνακα κατακερματισμού σήμερα

68
00:03:48,910 --> 00:03:54,030
σημεία και στη συνέχεια θα πάμε να αποθηκεύσετε
στον πίνακα κατακερματισμού στο hash

69
00:03:54,030 --> 00:03:55,350
η τρέχουσα καταχώρηση.

70
00:03:55,350 --> 00:03:59,320
>> Έτσι, αυτές οι δύο γραμμές εισάγουν επιτυχώς
Η είσοδος κατά την έναρξη της

71
00:03:59,320 --> 00:04:02,270
συνδεδεμένη λίστα σε αυτό το ευρετήριο
στον πίνακα κατακερματισμού.

72
00:04:02,270 --> 00:04:04,900
Μόλις τελειώσετε με αυτό, γνωρίζουμε
ότι βρήκαμε μια άλλη λέξη στο

73
00:04:04,900 --> 00:04:07,800
λεξικό και θα αυξήσετε και πάλι.

74
00:04:07,800 --> 00:04:13,960
Έτσι κρατάμε το κάνουμε αυτό μέχρι fscanf
επιτέλους επιστρέφει κάτι που δεν σε 1

75
00:04:13,960 --> 00:04:18,560
το οποίο σημείο να θυμάστε ότι πρέπει να
ελεύθερη είσοδο, τόσο εδώ, έχουμε μια malloced

76
00:04:18,560 --> 00:04:21,329
εισόδου και προσπαθήσαμε να διαβάσω κάτι
από το λεξικό.

77
00:04:21,329 --> 00:04:24,110
Και εμείς δεν διαβάστηκε επιτυχώς
κάτι από το λεξικό στο οποίο

78
00:04:24,110 --> 00:04:27,440
περίπτωση θα πρέπει να ελευθερώσετε την είσοδο που
πραγματικότητα δεν τίθενται ποτέ στον πίνακα κατακερματισμού

79
00:04:27,440 --> 00:04:29,110
και τελικά να σπάσουν.

80
00:04:29,110 --> 00:04:32,750
>> Μόλις ξεσπάσει, πρέπει να δούμε, επίσης,
δεν έχουμε σπάσει, επειδή εκεί έξω

81
00:04:32,750 --> 00:04:35,840
ήταν ένα σφάλμα κατά την ανάγνωση από το αρχείο, ή
κάναμε ξεσπάσει γιατί φτάσαμε

82
00:04:35,840 --> 00:04:37,120
το τέλος του αρχείου;

83
00:04:37,120 --> 00:04:40,150
Αν υπήρχε ένα λάθος, τότε θέλουμε να
return false, επειδή το φορτίο δεν έκανε

84
00:04:40,150 --> 00:04:43,260
επιτύχουμε, και στη διαδικασία, θέλουμε να
ξεφορτώσουν όλες τις λέξεις που διαβάζουμε

85
00:04:43,260 --> 00:04:45,670
και κλείστε το αρχείο λεξικού.

86
00:04:45,670 --> 00:04:48,740
Υποθέτοντας ότι τα κατάφερε, τότε απλά
πρέπει ακόμα να κλείσει το λεξικό

87
00:04:48,740 --> 00:04:51,970
αρχείο, και τελικά επιστρέφει αληθές, δεδομένου
έχουμε φορτωθεί με επιτυχία το

88
00:04:51,970 --> 00:04:53,040
λεξικό.

89
00:04:53,040 --> 00:04:54,420
Και αυτό είναι για το φορτίο.

90
00:04:54,420 --> 00:04:59,020
>> Έτσι ελέγχουν τώρα, δίνεται ένα φορτωμένο πίνακα κατακερματισμού,
πρόκειται να μοιάζει με αυτό.

91
00:04:59,020 --> 00:05:02,690
Έτσι ελέγχετε, επιστρέφει μια bool, η οποία
πρόκειται να δείξει εάν η

92
00:05:02,690 --> 00:05:07,530
πέρασε στο char * λέξη, αν η
πέρασε στο string είναι στο λεξικό μας.

93
00:05:07,530 --> 00:05:10,530
Έτσι, αν είναι στο λεξικό, αν είναι
στον πίνακα hash μας, εμείς θα επιστρέψει

94
00:05:10,530 --> 00:05:13,380
αλήθεια, και αν δεν είναι,
θα επιστρέψει false.

95
00:05:13,380 --> 00:05:17,770
Λαμβάνοντας υπόψη αυτό μετακυλίεται στα λόγια, είμαστε
πρόκειται για τον κατακερματισμό της λέξης.

96
00:05:17,770 --> 00:05:22,020
>> Τώρα, ένα σημαντικό πράγμα που πρέπει να αναγνωρίσουμε είναι
ότι το φορτίο, ξέραμε ότι όλα

97
00:05:22,020 --> 00:05:25,820
οι λέξεις επρόκειτο να είναι πεζά,
αλλά εδώ, δεν είμαστε τόσο σίγουροι.

98
00:05:25,820 --> 00:05:29,510
Αν ρίξουμε μια ματιά σε συνάρτηση κατακερματισμού μας,
μας λειτουργία hash πραγματικότητα

99
00:05:29,510 --> 00:05:32,700
είναι lowercasing κάθε χαρακτήρα
της λέξης.

100
00:05:32,700 --> 00:05:37,580
Έτσι, ανεξάρτητα από την κεφαλαιοποίηση
λέξη, συνάρτηση κατακερματισμού μας πρόκειται να

101
00:05:37,580 --> 00:05:42,270
επιστρέφει τον ίδιο δείκτη, ανεξάρτητα από το
κεφαλαιοποίησης είναι όπως θα έπρεπε

102
00:05:42,270 --> 00:05:45,280
Επέστρεψε για μια εντελώς πεζά
εκδοχή της λέξης.

103
00:05:45,280 --> 00:05:45,950
Εντάξει.

104
00:05:45,950 --> 00:05:47,410
>> Έτσι, αυτό είναι το ευρετήριό μας.

105
00:05:47,410 --> 00:05:49,790
Είναι ο πίνακας κατακερματισμού για αυτή τη λέξη.

106
00:05:49,790 --> 00:05:52,940
Τώρα, αυτό για το βρόχο θα
να πάνω από την συνδεδεμένη λίστα

107
00:05:52,940 --> 00:05:55,000
ότι ήταν λόγω δείκτη.

108
00:05:55,000 --> 00:05:59,630
Έτσι παρατηρούμε εμείς την προετοιμασία εισόδου
να οδηγούν σε αυτό το δείκτη.

109
00:05:59,630 --> 00:06:03,480
Εμείς πάμε για να συνεχίσει, ενώ κάνει είσοδο
δεν είναι ίσες NULL, και να θυμάστε ότι

110
00:06:03,480 --> 00:06:08,350
την ενημέρωση του δείκτη στη συνδεδεμένη λίστα μας
εισόδου ισοδυναμεί με την είσοδο-> επόμενο, έτσι ώστε να έχουν

111
00:06:08,350 --> 00:06:13,840
τρέχον σημείο εισόδου μας στο
επόμενο στοιχείο συνδεδεμένη λίστα.

112
00:06:13,840 --> 00:06:14,400
Εντάξει.

113
00:06:14,400 --> 00:06:19,150
>> Έτσι, για κάθε καταχώρηση στη συνδεδεμένη λίστα,
θα πάμε να χρησιμοποιήσετε strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Δεν είναι strcmp γιατί για άλλη μια φορά, εμείς
θέλουν να κάνουν τα πράγματα περίπτωση insensitively.

115
00:06:23,780 --> 00:06:28,830
Έτσι χρησιμοποιούμε strcasecmp να συγκρίνουν τη λέξη
η οποία πέρασε σε αυτή τη λειτουργία

116
00:06:28,830 --> 00:06:31,860
κατά το λόγο ότι
είναι σε αυτή την καταχώρηση.

117
00:06:31,860 --> 00:06:35,570
Αν επιστρέψει 0, αυτό σημαίνει ότι δεν υπήρχε
έναν αγώνα, οπότε θέλουμε να

118
00:06:35,570 --> 00:06:36,630
return true.

119
00:06:36,630 --> 00:06:39,590
Βρήκαμε επιτυχώς η
λέξη στον πίνακα hash μας.

120
00:06:39,590 --> 00:06:43,040
>> Εάν δεν υπάρχει αντιστοιχία, τότε είμαστε
πρόκειται να βρόχο και πάλι και να δούμε το

121
00:06:43,040 --> 00:06:43,990
επόμενη καταχώρηση.

122
00:06:43,990 --> 00:06:47,640
Και θα συνεχίσουμε looping, ενώ υπάρχει
είναι καταχωρήσεις σε αυτήν την συνδεδεμένη λίστα.

123
00:06:47,640 --> 00:06:50,160
Τι θα συμβεί αν σπάσει
έξω από αυτό για βρόχο;

124
00:06:50,160 --> 00:06:55,110
Αυτό σημαίνει ότι δεν κατάφερε να βρει μια καταχώρηση που
συμφωνημένα αυτή τη λέξη, στην οποία περίπτωση

125
00:06:55,110 --> 00:07:00,220
θα επιστρέψει false για να δείξει ότι μας
hash πίνακας δεν περιέχει αυτή τη λέξη.

126
00:07:00,220 --> 00:07:01,910
Και αυτό είναι για έλεγχο.

127
00:07:01,910 --> 00:07:02,540
Εντάξει.

128
00:07:02,540 --> 00:07:04,790
>> Έτσι, ας ρίξουμε μια ματιά στο μέγεθος.

129
00:07:04,790 --> 00:07:09,280
Τώρα, το μέγεθος θα είναι αρκετά απλή
δεδομένου ότι θυμάστε το φορτίο, για κάθε λέξη

130
00:07:09,280 --> 00:07:12,880
διαπιστώσαμε ότι αυξάνεται σε παγκόσμιο επίπεδο
μεταβλητή hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Έτσι, η λειτουργία είναι μόνο το μέγεθος
πρόκειται να επιστρέψει ότι η παγκόσμια

132
00:07:15,830 --> 00:07:18,150
μεταβλητή, και αυτό είναι όλο.

133
00:07:18,150 --> 00:07:22,300
>> Τώρα επιτέλους, θα πρέπει να ξεφορτώσουν το
λεξικό φορά κάνει τα πάντα.

134
00:07:22,300 --> 00:07:25,340
Λοιπόν, πώς θα πάμε να το κάνουμε αυτό;

135
00:07:25,340 --> 00:07:30,440
Ακριβώς εδώ, είμαστε πάνω από όλα looping
κουβάδες πίνακα κατακερματισμού μας.

136
00:07:30,440 --> 00:07:33,240
Έτσι, υπάρχουν NUM_BUCKETS κουβάδες.

137
00:07:33,240 --> 00:07:37,490
Και για κάθε συνδεδεμένη λίστα στην hash μας
τραπέζι, θα πάμε να βρόχο πάνω από το

138
00:07:37,490 --> 00:07:41,070
σύνολό του συνδεδεμένη λίστα
ελευθερώνοντας κάθε στοιχείο.

139
00:07:41,070 --> 00:07:46,070
Τώρα, πρέπει να είμαστε προσεκτικοί, κι έτσι εδώ
έχουν μια προσωρινή μεταβλητή που είναι

140
00:07:46,070 --> 00:07:49,740
αποθήκευση του δείκτη προς την επόμενη
στοιχείο στην συνδεδεμένη λίστα.

141
00:07:49,740 --> 00:07:52,140
Και μετά θα πάμε στην ελεύθερη
το τρέχον στοιχείο.

142
00:07:52,140 --> 00:07:55,990
>> Πρέπει να είμαστε σίγουροι ότι κάνουμε αυτό από τότε που
Δεν μπορούμε απλά να απελευθερώσει το τρέχον στοιχείο

143
00:07:55,990 --> 00:07:59,260
και στη συνέχεια προσπαθήστε να μεταβείτε στον επόμενο δείκτη
δεδομένου ότι από τη στιγμή που θα απελευθερωθεί η

144
00:07:59,260 --> 00:08:00,870
μνήμη καθίσταται άκυρη.

145
00:08:00,870 --> 00:08:04,990
Πρέπει, λοιπόν, να κρατήσει γύρω από ένα δείκτη για
το επόμενο στοιχείο, τότε μπορούμε να ελευθερώσουμε το

146
00:08:04,990 --> 00:08:08,360
τρέχον στοιχείο, και στη συνέχεια μπορούμε να ενημερώσετε
τρέχον στοιχείο μας να υποδεικνύουν

147
00:08:08,360 --> 00:08:09,590
Το επόμενο στοιχείο.

148
00:08:09,590 --> 00:08:12,770
>> Θα βρόχο ενώ υπάρχουν στοιχεία
σε αυτή την συνδεδεμένη λίστα.

149
00:08:12,770 --> 00:08:16,450
Θα το κάνουμε αυτό για όλες τις συνδεδεμένες καταλόγους
ο πίνακας κατακερματισμού, και μόλις τελειώσαμε

150
00:08:16,450 --> 00:08:20,180
με αυτό, έχουμε εντελώς εκφορτώνονται
ο πίνακας κατακερματισμού, και τελειώσαμε.

151
00:08:20,180 --> 00:08:24,050
Έτσι είναι αδύνατο για ξεφορτώνει σε όλο
return false, και όταν τελειώσουμε, θα

152
00:08:24,050 --> 00:08:25,320
μόλις επιστρέψει αλήθεια.

153
00:08:25,320 --> 00:08:27,563