[MUSIK SPELA] DOUG LLOYD: Vid det här laget du vet en hel del om matriser, och du vet en hel del om länkade listor. Och vi har att diskutera för- och nackdelar har vi diskuteras som länkade listor kan bli större och mindre, men de tar upp större storlek. Arrayer är mycket enklare att använda, men de är restriktiv i så mycket som vi måste ställa in storleken på uppsättningen i början och sedan är vi fastnat med det. 

Men det är, vi har ganska mycket uttömt alla våra ämnen om länkade listor och matriser. Eller har vi? Vi kanske kan göra något ännu mer kreativ. Och den sortens lånar tanken på en hash-tabell. 

Så i en hashtabell vi kommer att försöka kombinera en matris med en länkad lista. Vi kommer att ta fördelarna av matrisen, som random access, att kunna gå till array elementet 4 eller gruppelement 8 utan att iterera över. Det är ganska snabbt, eller hur? 

Men vi vill också ha våra data struktur kunna växa och krympa. Vi behöver inte, vi gör inte vill vara begränsad. Och vi vill kunna att lägga till och ta bort saker mycket lätt, vilket om ni minns, är mycket komplex med en array. Och vi kan kalla detta ny sak en hashtabell. 

Och om de genomförs på rätt sätt, vi sorts tar fördelarna med både data strukturer du redan har sett, arrayer och länkade listor. Infogning kan börja tenderar mot teta av en. Theta vi har inte riktigt diskuterat, men theta är bara det genomsnittliga fallet, vad som faktiskt kommer att hända. Du är inte alltid kommer att har det värsta scenariot, och du inte alltid kommer att ha bästa fall, så vad är den genomsnittliga scenariot? 

Väl en genomsnittlig inser in i en hash-tabell kan börja komma nära konstant tid. Och radering kan få nära till konstant tid. Och lookup kan få nära till konstant tid. That's-- vi inte har ett data struktur ännu som kan göra det, och så detta redan låter som en ganska stor sak. Vi har verkligen mildrat nackdelar med varje på egen hand. 

För att få detta resultat uppgradera men vi måste ompröva hur vi lägger data i strukturen. Specifikt vi vill att Uppgiften i sig att berätta för oss där det ska gå i strukturen. Och om vi då behöva se om det är i struktur, om vi behöver hitta det, vi vill titta på data igen och kunna effektivt med hjälp av data, slumpmässigt tillgång till den. Bara genom att titta på uppgifter bör vi ha en uppfattning om var vi exakt är kommer att hitta det i hashtabellen. 

Nu baksidan av en hash tabellen är att de är verkligen ganska dåliga på att beställa eller sortera data. Och faktum är att om du börjar att använda dem för att beställa eller sortera data du förlorar alla fördelar du tidigare hade när det gäller införande och radering. Tiden blir närmare theta n, och vi har i stort sett regredierat till en länkad lista. Och så vill vi bara använda hash tabeller om vi inte bryr sig om om data sorteras. För det sammanhang i vilket du kommer att använda dem i CS50 du förmodligen inte bryr att uppgifterna sorteras. 

Så en hashtabell är en kombination av två olika bitar som vi är bekant. Den första är en funktion, som vi brukar kalla en hashfunktion. Och det hashfunktion kommer att tillbaka vissa icke-negativt heltal, som vi brukar kalla en hashkod, OK? Den andra delen är en array, som är med förmåga att lagra data av den typ som vi vill placera in i datastrukturen. Vi kommer att vänta på länkad lista element för nu och bara börja med grunderna i en hash tabellen för att få huvudet runt det, och sedan kommer vi kanske att blåsa ditt sinne lite när vi kombinera arrayer och länklistor tillsammans. 

Den grundläggande idén om är vi ta några uppgifter. Vi kör dessa data genom hashfunktionen. Och så uppgifterna behandlas och det spottar ut ett nummer, OK? Och sedan med det numret lagrar vi bara data vi vill lagra i array på den platsen. Så till exempel har vi kanske denna hashtabell av strängar. Det har fått 10 element i det, så vi kan passa 10 strängar i det. 

Låt oss säga att vi vill hash John. Så Johannes som de data vi vill infoga i denna hash-tabell någonstans. Var ska vi säga? Väl typiskt med en array så långt vi förmodligen skulle uttrycka det i array plats 0. Men nu har vi denna nya hash funktion. 

Och låt oss säga att vi kör John genom denna hash-funktion och det är spottar ut 4. Ja, det är där vi är kommer att vilja sätta John. Vi vill sätta John i array plats 4, för om vi hash John igen-- låt oss säga senare vi vill söka och se om John existerar i denna hash table-- allt vi behöver göra körs det genom samma hash funktion, få nummer 4, och att kunna hitta John omedelbart i vår datastruktur. Det är ganska bra. 

Låt oss säga att vi nu göra detta igen, vi vill hash Paul. Vi vill lägga till Paul in i denna hashtabell. Låt oss säga att den här gången kör vi Paul genom hashfunktionen, den hashkod som genereras är sex. Nu kan vi sätta Paul i matrisen plats 6. Och om vi måste se upp om Paul är i detta hashtabell, allt vi behöver göra är att köra Paul genom hashfunktionen igen och vi kommer att få 6 igen. 

Och sedan ser vi bara på array plats 6. Är Paul det? Om så är fallet, är han i hashtabellen. Är Paul inte det? Han är inte i hashtabellen. Det är ganska enkelt. 

Nu hur definierar du en hashfunktion? Jo det finns egentligen ingen gräns för hur antal möjliga hashfunktioner. I själva verket finns det ett antal riktigt, riktigt bra på internet. Det finns ett antal riktigt, riktigt dåliga på internet. Det är också ganska lätt att skriva en dålig. 

Så vad gör en bra hashfunktion, eller hur? Tja en bra hashfunktion bör använder endast de data som hashas, och alla data som hashas. Så att vi inte vill använda anything-- vi inte införlivar något annanstans än uppgifterna. Och vi vill använda alla data. Vi vill inte bara använda en bit det vill vi använda allt. En hashfunktion bör också vara deterministisk. Vad betyder det? Jo det innebär att varje gång vi passera exakt samma bit data i hashfunktionen vi alltid få samma hashkod ut. Om jag passerar John i hashfunktion jag kommer ut 4. Jag skulle kunna göra det 10000 gånger och jag kommer alltid att få 4. Så inga slumptal effektivt kan vara inblandade i vår hash tables-- i våra hashfunktioner. 

En hashfunktion bör också likformigt distribuera data. Om varje gång du kör data via hashfunktion du får hashkod 0, det är nog inte så stor, eller hur? Du vill förmodligen stora ett intervall av hash-koder. Också saker kan spridas ut hela tabellen. Och det skulle vara bra om verkligen liknande data, som John och Jonathan, kanske spreds ut att väga olika platser i hashtabellen. Det skulle vara en trevlig fördel. 

Här är ett exempel på en hash-funktion. Jag skrev ett upp tidigare. Det är inte en särskilt bra hash-funktion av skäl som inte riktigt bära gå in just nu. Men ser du vad som händer här? Det verkar som om vi förklara en variabel kallas summa och ställa den lika med 0. Och sedan tydligen jag gör något så länge som strstr [j] är icke lika att bakåtstreck 0. Vad gör jag där? 

Detta är i grunden bara en annan sättet att genomföra [? strl?] och detektera när du har nått slutet av strängen. Så jag behöver inte faktiskt beräkna längden på strängen, Jag bara använda när jag träffade backslash 0 tecken jag vet Jag har nått slutet av strängen. Och sedan kommer jag att hålla iterera genom den strängen, sätta strstr [j] för att summera och sedan på slutet av dagen kommer att återvända summan mod HASH_MAX. 

I princip allt detta hash funktionen gör är att lägga upp alla ASCII-värdena av min string, och då är det återvända någon hashkod modded av HASH_MAX. Det är förmodligen storlek min samling, eller hur? Jag vill inte att få hash koder om min samling är av storlek 10, Jag vill inte vara att få ut hash-koder 11, 12, 13, jag kan inte sätta saker i dessa placeringar av arrayen, det skulle vara olagligt. Jag skulle drabbas av en segmentering fel. 

Nu här är en annan snabbt åt sidan. Generellt du förmodligen inte kommer att vill skriva egna hashfunktioner. Det är faktiskt lite av en konst, inte en vetenskap. Och det finns en hel del som går in i dem. Internet, som sagt, är full riktigt bra hashfunktioner, och du bör använda Internet för att hitta hash funktioner eftersom det är verkligen bara typ av en onödig slöseri med tid att skapa din egen. 

Du kan skriva enkla sådana för teständamål. Men när du faktiskt kommer att börja hashing uppgifter och lagra den i en hashtabell du förmodligen kommer att vilja att använda någon funktion som genererades för dig, finns det på internet. Om du bara vill vara säker för att citera dina källor. Det finns ingen anledning att plagiera något här. 

Datorn vetenskapliga samfundet är definitivt växer, och verkligen värden öppen källkod, och det är verkligen viktigt för att citera dina källor så att människor kan få erkännande för det arbete som de är gör till förmån för samhället. Så alltid vara sure-- och inte bara för hash funktioner, men i allmänhet, när du Använd koden från en extern källa, alltid nämna källan. Ge kredit till den person som gjorde en del av arbetet så att du inte behöver. 

OK så låt oss återvända till denna hashtabell för en sekund. Det är där vi lämnade rabatt när vi införas John och Paulus in i denna hashtabell. Ser du ett problem här? Du kan se två. Men framför allt, gör du se risken för detta? 

Vad händer om jag hash Ringo, och det visar sig att efter bearbetning att data genom hashfunktionen Ringo genererade också hashkod 6. Jag har redan fått uppgifter på hashcode-- array läge 6. Så det är förmodligen kommer att bli lite av ett problem för mig nu, eller hur? 

Vi kallar detta en kollision. Och kollisionen inträffar när två datadelar löper genom samma hash funktion ger samma hashkod. Förmodligen vi fortfarande vill få både bitar av data i hashtabellen, annars skulle vi inte vara igång Ringo godtyckligt genom hashfunktionen. Vi vill förmodligen för att få RINGO in den arrayen. 

Hur gör vi det ändå, om han och Paul både avkastning hashkod 6? Vi vill inte skriva Paul, Vi vill att Paul att vara där också. Så vi måste hitta ett sätt att få element i hash tabellen som fortfarande bevarar vår snabb införande och snabb titt upp. Och ett sätt att ta itu med det är att göra något som kallas linjär sondering. 

Med denna metod om vi har en kollision, ja, vad gör vi? Väl vi inte kan sätta honom i array plats 6, eller vad hashkod genererades, låt oss sätta honom på hashkod plus 1. Och om det är fullt låt oss satte honom i hashkod plus 2. Fördelen med denna varelse om han är inte precis där vi tror att han är, och vi måste börja söka, kanske vi behöver inte gå för långt. Vi kanske inte behöver söka alla n element i hashtabellen. Kanske måste vi söka ett par av dem. 

Och så vi fortfarande går mot att den genomsnittliga fall vara nära 1 vs nära n, så kanske det kommer att fungera. Så låt oss se hur detta skulle kunna fungera i verkligheten. Och låt oss se om kanske vi kan upptäcka det problem som kan uppstå här. 

Låt oss säga att vi hash Bart. Så nu ska vi köra en ny uppsättning strängar genom hashfunktionen, och vi kör Bart genom hash funktionen, vi får hashkod 6. Vi tar en titt, ser vi 6 tom, så att vi kan sätta Bart där. 

Nu hash vi Lisa och att även genererar hashkod 6. Tja nu när vi använder detta linjär sondering metod vi börjar vid 6, vi se att sex är fullt. Vi kan inte sätta Lisa 6. Så där går vi? Låt oss gå till 7. 7 är tomt, så det fungerar. Så låt oss sätta Lisa där. 

Nu hash vi Homer och vi får 7. OK väl vi vet att 7 fullständiga nu, så att vi inte kan sätta Homer där. Så låt oss gå till 8. Är 8 Tillgänglig? Ja, och 8: s nära 7, så om Vi måste börja söka vi är inte kommer att behöva gå för långt. Och så låt oss sätta Homer på 8. 

Nu är vi hash Maggie och returnerar 3, tack och lov vi kan bara sätta Maggie där. Vi behöver inte göra något sorts sondering för det. Nu hash vi Marge, och Marge återvänder också 6. 

Väl 6 är full, 7 är full, 8 är full, 9, okej tack och lov, 9 är tom. Jag kan sätta Marge på 9. Redan kan vi se att vi börjar att ha det här problemet där nu är vi börjar sträcka saker slag av långt borta från sina hash-koder. Och att teta av 1, i snitt som händelse av att vara konstant tid, börjar få lite more-- börjar tenderar lite mer mot theta n. Vi börjar att förlora det fördel av hashtabeller. 

Detta problem som vi såg bara är något som kallas kluster. Och vad är egentligen dåligt om kluster är att när du nu har två element som är sida vid sida det gör det ännu mer troligt, du har dubbelt chans, att du kommer att ha en annan kollision med detta kluster, och klustret kommer att växa med en. Och du ska hålla växer och växer dina chanser att ha en kollision. Och till slut är det lika illa som inte sortera data alls. 

Det andra problemet är dock att vi fortfarande, och hittills fram till denna punkt, Vi har bara varit sorts förstå vad en hash-tabell är, vi fortfarande bara har plats för 10 strängar. Om vi ​​vill fortsätta att hash medborgarna i Springfield, Vi kan bara få 10 av dem där. Och om vi försöker lägga till en 11: e eller 12: e, vi har inte en plats att sätta dem. Vi kunde bara snurra runt i cirklar att försöka hitta en tom plats, och vi kanske fastnar i en oändlig loop. 

Så här sortens lånar till idén av något som kallas kedja. Och det är där vi kommer att föra länkade listor tillbaka in i bilden. Tänk om istället för att lagra bara själva uppgifterna i arrayen, varje element i arrayen kunde hålla flera stycken av data? Tja det inte är vettigt, eller hur? Vi vet att en array endast kan hold-- varje element i en array kan bara hålla ett stycke av uppgifter om den datatypen. 

Men vad händer om den datatypen är en länkad lista, eller hur? Så vad händer om varje element i gruppen var en pekare till chefen för en länkad lista? Och då kunde vi bygga de länkade listor och odla dem godtyckligt, eftersom länkade listor tillåter oss att växa och krympa mycket mer flexibelt än en array gör. Så vad händer om vi nu använda, vi utnyttja denna, rätt? Vi börjar att odla dessa kedjor av dessa array platser. 

Nu kan vi passar en oändlig mängden data, eller inte oändlig, en godtycklig mängd av data in i vår hashtabellen utan att någonsin köra in problemet för kollision. Vi har också elimineras kluster genom att göra detta. Och väl vi vet att när vi sätter i en länkad lista, om du minns från vår video på länkade listor, var för sig länkade listor och dubbelt länkade listor, det är en ständig time operation. Vi bara lägga till fronten. 

Och för uppslags, väl vi vet att slå upp i en länkad lista kan vara ett problem, eller hur? Vi måste söka igenom det från början till slut. Det finns ingen slumpmässig åtkomst i en länkad lista. Men om istället för att ha en länkad lista där en uppslagning skulle vara O för n, vi nu har 10 länkade listor, eller 1000 länkade listor, nu är det O n dividerat med 10, eller O av n dividerat med 1000. 

Och medan vi pratade teoretiskt om komplexitet vi bortser från konstanter, i den verkliga värld dessa saker faktiskt roll, höger? Vi faktiskt kommer att märka att detta sker att springa 10 gånger snabbare, eller 1000 gånger snabbare, eftersom vi distribuerar en lång kedja över 1.000 mindre kedjor. Och så varje gång vi måste söka genom en av dessa kedjor vi kan för ignorera de 999 kedjorna vi inte bryr om, och bara söka den. 

Vilket är i genomsnitt vara 1000 gånger kortare. Och så är vi fortfarande sorts går mot denna genomsnittliga fallet av att vara konstant tid, men bara för att vi är hävstångseffekt dividera med några stora konstant faktor. Låt oss se hur detta kanske faktiskt ser dock. Så det här var hash tabell vi hade innan vi förklarade en hash tabell som var kan lagra 10 strängar. Vi kommer inte att göra det längre. Vi vet redan begränsningar av denna metod. Nu har vår hash bord kommer att bli en matris med 10 noder, pekare till cheferna för länkade listor. 

Och just nu är det noll. Var och en av dessa 10 pekare är noll. Det finns inget i vår hash tabellen just nu. 

Nu börjar sätta några saker i denna hash-tabell. Och låt oss se hur denna metod är kommer att gynna oss lite. Låt oss nu hash Joey. Vi kommer att köra strängen Joey genom en hash funktion och vi återvänder 6. Och vad gör vi nu? 

Väl arbetar nu med länkade listor, vi inte arbetar med arrayer. Och när vi jobbar med länkade listor vi vet att vi måste börja dynamiskt tilldelning av utrymme och byggkedjor. Det blir liksom how-- de är kärnan element för att bygga en länkad lista. Så låt oss dynamiskt allokera utrymme för Joey, och sedan ska vi lägga honom till kedjan. 

Så nu ser vad vi har gjort. När vi hash Joey vi fick hashkod 6. Nu pekaren på array plats 6 pekar på huvudet på en länkad lista, och just nu är det den enda element i en länkad lista. Och noden i den länkad lista är Joey. 

Så om vi behöver slå upp Joey senare, vi bara hash Joey igen, vi får 6 igen eftersom vår hashfunktion är deterministisk. Och sedan börjar vi i spetsen av den länkade listan pekade till genom array plats 6, och vi kan iterera över att försöka hitta Joey. Och om vi bygger vår hashtabell effektivt, och vår hashfunktion effektivt att distribuera data väl, i genomsnitt vart och ett av de länkade listor vid varje array plats kommer att vara 1/10 storleken på om vi bara haft det som en enda stor länkad lista med allt i den. 

Om vi ​​distribuerar den enorma länkade Listan över 10 länkade listor varje lista kommer att vara 1/10 storlek. Och därmed 10 gånger snabbare att söka igenom. Så låt oss göra det igen. Låt oss nu hash Ross. 

Och låt oss säga Ross, när vi gör det hash-kod vi får tillbaka är 2. Nåväl vi dynamiskt allokera en nya noden, sätter vi Ross i den noden, och vi säger nu array plats 2, i stället för att peka på null, pekar på huvudet av en länkad lista vars enda nod är Ross. Och vi kan göra det här en gång till, vi kan hash Rachel och få hashkod 4. malloc en ny nod, sätta Rachel i noden, och säger en array plats 4 pekar nu mot huvudet av en länkad lista vars enda element råkar vara Rachel. 

OK, men vad händer om Vi har en kollision? Låt oss se hur vi hanterar kollisioner med användning av separata följning. Låt oss hash Phoebe. Vi får hashkod 6. I vårt tidigare exempel var vi bara lagring av strängar i arrayen. Detta var ett problem. 

Vi vill inte clobber Joey, och vi har redan sett att vi kan få lite klustring problem om vi försöker och steg genom och sond. Men vad händer om vi bara typ av behandla detta på samma sätt, eller hur? Det är precis som att lägga ett element till chefen för en länkad lista. Låt oss bara malloc utrymme för Phoebe. 

Vi ska säga Phoebes nästa pekaren pekar till den gamla chefen för den länkade listan, och sedan 6 bara pekar på ny chef för den länkade listan. Och nu ser har vi ändrat Phoebe in. Vi kan nu lagra två element med hashkod 6, och vi har inte några problem. 

Det är ganska mycket alla finns att kedja. Och kedja är definitivt den metod som är kommer att vara mest effektiva för dig om du lagra data i en hash tabell. Men denna kombination av arrayer och länkade listor tillsammans för att bilda en hashtabell verkligen dramatiskt förbättrar din förmåga att lagra stora mängder data, och mycket snabbt och effektivt söka genom dessa uppgifter. 

Det finns fortfarande ett mer datastruktur ute som kanske till och med vara lite bättre när det gäller att garantera att vår insertion, deletion, och slå upp tider är ännu snabbare. Och vi ser att i en video på försök. Jag är Doug Lloyd, är detta CS50.