[Muziek] DOUG LLOYD: Door nu je weet veel over arrays, en je weet veel over gelinkte lijsten. En we hebben bespreken voors en tegens, we hebben besproken die lijsten verbonden kunnen groter en kleiner, maar ze nemen meer grootte. Arrays zijn veel eenvoudiger te gebruiken, maar ze zijn beperkt in zoverre als we de grootte van de vastgestelde de matrix aan het begin en dan zijn we vast te zitten. 

Maar dat is, we hebben vrij veel uitgeput al onze topics over gelinkte lijsten en arrays. Of hebben we? Misschien kunnen we iets doen nog meer creatieve. En dat soort leent het idee van een hash tabel. 

Dus in een hash tafel we gaan proberen combineren een array met een gekoppelde lijst. We gaan om de voordelen te nemen van de array, zoals random access, zijn om gewoon naar serie staat element 4 of array-element 8 zonder over herhalen. Dat is behoorlijk snel, toch? 

Maar we willen ook onze gegevens structuur kunnen groeien en krimpen. We niet nodig, we doen niet willen worden beperkt. En we willen kunnen toe te voegen en de dingen te verwijderen heel gemakkelijk, wat als je te herinneren, is zeer complex met een matrix. En we kunnen dit noemen nieuw ding een hash tabel. 

En indien correct geïmplementeerd, we soort nemen de voordelen van beide data structuren die je al hebt gezien, arrays en gelinkte lijsten. Inbrengen kan beginnen neigen naar theta van 1. Theta we hebben niet echt besproken, maar theta is slechts het gemiddelde geval, wat er werkelijk gaat gebeuren. Je bent niet altijd gaat om hebben het ergste geval, en je bent niet altijd zal hebben het beste geval, dus wat is de gemiddelde scenario? 

Goed gemiddeld insertie in een hash table kan beginnen om dicht bij constante tijd te krijgen. En verwijdering kan krijgen dicht bij constante tijd. En lookup kan krijgen dicht bij constante tijd. That's-- we geen gegevens structuur maar die kan dat doen, en zo dit al klinkt als een vrij groot ding. We hebben echt verzacht de nadelen van elk op zijn eigen. 

Om deze prestaties te krijgen upgraden hoewel, we moeten nadenken over hoe we voegen gegevens in de structuur. Concreet willen we de gegevens zelf om ons te vertellen waar het moet gaan in de structuur. En als we moeten dan om te zien of het in de structuur, als we het nodig om het te vinden, we willen kijken naar de data weer en in staat zijn om effectief, met de data, willekeurig toegang toe. Enkel door de gegevens die we moeten hebben een idee van waar we precies zijn gaan om het te vinden in de hash tabel. 

Nu het nadeel van een hash tabel is dat ze echt vrij slecht bij het bestellen of het sorteren van data. En in feite, als je begint om ze te gebruiken om te bestellen of sorteren gegevens verlies je alle voordelen die u eerder had in termen van inbrengen en verwijderen. De tijd wordt dichter bij theta van n, en we hebben eigenlijk regressie in een gekoppelde lijst. En dus we willen alleen hash gebruiken tafels als we niet de zorg over of de data wordt gesorteerd. Voor de context waarin u zult ze te gebruiken in CS50 u waarschijnlijk niet schelen dat de gegevens gesorteerd. 

Dus een hash tabel is een combinatie twee afzonderlijke stukken waarmee we vertrouwd zijn. De eerste is een functie, die we meestal noemen een hash-functie. En dat de hash-functie gaat terug een aantal niet-negatieve integer, die we meestal noemen een hashcode, OK? Het tweede stuk is een array, dat is geschikt voor het opslaan van gegevens van het type dat we willen plaatsen in de gegevensstructuur. We zullen af ​​te houden op de gelinkte lijst element voor nu en gewoon beginnen met de basis van een hash tabel om je hoofd te krijgen rond het, en dan zullen we misschien te blazen je geest een beetje toen we combineren arrays en lijsten samen. 

Het basisidee al is dat we een aantal gegevens te nemen. We lopen dat gegevens via de hash-functie. Zo worden de gegevens verwerkt en het spuugt een nummer, OK? En daarna met dat nummer we alleen de gegevens op te slaan we willen opslaan in de matrix op die locatie. Zo bijvoorbeeld hebben we misschien Deze hash tabel met strings. Het heeft 10 elementen in, dus kunnen we 10 snaren passen daarin. 

Laten we zeggen dat we willen hash John. Dus John als de gegevens die we willen invoegen in deze hash tafel ergens. Waar gaan we het? Goed typisch met een serie tot nu toe waarschijnlijk wij zou het in serie locatie 0. Maar nu hebben we deze nieuwe hash-functie. 

En laten we zeggen dat we lopen John door middel van deze hash-functie en het is spuugt 4. Nou, dat is waar we zijn gaat willen John zetten. Wij willen John in serie plaats zetten 4, want als we hash John again-- laten we zeggen dat we later wilt zoeken en te zien Als John bestaat in deze hash table-- alles wat we moeten doen wordt gerund het door dezelfde hash functie, ontvang de nummer 4, en in staat zijn om John te vinden onmiddellijk onze gegevensstructuur. Dat is vrij goed. 

Laten we zeggen dat we dit nu doen nogmaals, we willen hash Paul. We willen Paul toevoegen in deze hash tabel. Laten we zeggen dat we deze keer draaien Paul door de hash-functie, de hashcode die wordt gegenereerd is 6. Nou nu kunnen we Paul zetten in de array locatie 6. En als we moeten opzoeken of Paul is in deze hash tabel, alles wat we moeten doen is lopen Paul door de hash-functie weer en we gaan er weer uit te krijgen 6. 

En dan hebben we alleen kijken op rij plaats 6. Paul is er? Als dat zo is, hij is in de hash tabel. Paul is er niet? Hij is niet in de hash tabel. Het is vrij eenvoudig. 

Nu hoe maak je een hash-functie te definiëren? Nou er is echt geen limiet aan het aantal mogelijke hashfuncties. In feite is er een aantal echt, echt goede op het internet. Er is een aantal echt, echt slecht die op het internet. Het is ook vrij gemakkelijk een slechte schrijven. 

Dus wat maakt een goede hash-functie, toch? Wel een goede hash-functie moet gebruik alleen de gegevens die worden hashed, en alle gegevens worden hashed. Dus we willen niet anything-- gebruiken we hebben niets te nemen anders dan de gegevens. En we willen alle gegevens te gebruiken. We willen niet gewoon gebruik maken van een stuk van het, we willen al het te gebruiken. Een hash-functie moet Ook deterministisch zijn. Wat betekent dat? Nou, het betekent dat elke keer als we passeren exact dezelfde stuk van de gegevens in de hash-functie die we altijd krijgt dezelfde hashcode uit. Als ik langs John in de hash-functie ik uit 4. Ik moet in staat zijn om dat te doen 10.000 tijden en ik zal altijd 4. Dus geen willekeurige getallen effectief kunnen worden betrokken bij onze hash tables-- in onze hash functies. 

Een hash-functie moet ook uniform te verdelen data. Als elke keer dat u gegevens lopen door de hash-functie krijg je de hashcode 0, dat is waarschijnlijk niet zo groot, toch? Wilt u waarschijnlijk grote een bereik van hash codes. Ook dingen kunnen worden verspreid uit de hele tafel. En ook het zou geweldig zijn als echt gelijkwaardig, zoals John en Jonathan, misschien werden verspreid te wegen verschillende lokaties in de hashtabel. Dat zou een mooi voordeel. 

Hier is een voorbeeld van een hash-functie. Ik schreef dit één eerder. Het is niet een bijzonder goede hash-functie om redenen die niet echt doen dragen in te gaan op dit moment. Maar zie je wat er hier aan de hand? Het lijkt alsof we waarbij een variabele genoemd bedrag en de oprichting ervan gelijk is aan 0. En dan blijkbaar ben ik iets te doen zolang strstr [j] is niet gelijk om Backslash 0. Wat ben ik daar aan het doen? 

Dit is eigenlijk gewoon een ander manier van uitvoering [? strl?] en detecteren wanneer je hebt aan het einde van de string. Dus ik eigenlijk niet hoeft te berekenen van de lengte van de tekenreeks Ik ben gewoon met behulp van toen ik raakte de backslash 0 karakter ik weet Ik heb het einde van de string bereikt. En dan ga ik om te blijven itereren door middel van die string, toevoeging strstr [j] te vatten, en dan aan het einde van de dag gaat naar som mod terug HASH_MAX. 

In principe al deze hash functie doet is het toevoegen van up alle waarden van ASCII mijn reeks, en dan is het terugkerende sommige hashcode modded door HASH_MAX. Het is waarschijnlijk de grootte mijn array, toch? Ik wil niet te krijgen hash codes als mijn array is van maat 10, Ik wil niet te krijgen out hash codes 11, 12, 13, ik kan geen dingen te zetten in de locaties van de array, dat onwettig zou zijn. Ik zou lijden aan een segmentation fault. 

Nu is hier nog snel opzij. Over het algemeen ben je waarschijnlijk niet van plan om wilt u uw eigen hash functies te schrijven. Het is eigenlijk een beetje een kunst, geen wetenschap. En er is veel dat gaat in hen. Het internet, zoals ik al zei, is vol echt goede hash functies, en je moet het internet te gebruiken vinden hash functies, want het is echt gewoon een soort van een onnodige verspilling van tijd om je eigen te maken. 

U kunt eenvoudige degenen schrijven voor testdoeleinden. Maar als je daadwerkelijk gaat start hashing databank slaan in een hash table je bent waarschijnlijk gaat te willen met een functie die is gegenereerd gebruiken voor u, dat bestaat op het internet. Als je gewoon zeker om uw bronnen te citeren. Er is geen reden om plagiaat hier iets. 

De computer science gemeenschap is zeker groeien, en echt waarden open source, en het is echt belangrijk om uw bronnen citeren, zodat mensen kan attributie krijgen voor het werk dat ze doet in het voordeel van de gemeenschap. Dus altijd sure-- zijn en niet alleen voor hash functies, maar over het algemeen bij Gebruik de code van een externe bron, altijd citeren uw bron. Krediet aan de persoon die wel deel van het werk, zodat je niet hoeft te doen. 

OK dus laten we dit opnieuw hash tafel voor een tweede. Dit is waar we vertrokken off nadat we gestoken John en Paul in deze hash tabel. Heeft u een probleem hier te zien? Zie je misschien twee. Maar in het bijzonder, heb je zie dit mogelijk probleem? 

Wat als ik hash Ringo, en het blijkt dat na de verwerking dat gegevens via de hash-functie Ringo gegenereerd ook de hashcode 6. Ik heb al gegevens op hashcode-- scala locatie 6. Dus het is waarschijnlijk gaan om een ​​beetje te zijn een probleem voor mij nu, toch? 

We noemen dit een botsing. De botsing optreedt wanneer twee stukjes data lopen via dezelfde hash functie op dezelfde hashcode. Vermoedelijk willen we nog steeds allebei stukken van de gegevens in de hash-tabel, anders zouden we niet worden uitgevoerd Ringo arbitrair door de hash-functie. We willen vermoedelijk te krijgen Ringo in die array. 

Hoe doen we het wel, als hij en Paul zowel de opbrengst hashcode 6? We willen niet overschrijven Paul, we willen Paulus om daar te zijn. Dus we moeten een manier vinden om te krijgen elementen in de hash tabel die behoudt nog steeds onze snelle inbrengen en snelle blik omhoog. En een manier om te gaan met het is om een zogenaamde lineaire indringende doen. 

Met deze methode als we een botsing, nou ja, wat doen we? Goed we kunnen hem niet in serie locatie 6, of wat hashcode gegenereerd, laten we hem hashcode plus 1. En als dat vol laten we zet hem in hashcode plus 2. Het voordeel hiervan is als hij niet precies waar we denken dat hij is, en we moeten beginnen met zoeken, Misschien hoeven we niet te ver te gaan. Misschien hebben we niet hoeven te zoeken alle n elementen van de hash-tabel. Misschien moeten we zoeken een paar van hen. 

En zo zijn we nog steeds neigt naar dat de gemiddelde geval dicht bij 1 vs dicht bij n, dus misschien dat zal werken. Dus laten we zien hoe dit zou kunnen werken in de werkelijkheid. En laten we kijken of misschien kunnen we detecteren het probleem dat hier optreden. 

Laten we zeggen dat we hash Bart. Dus nu gaan we een nieuwe set draaien snaren door de hash-functie, en lopen we Bart door de hash functie, krijgen we hashcode 6. We nemen een kijkje, zien we 6 leeg, dus we kunnen Bart daar te zetten. 

Nu hash we Lisa en dat genereert ook hashcode 6. Nou nu dat we met behulp van deze lineaire indringende methode beginnen we op 6, we zien dat 6 vol. We kunnen niet zetten Lisa in 6. Dus waar gaan we heen? Laten we naar 7. 7's leeg, dus dat werkt. Dus laten we Lisa daar. 

Nu hash we Homer en we krijgen 7. OK goed we weten dat 7 volledige nu, dus we kunnen niet daar te zetten Homer. Dus laten we naar 8. 8 is beschikbaar? Ja, en 8, dicht bij 7, dus als we moeten beginnen met zoeken we niet van plan te hebben om te ver te gaan. En zo laten we Homer 8. 

Nu hash we Maggie en retourneert 3, godzijdank kunnen we gewoon Maggie daar. We hoeven niet elke doen soort indringende voor. Nu hash we Marge, en Marge keert ook 6. 

Goed 6 vol, vol 7, 8 vol is, 9, oke dank God, 9 is leeg. Ik kan Marge zetten op 9. Nu al kunnen we zien dat we beginnen om dit probleem, waar nu zijn we hebben begint om dingen soort rekken van ver weg van hun hash codes. En dat theta van 1, dat de gemiddelde Bij constant tijd, begint een beetje more-- krijgen begint een beetje meer de neiging richting theta van n. We beginnen te verliezen dat voordeel van hash tabellen. 

Dit probleem dat we net zagen is iets genaamd clustering. En wat is er echt slecht over clustering is dat zodra u nu twee elementen die kant zijn door kant maakt het nog waarschijnlijker, je moet het dubbele van de kans, dat je gaat nog een botsing hebben met die cluster, en het cluster zal groeien met een. En je zult blijven groeien en groeien je kans op een botsing. En uiteindelijk het is net zo slecht zo niet sorteren van de gegevens helemaal. 

Het andere probleem is echter dat we stil en zo ver op dit punt, we hebben net soort geweest begrijpen wat een hash-tabel is, we nog steeds slechts ruimte voor 10 snaren. Als we willen blijven hash de inwoners van Springfield, kunnen we alleen maar 10 van hen in. En als we proberen en voeg een 11e of 12e, we hebben geen plaats om ze te zetten. We konden gewoon spinnen rond in cirkels proberen om een ​​lege plek te vinden, en we misschien komen te zitten in een oneindige lus. 

Dus dit soort leent aan het idee van iets genaamd chaining. En dit is waar we gaan brengen gelinkte lijsten terug in beeld. Wat als in plaats van het opslaan van slechts de gegevens zelf in de array, elk element van de array kan Houd meerdere stukken van gegevens? Nou, dat heeft geen zin, toch? We weten dat een array kan alleen hold-- elk element van een array kan slechts één stuk van gegevens van dat soort gegevens. 

Maar wat als dat soort data is een gelinkte lijst, toch? Dus wat als elke element van de array was een verwijzing naar het hoofd van een gekoppelde lijst? En dan kunnen we bouwen die verbonden lijsten en groeien ze willekeurig, omdat gelinkte lijsten toestaan ons te groeien en krimpen veel meer flexibeler dan een matrix doet. Dus wat als we nu gebruiken, We benutten deze, toch? We beginnen deze ketens groeien uit deze reeks locaties. 

Nu kunnen we passen een oneindige hoeveelheid gegevens of niet oneindig, een willekeurig aantal data, in onze hash table zonder ooit te lopen in het probleem van de botsing. We hebben ook geëlimineerd clustering door dit te doen. En goed we weten dat wanneer we voegen in een gelinkte lijst, als je herinneren van onze video op gelinkte lijsten, afzonderlijk gelinkte lijsten en dubbel gelinkte lijsten, het is een constante tijd operatie. We gewoon toe te voegen aan de voorzijde. 

En voor het opzoeken, goed we weten die opzoeken in een gekoppelde lijst kan een probleem zijn, toch? We moeten zoeken door middel van het van begin tot einde. Er is geen willekeurige toegang in een gekoppelde lijst. Maar als plaats van één gekoppelde overzicht waar een lookup O van n zou zijn, we hebben nu 10 gelinkte lijsten, of 1000 gelinkte lijsten, Nu is het O n gedeeld door 10, of O n gedeeld door 1000. 

En terwijl we aan het praten waren theorie over de complexiteit We negeren constanten in de echte wereld deze dingen eigenlijk uit, toch? We eigenlijk zult merken dat dit gebeurt tot 10 keer sneller te lopen, of 1000 keer sneller, omdat we de distributie van één lange ketting in 1000 kleinere ketens. En zo elke keer dat we moeten zoeken door een van die ketens kunnen we negeren de 999 kettingen kan ons niet schelen over, en gewoon zoeken die ene. 

Die gemiddeld 1,000 korter. En dus hebben we nog steeds een soort van neigt naar dit gemiddelde geval van zijn constante tijd, maar alleen omdat we zijn hefboomwerking te delen door een aantal grote constante factor. Laten we eens kijken hoe dit zou kunnen eigenlijk kijken hoor. Dus dit was de hash tafel we hadden voordat we verklaarde een hash tabel die was kan opslaan 10 snaren. We zijn niet van plan om dat niet meer te doen. We weten al de beperkingen van deze methode. Nu onze hash tafel gaat worden een array van 10 knopen, pointers hoofden van gekoppelde lijsten. 

En nu is het nul. Elk van die 10 pointers is null. Er is niets in onze hash tafel nu. 

Laten we nu eens beginnen met een aantal zetten dingen in deze hash tabel. En laten we zien hoe deze methode is gaan profiteren ons een beetje. Laten we nu hash Joey. We zullen de string Joey doorlopen een hash-functie en we terug 6. Tja, wat moeten we nu doen? 

Welnu werken met gelinkte lijsten, we niet werken met arrays. En wanneer we werken met gekoppelde lijsten we weten dat we nodig hebben om dynamisch te beginnen toewijzing van ruimte en bouwen ketens. Dat is een soort van how-- dat zijn de kern elementen van het bouwen van een gekoppelde lijst. Dus laten we dynamisch toewijzen ruimte voor Joey, en dan laten we hem toe te voegen aan de keten. 

Dus nu kijken wat we hebben gedaan. Toen we hash Joey we de hashcode 6. Nu de wijzer op rij plaats 6 wijst op het hoofd van een gekoppelde lijst, en nu is het de enige element van een gekoppelde lijst. En het knooppunt, dat gekoppelde lijst is Joey. 

Dus als we moeten opzoeken Joey later, we hash weer Joey, krijgen we 6 weer omdat onze hash-functie is deterministisch. En dan beginnen we aan het hoofd van de gelinkte lijst wees Door scala locatie 6, en we kunnen herhalen over die proberen om Joey te vinden. En als we bouwen ons hash tafel effectief, en onze hash-functie effectief om gegevens goed te verdelen, gemiddeld elk van die verbonden lijsten bij elke reeks locatie zal de grootte van 1/10 als we net als een enorme gelinkte lijst met alles erin. 

Als we verdelen dat enorme gekoppeld lijst over 10 gelinkte lijsten elke lijst zal zijn 1/10 van de grootte. En dus 10 keer sneller te zoeken door. Dus laten we dit opnieuw doen. Laten we nu hash Ross. 

En laten we zeggen Ross, als we dat doen de hash-code die we weer terug is 2. Nou nu we dynamisch toewijzen een nieuw knooppunt, plaatsen we Ross in dat knooppunt, en we nu zeggen scala locatie 2, in plaats van te wijzen op null, wijst op het hoofd van een gekoppelde lijst wiens enige knooppunt is Ross. En kunnen we dit nog een keer te doen, we kan hash Rachel en krijg hashcode 4. malloc een nieuw knooppunt, zet Rachel in het knooppunt, en zeggen dat een reeks locatie 4 wijst nu naar het hoofd van een gekoppelde lijst wiens enige element toevallig Rachel zijn. 

OK, maar wat gebeurt er als We hebben een botsing? Laten we eens kijken hoe wij omgaan met botsingen met aparte chaining methode. Laten we hash Phoebe. We krijgen de hashcode 6. In ons vorige voorbeeld waren we net opslaan van de snaren in de array. Dit was een probleem. 

We willen niet afranselen Joey, en we hebben al gezien dat we een clustering kunnen krijgen problemen als we proberen en stap door en sonde. Maar wat als we gewoon een soort van behandel deze op dezelfde manier, toch? Het is net als het toevoegen van een element aan het hoofd van een gekoppelde lijst. Laten we gewoon malloc ruimte voor Phoebe. 

We zullen zeggen Phoebe's volgende pointer punten om de oude hoofd van de gelinkte lijst, en vervolgens 6 gewoon verwijst naar de nieuwe hoofd van de gelinkte lijst. En kijk nu, hebben we Phoebe veranderd. We kunnen nu slaan twee elementen hashcode 6, en we hebben geen problemen hebben. 

Dat is vrijwel alle er te chaining. En chaining is zeker de methode die is gaat het meest effectief voor u als te zijn u gegevens opslaan in een hash tabel. Maar deze combinatie van arrays en gelinkte lijsten samen om een ​​hash tafel echt te vormen drastisch verbetert uw vermogen om grote hoeveelheden gegevens en snel en efficiënt zoeken door die data. 

Er is nog steeds een meer datastructuur die er zijn dat misschien zelfs een beetje te beter in termen van het waarborgen dat onze insertie, deletie, en opzoeken tijden zijn nog sneller. En we zullen zien dat in een video op pogingen. Ik ben Doug Lloyd, dit is CS50.