[RIPRODUZIONE DI BRANI MUSICALI] DOUG LLOYD: Ormai sapere molto su array, e si sa molto su liste concatenate. E abbiamo discutere la pro e contro, abbiamo discusso che collegava gli elenchi può ottenere più grande e più piccolo, ma si occupano più dimensioni. Gli array sono molto più semplici da uso, ma sono restrittive in quanto come abbiamo per impostare la dimensione di la matrice proprio all'inizio e poi siamo bloccati con esso. 

Ma questo è, abbiamo praticamente esaurito tutti i nostri argomenti su liste e matrici collegate. O abbiamo? Forse possiamo fare qualcosa ancora più creativi. E questo genere di presta l'idea di una tabella di hash. 

Quindi, in una tabella hash che andremo a provare combinare una matrice con una lista collegata. Stiamo andando a prendere i vantaggi della matrice, come ad accesso casuale, essere in grado di andare solo a matrice Elemento 4 o array elemento 8 senza dover scorrere tutta. Questo è abbastanza veloce, giusto? 

Ma dobbiamo anche avere i nostri dati struttura in grado di crescere e restringersi. Non abbiamo bisogno, non lo facciamo vogliono essere limitato. E noi vogliamo essere in grado per aggiungere e rimuovere le cose molto facilmente, che se vi ricordate, è molto complesso con una matrice. E possiamo chiamare questo cosa nuova una tabella hash. 

E se implementato correttamente, stiamo sorta di presa i vantaggi di entrambi i dati strutture che hai già visto, array e liste concatenate. L'inserimento può iniziare a tendere theta di 1. Theta non abbiamo davvero discusso, ma theta è solo il caso medio, quello che in realtà sta per accadere. Non stai andando sempre avere la peggiore delle ipotesi, e non sei sempre andando ad avere la migliore delle ipotesi, quindi qual è lo scenario medio? 

Beh un inserimento medio in una tabella hash può iniziare ad avvicinarsi a tempo costante. E l'eliminazione può ottenere vicino al tempo costante. E ricerca può ottenere vicino al tempo costante. That's-- non abbiamo un dato struttura ma che può farlo, e quindi questo suona già come una bella grande cosa. Abbiamo davvero attenuato la svantaggi di ciascuno per conto suo. 

Per ottenere queste prestazioni l'aggiornamento, però, abbiamo bisogno di ripensare il modo in cui aggiungiamo i dati nella struttura. In particolare vogliamo che il dati stessi a dirci dove dovrebbe andare nella struttura. E se poi bisogna vedere se è in la struttura, se abbiamo bisogno di trovarlo, vogliamo guardare ai dati nuovo e poter efficacemente, utilizzando i dati, in modo casuale accedervi. Solo guardando il dati dovremmo avere un'idea di dove esattamente siamo andando a trovare nella tabella hash. 

Ora, il lato negativo di un hash tavolo è che sono davvero piuttosto male a ordinare o l'ordinamento dei dati. E infatti, se si avvia usarli per ordinare o specie dati si perde tutto il vantaggi che in precedenza avuto in termini di inserimento e cancellazione. Il tempo diventa più vicino theta di n, e abbiamo praticamente regredito in una lista collegata. E così abbiamo solo vogliamo usare hash tavoli se non ci stanno a cuore se i dati vengono ordinati. Per il contesto in cui ti usarli in CS50 probabilmente non si cura che i dati vengono ordinati. 

Quindi una tabella di hash è una combinazione di due pezzi distinti con cui siamo a conoscenza. Il primo è una funzione che che di solito chiamiamo una funzione di hash. E che la funzione di hash sta per tornare un intero non negativo, che che di solito chiamiamo un codice hash, OK? Il secondo pezzo è un array, che è in grado di memorizzare i dati del tipo che abbiamo desidera inserire nella struttura di dati. Terremo via sul linked elemento di lista, per ora e iniziare con le basi di una hash tavolo per ottenere la testa intorno ad esso, e poi ci magari saltare la mente un po 'quando abbiamo combinano matrici ed elenchi di link insieme. 

L'idea di base se è prendiamo alcuni dati. Corriamo che i dati attraverso la funzione di hash. E così i dati sono trattati e sputa fuori un numero, OK? E poi con quel numero abbiamo appena memorizzare i dati vogliamo memorizzare nella matrice in quella posizione. Così, per esempio abbiamo forse questa tabella hash di stringhe. E 'ottenuto 10 elementi in esso, in modo possiamo inserire 10 corde in esso. 

Diciamo che vogliamo hash John. Così Giovanni come i dati che vogliamo inserire in questa tabella hash da qualche parte. Dove la mettiamo? Bene in genere con un matrice finora abbiamo probabilmente avrebbe messo in ordine posizione 0. Ma ora abbiamo questa nuova funzione di hash. 

E diciamo che corriamo John attraverso questa funzione hash ed è sputa fuori 4. Beh, questo è dove siamo intenzione di voler mettere John. Vogliamo mettere Giovanni in posizione dell'array 4, perché se hash John again-- diciamo dopo siamo desidera cercare e vedere se John esiste in questo hash table-- tutto quello che dobbiamo fare è gestito attraverso lo stesso hash la funzione, ottenere il numero 4 fuori, ed essere in grado di trovare John immediatamente nella nostra struttura dati. Questo è abbastanza buono. 

Diciamo che ora facciamo ancora una volta, vogliamo hash Paolo. Vogliamo aggiungere Paul in questa tabella di hash. Diciamo che questa volta si corre Paolo attraverso la funzione di hash, il codice hash che viene generato è di 6. Bene, ora siamo in grado di mettere Paul nella posizione di matrice 6. E se abbiamo bisogno di cercare se Paolo è in questa tabella di hash, tutto quello che dobbiamo fare è eseguire Paul attraverso la funzione hash di nuovo e stiamo andando a ottenere 6 di nuovo fuori. 

E poi ci limitiamo a guardare in posizione di matrice 6. È Paul lì? Se è così, lui è nella tabella hash. È Paolo non ci sono? Non è nella tabella hash. E 'piuttosto semplice. 

Ora, come si fa a definire una funzione di hash? Beh, non c'è davvero alcun limite al numero di possibili funzioni hash. In realtà c'è un certo numero di realtà, quelli veramente buoni su internet. C'è un certo numero di realtà, quelli veramente negative su internet. E 'anche abbastanza facile di scrivere uno cattivo. 

Quindi, ciò che rende una buona funzione di hash, giusto? Beh, una buona funzione di hash dovrebbe utilizzare solo i dati che vengono hash, e tutti i dati che vengono hashing. Quindi noi non vogliamo usare anything-- noi non incorporiamo nulla altro che i dati. E vogliamo utilizzare tutti i dati. Non vogliamo usare solo un pezzo di essa, vogliamo usare tutto. Una funzione hash dovrebbe anche essere deterministico. Che cosa significa? Beh, vuol dire che ogni volta che passare la stessa porzione di dati nella funzione di hash che abbiamo sempre ottenere lo stesso codice hash fuori. Se io passo John nella funzione hash esco 4. Dovrei essere in grado di farlo 10.000 tempi e sarò sempre ottengono 4. Quindi niente numeri casuali in modo efficace possono essere coinvolti nel nostro hash tables-- nelle nostre funzioni di hash. 

Una funzione hash dovrebbe anche distribuire uniformemente i dati. Se ogni volta che si esegue dati attraverso il funzione hash si ottiene il codice hash 0, che probabilmente non è così grande, giusto? Probabilmente si desidera grande una serie di codici hash. Anche le cose possono essere diffuse durante tutta la tabella. Ed inoltre sarebbe bello se davvero dati simili, come John e Jonathan, forse sono stati sparsi per pesare diverse posizioni nella tabella hash. Questo sarebbe un bel vantaggio. 

Ecco un esempio di una funzione di hash. Ho scritto questo in precedenza. Non è un particolarmente buona funzione di hash per ragioni che non lo fanno davvero orso andando in questo momento. Ma si vede che cosa sta succedendo qui? Sembra che stiamo dichiarazione di una variabile chiamato somma e porla uguale a 0. E poi pare che sto facendo qualcosa purché strstr [j] non è uguale di backslash 0. Che cosa sto facendo lì? 

Questo è fondamentalmente solo un altro modo di attuare [? strl?] e rilevare quando hai raggiunta la fine della stringa. Quindi io non devo realmente calcolare la lunghezza della stringa, Sto usando solo quando ho colpito la backslash 0 personaggio che conosco Ho raggiunto la fine della stringa. E poi ho intenzione di continuare a scorrendo la stringa, aggiungendo strstr [j] per riassumere, e poi al fine della giornata andando a tornare somma mod HASH_MAX. 

Fondamentalmente tutto questo hash Funzione sta facendo è sommando tutti i valori ASCII mia stringa, e quindi è tornare un codice hash modded by HASH_MAX. E 'probabilmente la dimensione della mia matrice, giusto? Non voglio essere sempre hash codici se la mia matrice è di dimensioni 10, Io non voglio essere sempre codici hash fuori 11, 12, 13, non riesco a mettere le cose in quelle posizioni della matrice, che sarebbe illegale. Mi piacerebbe soffro un segmentation fault. 

Ora qui è un altro rapido da parte. In generale si sta probabilmente non andare a vogliono scrivere le proprie funzioni di hash. In realtà è un po 'di un'arte, non una scienza. E ci sono un sacco che va in loro. Internet, come ho detto, è piena di veramente buono funzioni hash, e si dovrebbe utilizzare internet per trovare funzioni hash perché è davvero solo una specie di inutile perdita di tempo per creare il proprio. 

È possibile scrivere quelle semplici a scopo di test. Ma quando effettivamente intenzione di iniziare hashing dei dati e la memorizzazione in una tabella hash sei probabilmente andando a voler usare qualche funzione che è stato generato per te, che esiste su Internet. Se non tanto per essere sicuro per citare le tue fonti. Non c'è motivo per plagiare nulla qui. 

La comunità informatica è decisamente in crescita, e davvero i valori open source, ed è molto importante per citare le fonti in modo che la gente può ottenere attribuzione per il lavoro che sono facendo per il beneficio della comunità. Quindi, essere sempre sure-- e non solo per hash funzioni, ma in genere quando si utilizzare il codice da una fonte esterna, citare sempre la vostra fonte. Devi riconoscere il soggetto che ha fatto alcuni dei lavori in modo da non devi. 

OK quindi cerchiamo di rivisitare questo tabella di hash per un secondo. Questo è dove abbiamo lasciato dopo abbiamo inserito Giovanni e Paolo in questa tabella di hash. Vedete un problema qui? Si potrebbe vedere due. Ma in particolare, si fa vedere questo possibile problema? 

Cosa succede se Hash Ringo, e risulta che dopo la trasformazione che i dati tramite la funzione hash Ringo anche generato il codice hash 6. Ho già dati a hashcode-- posizione di matrice 6. Quindi è destinata probabilmente ad essere un po ' di un problema per me, ora, giusto? 

Noi chiamiamo questo una collisione. E la collisione si verifica quando due pezzi di dati attraversano lo stesso hash funzione di cedere lo stesso codice hash. Presumibilmente abbiamo ancora voglia di ottenere sia pezzi di dati nella tabella di hash, altrimenti non saremmo in esecuzione Ringo arbitrariamente attraverso la funzione hash. Noi presumibilmente vogliamo ottenere RINGO in tale matrice. 

Come lo facciamo, però, se lui e Paolo sia resa codice hash 6? Non vogliamo sovrascrivere Paul, vogliamo che Paul sia lì. Quindi abbiamo bisogno di trovare un modo per ottenere elementi nella tabella hash conserva ancora il nostro rapido inserimento e rapido sguardo in su. E un modo per affrontare il problema è quello di fare qualcosa chiamato scansione lineare. 

Utilizzando questo metodo, se abbiamo un collisione, beh, che cosa facciamo? Beh, non possiamo mettere in posizione dell'array 6, o qualunque codice hash è stato generato, Mettiamolo in codice hash più 1. E se questo è pieno di let metterlo in codice hash più 2. Il vantaggio di questo essere se e ' Non esattamente dove pensiamo che è, e dobbiamo cominciare a cercare, forse non dobbiamo andare troppo lontano. Forse noi non dobbiamo cercare tutti gli n elementi della tabella hash. Forse dobbiamo cercare un paio di loro. 

E così siamo ancora tendente quel caso media prossima a 1 vs vicino ai n, quindi forse sarà il lavoro. Quindi cerchiamo di vedere come questo potrebbe funzionare nella realtà. E vediamo se forse possiamo scoprire il problema che potrebbe verificarsi qui. 

Diciamo che Hash Bart. Così ora stiamo andando a correre una nuova serie di stringhe tramite la funzione di hash, e corriamo Bart attraverso l'hash Funzione, otteniamo codice hash 6. Diamo uno sguardo, vediamo 6 è vuoto, in modo che possiamo mettere Bart lì. 

Ora ci hash Lisa e che genera anche codice hash 6. Bene, ora che stiamo usando questo lineare metodo partiamo alle 6 sondare, vediamo che 6 è piena. Non possiamo mettere Lisa in 6. Allora dove andiamo? Andiamo a 7. 7 di vuoto, in modo che funziona. Quindi cerchiamo di mettere Lisa lì. 

Ora ci hash Omero e otteniamo 7. OK bene sappiamo che 7 di piena ora, in modo da non possiamo mettere Omero lì. Così andiamo a 8. È disponibile 8? Sì, e 8 di quasi il 7, quindi se dobbiamo iniziare a cercare siamo non andando ad avere per andare troppo lontano. E così mettiamo Omero a 8. 

Ora ci hash Maggie e restituisce 3, grazie al cielo siamo in grado di mettere solo Maggie lì. Non abbiamo a che fare ogni sorta di sondare per questo. Ora noi Hash Marge, e Marge restituisce anche 6. 

Ebbene 6 è pieno, 7 è pieno, 8 è piena, 9, va bene grazie a Dio, 9 è vuoto. Posso mettere Marge a 9. Già possiamo vedere che stiamo iniziando di avere questo problema in cui ora siamo iniziando ad allungare le cose tipo di lontano dalle loro codici hash. E che theta di 1, questa media caso di essere costante di tempo, sta iniziando a diventare un po 'more-- iniziando a tendere un po 'più verso theta di n. Stiamo iniziando a perdere quel vantaggio di tabelle hash. 

Questo problema che abbiamo appena visto è qualcosa chiamato clustering. E ciò che è veramente male su il clustering è che una volta ora avere due elementi che sono fianco a lato si rende ancora più probabile, si ha il doppio possibilità, che si sta andando di avere un altro scontro con quel gruppo, e il cluster crescerà di uno. E ti tenere a crescere e crescere la probabilità di avere una collisione. E alla fine è proprio così male da non classificare i dati a tutti. 

L'altro problema è se siamo ancora, e finora fino a questo punto, che abbiamo appena sorta di capire che cosa una tabella hash è, abbiamo ancora spazio solo per 10 corde. Se vogliamo continuare a hash i cittadini di Springfield, siamo in grado di ottenere solo 10 di loro in là. E se cerchiamo di aggiungere un 11 ° o 12, non abbiamo un posto dove metterli. Potremmo essere in Spinning Around cerchi cercando di trovare un punto vuoto, e noi forse si blocca in un ciclo infinito. 

Quindi questo tipo di presta all'idea di una cosa chiamata concatenamento. E questo è dove stiamo andando a portare liste collegate torna in scena. Che cosa succede se invece di memorizzare solo i dati stessi nella matrice, ogni elemento della matrice potrebbe tenere più pezzi di dati? Beh, questo non ha senso, giusto? Sappiamo che una matrice solo è possibile hold-- ogni elemento di un array può contenere solo un pezzo di dati di tale tipo di dati. 

Ma cosa succede se quel tipo di dati è una lista collegata, giusto? Così che cosa se ogni elemento della matrice era un puntatore alla testa di una lista collegata? E allora potremmo costruire quelle liste concatenate e farle crescere arbitrariamente, perché liste concatenate consentono di crescere e ridurre molto di più flessibilità di un array fa. Che importa se ora usiamo, facciamo leva questo, giusto? Si comincia a coltivare queste catene da queste posizioni di matrice. 

Ora possiamo andare bene un infinito quantità di dati, o non infinito, una quantità arbitraria di i dati, nella nostra tabella hash senza mai incorrere in il problema di collisione. Abbiamo anche eliminato il clustering in questo modo. E ben sappiamo che quando inseriamo in una lista collegata, se vi ricordate dal nostro video su liste concatenate, singolarmente liste concatenate e liste doppiamente collegate, si tratta di una operazione di tempo costante. Stiamo solo aggiungendo alla parte anteriore. 

E per guardare in alto, ben sappiamo quello sguardo in una lista collegata può essere un problema, giusto? Dobbiamo per la ricerca in che dall'inizio alla fine. Non c'è nessun caso accesso in una lista collegata. Ma se invece di avere uno collegato lista in cui una ricerca sarebbe O di n, ora abbiamo 10 liste collegate, o 1.000 liste collegate, ora è O di n diviso 10, o O di n diviso per 1.000. 

E mentre stavamo parlando teoricamente sulla complessità ignoriamo costanti, nel vero mondo queste cose realmente importa, destra? Noi in realtà noteremo che ciò avvenga per eseguire 10 volte più veloce, o 1.000 volte più veloce, perché stiamo distribuendo una lunga catena in tutto 1.000 catene più piccole. E così ogni volta che dobbiamo cercare attraverso una di quelle catene che possiamo ignorare le 999 catene non ci preoccupiamo su, e basta cercare quello. 

Che è, in media, a essere 1000 volte più breve. E così siamo ancora sorta di tendente questo caso medio di essere costante di tempo, ma solo perché facciamo leva dividendo per qualche enorme fattore costante. Vediamo come questo potrebbe effettivamente guardare però. Quindi questa è stata la tabella di hash che abbiamo avuto prima abbiamo dichiarato una tabella hash che era in grado di memorizzare 10 stringhe. Non abbiamo intenzione di farlo più. Sappiamo già la limitazioni di quel metodo. Ora la nostra tabella di hash sarà un array di 10 nodi, puntatori ai capi di liste collegate. 

E in questo momento è nullo. Ognuno di questi 10 puntatori è nullo. Non c'è nulla nel nostro hash tavolo in questo momento. 

Ora cominciamo a mettere un po ' cose in questa tabella di hash. E vediamo come questo metodo andare a beneficio di noi un po '. Vediamo ora l'hashing Joey. Ti verrà eseguito la stringa Joey attraverso una funzione hash e torniamo 6. Beh, cosa facciamo adesso? 

Bene, ora si lavora con liste collegate, non stiamo lavorando con gli array. E quando stiamo lavorando con liste concatenate noi sappiamo che dobbiamo iniziare in modo dinamico assegnazione catene di spazio e di costruzione. Questo è una sorta di how-- questi sono il nucleo elementi di costruzione di una lista collegata. Quindi cerchiamo di dinamicamente allocare spazio per Joey, e poi facciamo lo aggiungiamo alla catena. 

Ora guardiamo quello che abbiamo fatto. Quando abbiamo hash Joey abbiamo ottenuto il codice hash 6. Ora il puntatore in posizione di matrice 6 punta alla testa di una lista collegata, e in questo momento è l'unica elemento di una lista collegata. E il nodo che lista collegata è Joey. 

Quindi, se abbiamo bisogno di guardare in alto Joey più tardi, abbiamo appena hash di nuovo Joey, otteniamo 6 di nuovo perché il nostro funzione hash è deterministica. E poi si parte in testa della lista collegata puntato a da posizione dell'array 6, e siamo in grado di iterare attraverso che cercando di trovare Joey. E se noi costruiamo il nostro hash efficacemente tavolo, e la nostra funzione di hash in modo efficace per distribuire bene i dati, in media ciascuno di quelli legati liste in ogni posizione dell'array sarà 1/10 delle dimensioni di se appena avuto come un unico enorme lista collegata con tutto ciò che contiene. 

Se distribuiamo quell'enorme collegati Lista in 10 liste collegate ogni lista sarà 1/10 delle dimensioni. E così 10 volte più veloce per la ricerca in. Quindi cerchiamo di farlo di nuovo. Vediamo ora l'hashing Ross. 

E diciamo Ross, quando lo facciamo il codice hash torniamo è 2. Bene, ora abbiamo allocare dinamicamente un nuovo nodo, abbiamo messo Ross in quel nodo, e noi diciamo ora posizione dell'array 2, invece di puntare su null, punta alla testa di un legato lista il cui unico nodo è Ross. E possiamo farlo ancora una volta, abbiamo può hash Rachel e ottenere codice hash 4. malloc un nuovo nodo, mettere Rachel il nodo, e dire una posizione di matrice 4 ora punta alla testa di una lista collegata la cui unico elemento sembra essere Rachel. 

OK ma cosa succede se abbiamo una collisione? Vediamo come gestiamo le collisioni utilizzando il metodo concatenazioni separate. Cerchiamo di eseguire l'hashing Phoebe. Otteniamo il codice hash 6. Nel nostro esempio precedente eravamo solo memorizzare le stringhe nella matrice. Questo è stato un problema. 

Noi non vogliamo clobber Joey, e abbiamo già visto che siamo in grado di ottenere un po 'di clustering problemi se cerchiamo di passo attraverso e sonda. Ma cosa succederebbe se solo tipo di trattare questo allo stesso modo, giusto? E 'proprio come aggiunta di un elemento alla testa di una lista collegata. Diamo spazio solo malloc per Phoebe. 

Diremo puntatore punti successivi di Phoebe al vecchio capo della lista collegata, e poi 6 punti solo per la nuovo capo della lista collegata. E ora guardiamo, abbiamo cambiato Phoebe in. Ora possiamo memorizzare due elementi con codice hash 6, e non abbiamo alcun problema. 

Questo è praticamente tutto c'è da concatenamento. E concatenamento è sicuramente il metodo che è sta per essere più efficace per voi se si memorizzano i dati in una tabella hash. Ma questa combinazione di array e liste concatenate insieme per formare una tabella hash veramente migliora notevolmente la vostra capacità per memorizzare grandi quantità di dati, e molto rapido ed efficiente ricerca attraverso tali dati. 

C'è ancora un altro struttura di dati là fuori che potrebbe anche essere un po ' migliore in termini di garantire che il nostro inserimento, cancellazione, e consultare le tabelle sono ancora più veloci. E vedremo che in un video su tentativi. Sono Doug Lloyd, questo è CS50.