ROB BOWDEN: Ciao. Sono Rob e hash di let questa soluzione out. Così qui stiamo andando a implementare una tabella hash generale. Si vede che il nodo struct del nostro hash tabella è andare a guardare come questo. Così sta andando ad avere un carattere normale array di lunghezza più di formato 1. Non dimenticare il 1 dato che il massimo parola nel dizionario è di 45 personaggi, e poi andremo a bisogno di un carattere in più per la backslash 0. 

E allora la nostra tabella hash in ogni benna sta per memorizzare un lista concatenata di nodi. Non stiamo facendo scansione lineare qui. E così, al fine di collegare al successivo elemento nel secchio, abbiamo bisogno di una struct node * prossimo. Quindi questo è quello che un nodo assomiglia. Ora, ecco la dichiarazione della nostra tabella hash. E 'intenzione di avere 16.384 secchi, ma tale numero non ha molta importanza. E, infine, stiamo andando ad avere la hashtable_size variabile globale, che sta per cominciare come 0, ed è andando a tenere traccia di quante parole erano in nostro dizionario. Bene. 

Quindi diamo un'occhiata a carico. Quindi notare che il carico, restituisce un bool. Si ritorna true se fosse successo caricato e false altrimenti. E ci vuole un const char * stelle dizionario, che è il dizionario che vogliamo aprire. Ecco, questo è la prima cosa stiamo andando a fare. Stiamo andando a fopen il dizionario per lettura, e stiamo andando ad avere per assicurarsi che riuscì quindi se è tornato NULL, allora non abbiamo aprire correttamente il dizionario e abbiamo bisogno di tornare false. 

Ma supponendo che lo ha fatto con successo aperto, quindi vogliamo leggere l' dizionario. In modo da mantenere il ciclo finché non troviamo un po ' motivo per uscire da questo ciclo che vedremo. Così continuiamo a loop, e ora stiamo andando a malloc un singolo nodo. E, naturalmente, abbiamo bisogno di errore di controllo di nuovo quindi se mallocing non è riuscita e vogliamo scaricare qualsiasi nodo che è successo a malloc prima, chiudere il Dizionario e restituire false. 

Ma ignorare che, assumendo che riuscito, allora vogliamo usare fscanf leggere una sola parola dei Dizionario nel nostro nodo. Quindi ricorda che la parola d'ordine-> è il char tampone parola di lunghezza plus size quello che stiamo andando a memorizzare la parola dentro Così fscanf sta per tornare 1 finché come è stato in grado di leggere correttamente un Messaggio del file. 

Se uno dei due si verifica un errore o si raggiunge la fine del file, non sarà ritorno 1 nel qual caso, se non lo fa ritorno 1, stiamo finalmente andando a rompere su questo ciclo while. Così vediamo che quando abbiamo successo leggere una parola in entry-> parola, allora stiamo andando a hash che la parola utilizzando la nostra funzione di hash. Diamo uno sguardo a la funzione hash. 

Quindi non si ha realmente bisogno per capire questo. E in realtà, abbiamo appena tirato questa hash funzione da internet. L'unica cosa che dovete riconoscere è che questo richiede un const char * word, così sta prendendo una stringa come input e restituire un int unsigned come output. Ecco, questo è tutto una funzione di hash è, è prende in ingresso, si dà un indice nella tabella hash. Notate che stiamo modding da NUM_BUCKETS quindi il valore hash restituito in realtà è un indice nella tabella hash e non indicizza oltre il limiti della matrice. 

Quindi, dato che la funzione di hash, stiamo andando hash la parola che leggiamo dal dizionario e poi stiamo andando utilizzare che deve inserire la voce nella tabella hash. Ora, hash hashtable è la corrente lista collegata nella tabella hash, e è molto probabile che è proprio NULL. Vogliamo inserire il nostro ingresso alla inizio di questa lista collegata, e così stiamo per avere la nostra voce corrente puntare a ciò che la tabella hash attualmente punti e poi andremo a memorizzare nella tabella hash al hash la voce corrente. 

Così queste due righe inserire con successo la voce all'inizio del lista collegata a tale indice nella tabella hash. Una volta che abbiamo finito con quello, sappiamo che abbiamo trovato un'altra parola nella dizionario e noi incrementano di nuovo. Così continuiamo a farlo fino fscanf finalmente restituisce qualcosa di non 1 a questo punto ricordare che abbiamo bisogno di ingresso gratuito, così qui, abbiamo malloced un ingresso e abbiamo cercato di leggere qualcosa dal dizionario. E non abbiamo letto con successo qualcosa dal dizionario in cui caso abbiamo bisogno di liberare la voce che si in realtà mai messo in tabella hash e infine rompere. 

Una volta che usciamo, abbiamo bisogno di vedere, bene, fatto usciamo perché non stava leggendo un errore dal file, o abbiamo rompere fuori perché abbiamo raggiunto la fine del file? Se c'è stato un errore, allora vogliamo return false perché il carico non ha successo, e nel processo, vogliamo scaricare tutte le parole che leggiamo e chiudere il file dizionario. Supponendo che ci siamo riusciti, poi abbiamo appena ancora bisogno di chiudere il dizionario File e infine ritorno vero in quanto abbiamo caricato con successo l' dizionario. E questo è tutto per il carico. 

Così ora controllare, in una tabella hash caricato, sta andando a guardare come questo. Quindi controllare, restituisce un bool, che sta per indicare se il passata in char * parola, se l' stringa passata-in è nel nostro dizionario. Quindi, se è nel dizionario, se è nella nostra tabella hash, torneremo vero, e se non lo è, ci torneremo false. Data questa parola passata in, siamo andando hash parola. 

Ora, una cosa importante da riconoscere è che nel carico, sapevamo che tutte le parole stavano per essere minuscolo, ma qui, non siamo così sicuri. Se diamo uno sguardo alla nostra funzione di hash, la nostra funzione di hash realtà è caratteri minuscoli ogni personaggio della parola. Quindi, indipendentemente dalla capitalizzazione di parola, la nostra funzione hash sta per restituire lo stesso indice per qualunque capitalizzazione è come sarebbe restituito per completamente minuscolo versione della parola. Bene. 

Ecco, questo è il nostro indice. E 'la tabella di hash per questa parola. Ora, questo ciclo for sta andando a oltre l'elenco collegato che era a tale indice. Così notiamo che stiamo inizializzazione di iscrizione per puntare a tale indice. Abbiamo intenzione di continuare mentre entry fa non uguale NULL, e ricordate che aggiornando il puntatore nella nostra lista collegata entry uguale entry-> prossimo, in modo da avere nostro punto di ingresso corrente al elemento successivo in lista collegata. Bene. 

Quindi, per ogni voce nella lista collegata, stiamo andando a utilizzare strcasecmp. Non è strcmp perché ancora una volta, abbiamo vogliono fare caso le cose insensitively. Quindi usiamo strcasecmp di confrontare la parola che è stato passato a questa funzione contro la parola che è in questa voce. Se restituisce 0, che significa che non c'era una partita, in questo caso vogliamo return true. Abbiamo trovato con successo la parola nella nostra tabella hash. 

Se non ci fosse una partita, quindi siamo andando in loop di nuovo e guardare il voce successiva. E noi continueremo looping mentre ci sono voci in questa lista collegata. Cosa succede se rompiamo fuori di questo ciclo for? Questo significa che non abbiamo trovato una voce che abbinato questa parola, nel qual caso torniamo false per indicare che il nostro tabella di hash non conteneva questa parola. E questo è tutto per il controllo. Bene. 

Quindi diamo un'occhiata a dimensioni. Ora, la dimensione sarà piuttosto semplice da ricordare in carico, per ogni parola abbiamo trovato abbiamo incrementato globale hashtable_size variabile. Quindi la funzione di dimensione è solo andando a ritorno che globale variabile, e questo è tutto. 

Ora finalmente, abbiamo bisogno di scaricare la dizionario una volta che tutto è fatto. Quindi, come facciamo a fare questo? Proprio qui, stiamo eseguendo un ciclo su tutto secchi di nostra tabella di hash. Quindi ci sono NUM_BUCKETS secchi. E per ogni lista collegata nel nostro hash tavolo, stiamo andando a cappio sopra la elementi della lista collegata liberando ogni elemento. Ora, dobbiamo stare attenti, ecco noi avere una variabile temporanea che è memorizzare il puntatore al successivo elemento della lista concatenata. E poi stiamo andando alla libera l'elemento corrente. 

Dobbiamo essere sicuri che facciamo da quando abbiamo non si può semplicemente liberare l'elemento corrente e quindi provare ad accedere l'indicatore accanto dal momento che una volta liberata l' la memoria non è più valido. Quindi abbiamo bisogno di mantenere attorno a un puntatore a l'elemento successivo, allora possiamo liberare il elemento corrente, e quindi possiamo aggiornare il nostro elemento corrente per puntare a l'elemento successivo. 

Ti ciclo while ci sono elementi in questa lista collegata. Lo faremo per tutte le liste collegate in la tabella hash, e una volta che avremo finito con questo, abbiamo completamente scaricato la tabella hash, e abbiamo finito. Quindi è impossibile per singole discariche di sempre return false, e quando abbiamo finito, abbiamo solo return true.