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

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

3
00:00:13,050 --> 00:00:16,210
Sono Rob e hash di let
questa soluzione out.

4
00:00:16,210 --> 00:00:20,070
Così qui stiamo andando a implementare
una tabella hash generale.

5
00:00:20,070 --> 00:00:24,090
Si vede che il nodo struct del nostro hash
tabella è andare a guardare come questo.

6
00:00:24,090 --> 00:00:28,710
Così sta andando ad avere un carattere normale
array di lunghezza più di formato 1.

7
00:00:28,710 --> 00:00:32,259
Non dimenticare il 1 dato che il massimo
parola nel dizionario è di 45

8
00:00:32,259 --> 00:00:35,110
personaggi, e poi andremo a
bisogno di un carattere in più per la

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

10
00:00:37,070 --> 00:00:40,870
>> E allora la nostra tabella hash in ogni
benna sta per memorizzare un

11
00:00:40,870 --> 00:00:42,320
lista concatenata di nodi.

12
00:00:42,320 --> 00:00:44,420
Non stiamo facendo scansione lineare qui.

13
00:00:44,420 --> 00:00:48,430
E così, al fine di collegare al successivo
elemento nel secchio, abbiamo bisogno di una

14
00:00:48,430 --> 00:00:51,110
struct node * prossimo.

15
00:00:51,110 --> 00:00:53,090
Quindi questo è quello che un nodo assomiglia.

16
00:00:53,090 --> 00:00:56,180
Ora, ecco la dichiarazione
della nostra tabella hash.

17
00:00:56,180 --> 00:01:01,910
E 'intenzione di avere 16.384 secchi, ma
tale numero non ha molta importanza.

18
00:01:01,910 --> 00:01:05,450
E, infine, stiamo andando ad avere la
hashtable_size variabile globale, che

19
00:01:05,450 --> 00:01:08,640
sta per cominciare come 0, ed è
andando a tenere traccia di quante parole

20
00:01:08,640 --> 00:01:10,080
erano in nostro dizionario.

21
00:01:10,080 --> 00:01:10,760
Bene.

22
00:01:10,760 --> 00:01:13,190
>> Quindi diamo un'occhiata a carico.

23
00:01:13,190 --> 00:01:16,390
Quindi notare che il carico,
restituisce un bool.

24
00:01:16,390 --> 00:01:20,530
Si ritorna true se fosse successo
caricato e false altrimenti.

25
00:01:20,530 --> 00:01:23,990
E ci vuole un const char * stelle
dizionario, che è il dizionario

26
00:01:23,990 --> 00:01:25,280
che vogliamo aprire.

27
00:01:25,280 --> 00:01:27,170
Ecco, questo è la prima cosa
stiamo andando a fare.

28
00:01:27,170 --> 00:01:30,420
Stiamo andando a fopen il dizionario per
lettura, e stiamo andando ad avere

29
00:01:30,420 --> 00:01:34,700
per assicurarsi che riuscì quindi se
è tornato NULL, allora non abbiamo

30
00:01:34,700 --> 00:01:37,440
aprire correttamente il dizionario
e abbiamo bisogno di tornare false.

31
00:01:37,440 --> 00:01:41,580
>> Ma supponendo che lo ha fatto con successo
aperto, quindi vogliamo leggere l'

32
00:01:41,580 --> 00:01:42,400
dizionario.

33
00:01:42,400 --> 00:01:46,210
In modo da mantenere il ciclo finché non troviamo un po '
motivo per uscire da questo

34
00:01:46,210 --> 00:01:47,570
ciclo che vedremo.

35
00:01:47,570 --> 00:01:51,780
Così continuiamo a loop, e ora stiamo andando
a malloc un singolo nodo.

36
00:01:51,780 --> 00:01:56,800
E, naturalmente, abbiamo bisogno di errore di controllo
di nuovo quindi se mallocing non è riuscita

37
00:01:56,800 --> 00:02:00,660
e vogliamo scaricare qualsiasi nodo che
è successo a malloc prima, chiudere il

38
00:02:00,660 --> 00:02:02,590
Dizionario e restituire false.

39
00:02:02,590 --> 00:02:07,440
>> Ma ignorare che, assumendo che
riuscito, allora vogliamo usare fscanf

40
00:02:07,440 --> 00:02:12,400
leggere una sola parola dei
Dizionario nel nostro nodo.

41
00:02:12,400 --> 00:02:17,310
Quindi ricorda che la parola d'ordine-> è il char
tampone parola di lunghezza plus size

42
00:02:17,310 --> 00:02:20,300
quello che stiamo andando a
memorizzare la parola dentro

43
00:02:20,300 --> 00:02:25,280
Così fscanf sta per tornare 1 finché
come è stato in grado di leggere correttamente un

44
00:02:25,280 --> 00:02:26,750
Messaggio del file.

45
00:02:26,750 --> 00:02:31,030
>> Se uno dei due si verifica un errore o si raggiunge
la fine del file, non sarà

46
00:02:31,030 --> 00:02:34,950
ritorno 1 nel qual caso, se non lo fa
ritorno 1, stiamo finalmente andando a rompere

47
00:02:34,950 --> 00:02:37,280
su questo ciclo while.

48
00:02:37,280 --> 00:02:42,770
Così vediamo che quando abbiamo successo
leggere una parola in

49
00:02:42,770 --> 00:02:48,270
entry-> parola, allora stiamo andando a hash
che la parola utilizzando la nostra funzione di hash.

50
00:02:48,270 --> 00:02:49,580
Diamo uno sguardo a
la funzione hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Quindi non si ha realmente bisogno
per capire questo.

53
00:02:55,610 --> 00:02:59,460
E in realtà, abbiamo appena tirato questa
hash funzione da internet.

54
00:02:59,460 --> 00:03:04,010
L'unica cosa che dovete riconoscere è
che questo richiede un const char * word,

55
00:03:04,010 --> 00:03:08,960
così sta prendendo una stringa come input e
restituire un int unsigned come output.

56
00:03:08,960 --> 00:03:12,360
Ecco, questo è tutto una funzione di hash è, è
prende in ingresso, si dà un

57
00:03:12,360 --> 00:03:14,490
indice nella tabella hash.

58
00:03:14,490 --> 00:03:18,530
Notate che stiamo modding da NUM_BUCKETS
quindi il valore hash restituito

59
00:03:18,530 --> 00:03:21,730
in realtà è un indice nella tabella hash
e non indicizza oltre il

60
00:03:21,730 --> 00:03:24,320
limiti della matrice.

61
00:03:24,320 --> 00:03:27,855
>> Quindi, dato che la funzione di hash, stiamo andando
hash la parola che leggiamo

62
00:03:27,855 --> 00:03:31,700
dal dizionario e poi stiamo andando
utilizzare che deve inserire la

63
00:03:31,700 --> 00:03:33,750
voce nella tabella hash.

64
00:03:33,750 --> 00:03:38,830
Ora, hash hashtable è la corrente
lista collegata nella tabella hash, e

65
00:03:38,830 --> 00:03:41,410
è molto probabile che è proprio NULL.

66
00:03:41,410 --> 00:03:45,640
Vogliamo inserire il nostro ingresso alla
inizio di questa lista collegata, e così

67
00:03:45,640 --> 00:03:48,910
stiamo per avere la nostra voce corrente
puntare a ciò che la tabella hash attualmente

68
00:03:48,910 --> 00:03:54,030
punti e poi andremo a memorizzare
nella tabella hash al hash

69
00:03:54,030 --> 00:03:55,350
la voce corrente.

70
00:03:55,350 --> 00:03:59,320
>> Così queste due righe inserire con successo
la voce all'inizio del

71
00:03:59,320 --> 00:04:02,270
lista collegata a tale indice
nella tabella hash.

72
00:04:02,270 --> 00:04:04,900
Una volta che abbiamo finito con quello, sappiamo
che abbiamo trovato un'altra parola nella

73
00:04:04,900 --> 00:04:07,800
dizionario e noi incrementano di nuovo.

74
00:04:07,800 --> 00:04:13,960
Così continuiamo a farlo fino fscanf
finalmente restituisce qualcosa di non 1 a

75
00:04:13,960 --> 00:04:18,560
questo punto ricordare che abbiamo bisogno di
ingresso gratuito, così qui, abbiamo malloced un

76
00:04:18,560 --> 00:04:21,329
ingresso e abbiamo cercato di leggere qualcosa
dal dizionario.

77
00:04:21,329 --> 00:04:24,110
E non abbiamo letto con successo
qualcosa dal dizionario in cui

78
00:04:24,110 --> 00:04:27,440
caso abbiamo bisogno di liberare la voce che si
in realtà mai messo in tabella hash

79
00:04:27,440 --> 00:04:29,110
e infine rompere.

80
00:04:29,110 --> 00:04:32,750
>> Una volta che usciamo, abbiamo bisogno di vedere, bene,
fatto usciamo perché non

81
00:04:32,750 --> 00:04:35,840
stava leggendo un errore dal file, o
abbiamo rompere fuori perché abbiamo raggiunto

82
00:04:35,840 --> 00:04:37,120
la fine del file?

83
00:04:37,120 --> 00:04:40,150
Se c'è stato un errore, allora vogliamo
return false perché il carico non ha

84
00:04:40,150 --> 00:04:43,260
successo, e nel processo, vogliamo
scaricare tutte le parole che leggiamo

85
00:04:43,260 --> 00:04:45,670
e chiudere il file dizionario.

86
00:04:45,670 --> 00:04:48,740
Supponendo che ci siamo riusciti, poi abbiamo appena
ancora bisogno di chiudere il dizionario

87
00:04:48,740 --> 00:04:51,970
File e infine ritorno vero in quanto
abbiamo caricato con successo l'

88
00:04:51,970 --> 00:04:53,040
dizionario.

89
00:04:53,040 --> 00:04:54,420
E questo è tutto per il carico.

90
00:04:54,420 --> 00:04:59,020
>> Così ora controllare, in una tabella hash caricato,
sta andando a guardare come questo.

91
00:04:59,020 --> 00:05:02,690
Quindi controllare, restituisce un bool, che
sta per indicare se il

92
00:05:02,690 --> 00:05:07,530
passata in char * parola, se l'
stringa passata-in è nel nostro dizionario.

93
00:05:07,530 --> 00:05:10,530
Quindi, se è nel dizionario, se è
nella nostra tabella hash, torneremo

94
00:05:10,530 --> 00:05:13,380
vero, e se non lo è,
ci torneremo false.

95
00:05:13,380 --> 00:05:17,770
Data questa parola passata in, siamo
andando hash parola.

96
00:05:17,770 --> 00:05:22,020
>> Ora, una cosa importante da riconoscere è
che nel carico, sapevamo che tutte

97
00:05:22,020 --> 00:05:25,820
le parole stavano per essere minuscolo,
ma qui, non siamo così sicuri.

98
00:05:25,820 --> 00:05:29,510
Se diamo uno sguardo alla nostra funzione di hash,
la nostra funzione di hash realtà

99
00:05:29,510 --> 00:05:32,700
è caratteri minuscoli ogni personaggio
della parola.

100
00:05:32,700 --> 00:05:37,580
Quindi, indipendentemente dalla capitalizzazione di
parola, la nostra funzione hash sta per

101
00:05:37,580 --> 00:05:42,270
restituire lo stesso indice per qualunque
capitalizzazione è come sarebbe

102
00:05:42,270 --> 00:05:45,280
restituito per completamente minuscolo
versione della parola.

103
00:05:45,280 --> 00:05:45,950
Bene.

104
00:05:45,950 --> 00:05:47,410
>> Ecco, questo è il nostro indice.

105
00:05:47,410 --> 00:05:49,790
E 'la tabella di hash per questa parola.

106
00:05:49,790 --> 00:05:52,940
Ora, questo ciclo for sta andando
a oltre l'elenco collegato

107
00:05:52,940 --> 00:05:55,000
che era a tale indice.

108
00:05:55,000 --> 00:05:59,630
Così notiamo che stiamo inizializzazione di iscrizione
per puntare a tale indice.

109
00:05:59,630 --> 00:06:03,480
Abbiamo intenzione di continuare mentre entry fa
non uguale NULL, e ricordate che

110
00:06:03,480 --> 00:06:08,350
aggiornando il puntatore nella nostra lista collegata
entry uguale entry-> prossimo, in modo da avere

111
00:06:08,350 --> 00:06:13,840
nostro punto di ingresso corrente al
elemento successivo in lista collegata.

112
00:06:13,840 --> 00:06:14,400
Bene.

113
00:06:14,400 --> 00:06:19,150
>> Quindi, per ogni voce nella lista collegata,
stiamo andando a utilizzare strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Non è strcmp perché ancora una volta, abbiamo
vogliono fare caso le cose insensitively.

115
00:06:23,780 --> 00:06:28,830
Quindi usiamo strcasecmp di confrontare la parola
che è stato passato a questa funzione

116
00:06:28,830 --> 00:06:31,860
contro la parola che
è in questa voce.

117
00:06:31,860 --> 00:06:35,570
Se restituisce 0, che significa che non c'era
una partita, in questo caso vogliamo

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

119
00:06:36,630 --> 00:06:39,590
Abbiamo trovato con successo la
parola nella nostra tabella hash.

120
00:06:39,590 --> 00:06:43,040
>> Se non ci fosse una partita, quindi siamo
andando in loop di nuovo e guardare il

121
00:06:43,040 --> 00:06:43,990
voce successiva.

122
00:06:43,990 --> 00:06:47,640
E noi continueremo looping mentre ci
sono voci in questa lista collegata.

123
00:06:47,640 --> 00:06:50,160
Cosa succede se rompiamo
fuori di questo ciclo for?

124
00:06:50,160 --> 00:06:55,110
Questo significa che non abbiamo trovato una voce che
abbinato questa parola, nel qual caso

125
00:06:55,110 --> 00:07:00,220
torniamo false per indicare che il nostro
tabella di hash non conteneva questa parola.

126
00:07:00,220 --> 00:07:01,910
E questo è tutto per il controllo.

127
00:07:01,910 --> 00:07:02,540
Bene.

128
00:07:02,540 --> 00:07:04,790
>> Quindi diamo un'occhiata a dimensioni.

129
00:07:04,790 --> 00:07:09,280
Ora, la dimensione sarà piuttosto semplice
da ricordare in carico, per ogni parola

130
00:07:09,280 --> 00:07:12,880
abbiamo trovato abbiamo incrementato globale
hashtable_size variabile.

131
00:07:12,880 --> 00:07:15,830
Quindi la funzione di dimensione è solo
andando a ritorno che globale

132
00:07:15,830 --> 00:07:18,150
variabile, e questo è tutto.

133
00:07:18,150 --> 00:07:22,300
>> Ora finalmente, abbiamo bisogno di scaricare la
dizionario una volta che tutto è fatto.

134
00:07:22,300 --> 00:07:25,340
Quindi, come facciamo a fare questo?

135
00:07:25,340 --> 00:07:30,440
Proprio qui, stiamo eseguendo un ciclo su tutto
secchi di nostra tabella di hash.

136
00:07:30,440 --> 00:07:33,240
Quindi ci sono NUM_BUCKETS secchi.

137
00:07:33,240 --> 00:07:37,490
E per ogni lista collegata nel nostro hash
tavolo, stiamo andando a cappio sopra la

138
00:07:37,490 --> 00:07:41,070
elementi della lista collegata
liberando ogni elemento.

139
00:07:41,070 --> 00:07:46,070
Ora, dobbiamo stare attenti, ecco noi
avere una variabile temporanea che è

140
00:07:46,070 --> 00:07:49,740
memorizzare il puntatore al successivo
elemento della lista concatenata.

141
00:07:49,740 --> 00:07:52,140
E poi stiamo andando alla libera
l'elemento corrente.

142
00:07:52,140 --> 00:07:55,990
>> Dobbiamo essere sicuri che facciamo da quando abbiamo
non si può semplicemente liberare l'elemento corrente

143
00:07:55,990 --> 00:07:59,260
e quindi provare ad accedere l'indicatore accanto
dal momento che una volta liberata l'

144
00:07:59,260 --> 00:08:00,870
la memoria non è più valido.

145
00:08:00,870 --> 00:08:04,990
Quindi abbiamo bisogno di mantenere attorno a un puntatore a
l'elemento successivo, allora possiamo liberare il

146
00:08:04,990 --> 00:08:08,360
elemento corrente, e quindi possiamo aggiornare
il nostro elemento corrente per puntare a

147
00:08:08,360 --> 00:08:09,590
l'elemento successivo.

148
00:08:09,590 --> 00:08:12,770
>> Ti ciclo while ci sono elementi
in questa lista collegata.

149
00:08:12,770 --> 00:08:16,450
Lo faremo per tutte le liste collegate in
la tabella hash, e una volta che avremo finito

150
00:08:16,450 --> 00:08:20,180
con questo, abbiamo completamente scaricato
la tabella hash, e abbiamo finito.

151
00:08:20,180 --> 00:08:24,050
Quindi è impossibile per singole discariche di sempre
return false, e quando abbiamo finito, abbiamo

152
00:08:24,050 --> 00:08:25,320
solo return true.

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