1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:01,900 [Muziek] 3 00:00:01,900 --> 00:00:05,710 4 00:00:05,710 --> 00:00:09,150 >> DOUG LLOYD: Door nu je weet veel over arrays, 5 00:00:09,150 --> 00:00:11,610 en je weet veel over gelinkte lijsten. 6 00:00:11,610 --> 00:00:13,650 En we hebben bespreken voors en tegens, we hebben 7 00:00:13,650 --> 00:00:16,620 besproken die lijsten verbonden kunnen groter en kleiner, 8 00:00:16,620 --> 00:00:18,630 maar ze nemen meer grootte. 9 00:00:18,630 --> 00:00:22,359 Arrays zijn veel eenvoudiger te gebruiken, maar ze zijn beperkt in zoverre 10 00:00:22,359 --> 00:00:24,900 als we de grootte van de vastgestelde de matrix aan het begin 11 00:00:24,900 --> 00:00:26,910 en dan zijn we vast te zitten. 12 00:00:26,910 --> 00:00:30,470 >> Maar dat is, we hebben vrij veel uitgeput al onze topics 13 00:00:30,470 --> 00:00:33,040 over gelinkte lijsten en arrays. 14 00:00:33,040 --> 00:00:34,950 Of hebben we? 15 00:00:34,950 --> 00:00:37,720 Misschien kunnen we iets doen nog meer creatieve. 16 00:00:37,720 --> 00:00:40,950 En dat soort leent het idee van een hash tabel. 17 00:00:40,950 --> 00:00:46,680 >> Dus in een hash tafel we gaan proberen combineren een array met een gekoppelde lijst. 18 00:00:46,680 --> 00:00:49,520 We gaan om de voordelen te nemen van de array, zoals random access, 19 00:00:49,520 --> 00:00:53,510 zijn om gewoon naar serie staat element 4 of array-element 8 20 00:00:53,510 --> 00:00:55,560 zonder over herhalen. 21 00:00:55,560 --> 00:00:57,260 Dat is behoorlijk snel, toch? 22 00:00:57,260 --> 00:01:00,714 >> Maar we willen ook onze gegevens structuur kunnen groeien en krimpen. 23 00:01:00,714 --> 00:01:02,630 We niet nodig, we doen niet willen worden beperkt. 24 00:01:02,630 --> 00:01:04,588 En we willen kunnen toe te voegen en de dingen te verwijderen 25 00:01:04,588 --> 00:01:08,430 heel gemakkelijk, wat als je te herinneren, is zeer complex met een matrix. 26 00:01:08,430 --> 00:01:11,650 En we kunnen dit noemen nieuw ding een hash tabel. 27 00:01:11,650 --> 00:01:15,190 >> En indien correct geïmplementeerd, we soort nemen 28 00:01:15,190 --> 00:01:18,150 de voordelen van beide data structuren die je al hebt gezien, 29 00:01:18,150 --> 00:01:19,880 arrays en gelinkte lijsten. 30 00:01:19,880 --> 00:01:23,070 Inbrengen kan beginnen neigen naar theta van 1. 31 00:01:23,070 --> 00:01:26,207 Theta we hebben niet echt besproken, maar theta is slechts het gemiddelde geval, 32 00:01:26,207 --> 00:01:27,540 wat er werkelijk gaat gebeuren. 33 00:01:27,540 --> 00:01:29,680 Je bent niet altijd gaat om hebben het ergste geval, 34 00:01:29,680 --> 00:01:32,555 en je bent niet altijd zal hebben het beste geval, dus wat is 35 00:01:32,555 --> 00:01:33,900 de gemiddelde scenario? 36 00:01:33,900 --> 00:01:36,500 >> Goed gemiddeld insertie in een hash table 37 00:01:36,500 --> 00:01:39,370 kan beginnen om dicht bij constante tijd te krijgen. 38 00:01:39,370 --> 00:01:41,570 En verwijdering kan krijgen dicht bij constante tijd. 39 00:01:41,570 --> 00:01:44,440 En lookup kan krijgen dicht bij constante tijd. 40 00:01:44,440 --> 00:01:48,600 That's-- we geen gegevens structuur maar die kan dat doen, 41 00:01:48,600 --> 00:01:51,180 en zo dit al klinkt als een vrij groot ding. 42 00:01:51,180 --> 00:01:57,010 We hebben echt verzacht de nadelen van elk op zijn eigen. 43 00:01:57,010 --> 00:01:59,160 >> Om deze prestaties te krijgen upgraden hoewel, we 44 00:01:59,160 --> 00:02:03,580 moeten nadenken over hoe we voegen gegevens in de structuur. 45 00:02:03,580 --> 00:02:07,380 Concreet willen we de gegevens zelf om ons te vertellen 46 00:02:07,380 --> 00:02:09,725 waar het moet gaan in de structuur. 47 00:02:09,725 --> 00:02:12,850 En als we moeten dan om te zien of het in de structuur, als we het nodig om het te vinden, 48 00:02:12,850 --> 00:02:16,610 we willen kijken naar de data weer en in staat zijn om effectief, 49 00:02:16,610 --> 00:02:18,910 met de data, willekeurig toegang toe. 50 00:02:18,910 --> 00:02:20,700 Enkel door de gegevens die we moeten hebben 51 00:02:20,700 --> 00:02:25,890 een idee van waar we precies zijn gaan om het te vinden in de hash tabel. 52 00:02:25,890 --> 00:02:28,770 >> Nu het nadeel van een hash tabel is dat ze echt 53 00:02:28,770 --> 00:02:31,770 vrij slecht bij het bestellen of het sorteren van data. 54 00:02:31,770 --> 00:02:34,970 En in feite, als je begint om ze te gebruiken om te bestellen of sorteren 55 00:02:34,970 --> 00:02:37,990 gegevens verlies je alle voordelen die u eerder 56 00:02:37,990 --> 00:02:40,710 had in termen van inbrengen en verwijderen. 57 00:02:40,710 --> 00:02:44,060 De tijd wordt dichter bij theta van n, en we hebben eigenlijk 58 00:02:44,060 --> 00:02:45,530 regressie in een gekoppelde lijst. 59 00:02:45,530 --> 00:02:48,850 En dus we willen alleen hash gebruiken tafels als we niet de zorg over 60 00:02:48,850 --> 00:02:51,490 of de data wordt gesorteerd. 61 00:02:51,490 --> 00:02:54,290 Voor de context waarin u zult ze te gebruiken in CS50 62 00:02:54,290 --> 00:02:58,900 u waarschijnlijk niet schelen dat de gegevens gesorteerd. 63 00:02:58,900 --> 00:03:03,170 >> Dus een hash tabel is een combinatie twee afzonderlijke stukken 64 00:03:03,170 --> 00:03:04,980 waarmee we vertrouwd zijn. 65 00:03:04,980 --> 00:03:07,930 De eerste is een functie, die we meestal noemen een hash-functie. 66 00:03:07,930 --> 00:03:11,760 En dat de hash-functie gaat terug een aantal niet-negatieve integer, die 67 00:03:11,760 --> 00:03:14,870 we meestal noemen een hashcode, OK? 68 00:03:14,870 --> 00:03:20,230 Het tweede stuk is een array, dat is geschikt voor het opslaan van gegevens van het type dat we 69 00:03:20,230 --> 00:03:22,190 willen plaatsen in de gegevensstructuur. 70 00:03:22,190 --> 00:03:24,310 We zullen af ​​te houden op de gelinkte lijst element voor nu 71 00:03:24,310 --> 00:03:27,810 en gewoon beginnen met de basis van een hash tabel om je hoofd te krijgen rond het, 72 00:03:27,810 --> 00:03:30,210 en dan zullen we misschien te blazen je geest een beetje toen we 73 00:03:30,210 --> 00:03:32,920 combineren arrays en lijsten samen. 74 00:03:32,920 --> 00:03:35,590 >> Het basisidee al is dat we een aantal gegevens te nemen. 75 00:03:35,590 --> 00:03:37,860 We lopen dat gegevens via de hash-functie. 76 00:03:37,860 --> 00:03:41,980 Zo worden de gegevens verwerkt en het spuugt een nummer, OK? 77 00:03:41,980 --> 00:03:44,890 En daarna met dat nummer we alleen de gegevens op te slaan 78 00:03:44,890 --> 00:03:48,930 we willen opslaan in de matrix op die locatie. 79 00:03:48,930 --> 00:03:53,990 Zo bijvoorbeeld hebben we misschien Deze hash tabel met strings. 80 00:03:53,990 --> 00:03:57,350 Het heeft 10 elementen in, dus kunnen we 10 snaren passen daarin. 81 00:03:57,350 --> 00:03:59,320 >> Laten we zeggen dat we willen hash John. 82 00:03:59,320 --> 00:04:02,979 Dus John als de gegevens die we willen invoegen in deze hash tafel ergens. 83 00:04:02,979 --> 00:04:03,770 Waar gaan we het? 84 00:04:03,770 --> 00:04:05,728 Goed typisch met een serie tot nu toe waarschijnlijk wij 85 00:04:05,728 --> 00:04:07,610 zou het in serie locatie 0. 86 00:04:07,610 --> 00:04:09,960 Maar nu hebben we deze nieuwe hash-functie. 87 00:04:09,960 --> 00:04:13,180 >> En laten we zeggen dat we lopen John door middel van deze hash-functie 88 00:04:13,180 --> 00:04:15,417 en het is spuugt 4. 89 00:04:15,417 --> 00:04:17,500 Nou, dat is waar we zijn gaat willen John zetten. 90 00:04:17,500 --> 00:04:22,050 Wij willen John in serie plaats zetten 4, want als we hash John again-- 91 00:04:22,050 --> 00:04:23,810 laten we zeggen dat we later wilt zoeken en te zien 92 00:04:23,810 --> 00:04:26,960 Als John bestaat in deze hash table-- alles wat we moeten doen 93 00:04:26,960 --> 00:04:30,310 wordt gerund het door dezelfde hash functie, ontvang de nummer 4, 94 00:04:30,310 --> 00:04:33,929 en in staat zijn om John te vinden onmiddellijk onze gegevensstructuur. 95 00:04:33,929 --> 00:04:34,720 Dat is vrij goed. 96 00:04:34,720 --> 00:04:36,928 >> Laten we zeggen dat we dit nu doen nogmaals, we willen hash Paul. 97 00:04:36,928 --> 00:04:39,446 We willen Paul toevoegen in deze hash tabel. 98 00:04:39,446 --> 00:04:42,070 Laten we zeggen dat we deze keer draaien Paul door de hash-functie, 99 00:04:42,070 --> 00:04:44,600 de hashcode die wordt gegenereerd is 6. 100 00:04:44,600 --> 00:04:47,340 Nou nu kunnen we Paul zetten in de array locatie 6. 101 00:04:47,340 --> 00:04:50,040 En als we moeten opzoeken of Paul is in deze hash tabel, 102 00:04:50,040 --> 00:04:53,900 alles wat we moeten doen is lopen Paul door de hash-functie weer 103 00:04:53,900 --> 00:04:55,830 en we gaan er weer uit te krijgen 6. 104 00:04:55,830 --> 00:04:57,590 >> En dan hebben we alleen kijken op rij plaats 6. 105 00:04:57,590 --> 00:04:58,910 Paul is er? 106 00:04:58,910 --> 00:05:00,160 Als dat zo is, hij is in de hash tabel. 107 00:05:00,160 --> 00:05:01,875 Paul is er niet? 108 00:05:01,875 --> 00:05:03,000 Hij is niet in de hash tabel. 109 00:05:03,000 --> 00:05:05,720 Het is vrij eenvoudig. 110 00:05:05,720 --> 00:05:07,770 >> Nu hoe maak je een hash-functie te definiëren? 111 00:05:07,770 --> 00:05:11,460 Nou er is echt geen limiet aan het aantal mogelijke hashfuncties. 112 00:05:11,460 --> 00:05:14,350 In feite is er een aantal echt, echt goede op het internet. 113 00:05:14,350 --> 00:05:17,560 Er is een aantal echt, echt slecht die op het internet. 114 00:05:17,560 --> 00:05:21,080 Het is ook vrij gemakkelijk een slechte schrijven. 115 00:05:21,080 --> 00:05:23,760 >> Dus wat maakt een goede hash-functie, toch? 116 00:05:23,760 --> 00:05:27,280 Wel een goede hash-functie moet gebruik alleen de gegevens die worden hashed, 117 00:05:27,280 --> 00:05:29,420 en alle gegevens worden hashed. 118 00:05:29,420 --> 00:05:32,500 Dus we willen niet anything-- gebruiken we hebben niets te nemen 119 00:05:32,500 --> 00:05:35,560 anders dan de gegevens. 120 00:05:35,560 --> 00:05:37,080 En we willen alle gegevens te gebruiken. 121 00:05:37,080 --> 00:05:39,830 We willen niet gewoon gebruik maken van een stuk van het, we willen al het te gebruiken. 122 00:05:39,830 --> 00:05:41,710 Een hash-functie moet Ook deterministisch zijn. 123 00:05:41,710 --> 00:05:42,550 Wat betekent dat? 124 00:05:42,550 --> 00:05:46,200 Nou, het betekent dat elke keer als we passeren exact dezelfde stuk van de gegevens 125 00:05:46,200 --> 00:05:50,040 in de hash-functie die we altijd krijgt dezelfde hashcode uit. 126 00:05:50,040 --> 00:05:52,870 Als ik langs John in de hash-functie ik uit 4. 127 00:05:52,870 --> 00:05:56,110 Ik moet in staat zijn om dat te doen 10.000 tijden en ik zal altijd 4. 128 00:05:56,110 --> 00:06:00,810 Dus geen willekeurige getallen effectief kunnen worden betrokken bij onze hash tables-- 129 00:06:00,810 --> 00:06:02,750 in onze hash functies. 130 00:06:02,750 --> 00:06:05,750 >> Een hash-functie moet ook uniform te verdelen data. 131 00:06:05,750 --> 00:06:09,700 Als elke keer dat u gegevens lopen door de hash-functie krijg je de hashcode 0, 132 00:06:09,700 --> 00:06:11,200 dat is waarschijnlijk niet zo groot, toch? 133 00:06:11,200 --> 00:06:14,600 Wilt u waarschijnlijk grote een bereik van hash codes. 134 00:06:14,600 --> 00:06:17,190 Ook dingen kunnen worden verspreid uit de hele tafel. 135 00:06:17,190 --> 00:06:23,210 En ook het zou geweldig zijn als echt gelijkwaardig, zoals John en Jonathan, 136 00:06:23,210 --> 00:06:26,320 misschien werden verspreid te wegen verschillende lokaties in de hashtabel. 137 00:06:26,320 --> 00:06:28,750 Dat zou een mooi voordeel. 138 00:06:28,750 --> 00:06:31,250 >> Hier is een voorbeeld van een hash-functie. 139 00:06:31,250 --> 00:06:33,150 Ik schreef dit één eerder. 140 00:06:33,150 --> 00:06:35,047 Het is niet een bijzonder goede hash-functie 141 00:06:35,047 --> 00:06:37,380 om redenen die niet echt doen dragen in te gaan op dit moment. 142 00:06:37,380 --> 00:06:41,040 Maar zie je wat er hier aan de hand? 143 00:06:41,040 --> 00:06:44,420 Het lijkt alsof we waarbij een variabele genoemd bedrag en de oprichting ervan gelijk is aan 0. 144 00:06:44,420 --> 00:06:50,010 En dan blijkbaar ben ik iets te doen zolang strstr [j] is niet gelijk 145 00:06:50,010 --> 00:06:52,490 om Backslash 0. 146 00:06:52,490 --> 00:06:54,870 Wat ben ik daar aan het doen? 147 00:06:54,870 --> 00:06:57,440 >> Dit is eigenlijk gewoon een ander manier van uitvoering [? strl?] 148 00:06:57,440 --> 00:06:59,773 en detecteren wanneer je hebt aan het einde van de string. 149 00:06:59,773 --> 00:07:02,480 Dus ik eigenlijk niet hoeft te berekenen van de lengte van de tekenreeks 150 00:07:02,480 --> 00:07:05,640 Ik ben gewoon met behulp van toen ik raakte de backslash 0 karakter ik weet 151 00:07:05,640 --> 00:07:07,185 Ik heb het einde van de string bereikt. 152 00:07:07,185 --> 00:07:09,560 En dan ga ik om te blijven itereren door middel van die string, 153 00:07:09,560 --> 00:07:15,310 toevoeging strstr [j] te vatten, en dan aan het einde van de dag gaat naar som mod terug 154 00:07:15,310 --> 00:07:16,200 HASH_MAX. 155 00:07:16,200 --> 00:07:18,700 >> In principe al deze hash functie doet is het toevoegen van up 156 00:07:18,700 --> 00:07:23,450 alle waarden van ASCII mijn reeks, en dan is het 157 00:07:23,450 --> 00:07:26,390 terugkerende sommige hashcode modded door HASH_MAX. 158 00:07:26,390 --> 00:07:29,790 Het is waarschijnlijk de grootte mijn array, toch? 159 00:07:29,790 --> 00:07:33,160 Ik wil niet te krijgen hash codes als mijn array is van maat 10, 160 00:07:33,160 --> 00:07:35,712 Ik wil niet te krijgen out hash codes 11, 12, 161 00:07:35,712 --> 00:07:38,690 13, ik kan geen dingen te zetten in de locaties van de array, 162 00:07:38,690 --> 00:07:39,790 dat onwettig zou zijn. 163 00:07:39,790 --> 00:07:42,130 Ik zou lijden aan een segmentation fault. 164 00:07:42,130 --> 00:07:45,230 >> Nu is hier nog snel opzij. 165 00:07:45,230 --> 00:07:48,470 Over het algemeen ben je waarschijnlijk niet van plan om wilt u uw eigen hash functies te schrijven. 166 00:07:48,470 --> 00:07:50,997 Het is eigenlijk een beetje een kunst, geen wetenschap. 167 00:07:50,997 --> 00:07:52,580 En er is veel dat gaat in hen. 168 00:07:52,580 --> 00:07:55,288 Het internet, zoals ik al zei, is vol echt goede hash functies, 169 00:07:55,288 --> 00:07:58,470 en je moet het internet te gebruiken vinden hash functies, want het is echt 170 00:07:58,470 --> 00:08:03,230 gewoon een soort van een onnodige verspilling van tijd om je eigen te maken. 171 00:08:03,230 --> 00:08:05,490 >> U kunt eenvoudige degenen schrijven voor testdoeleinden. 172 00:08:05,490 --> 00:08:08,323 Maar als je daadwerkelijk gaat start hashing databank slaan 173 00:08:08,323 --> 00:08:10,780 in een hash table je bent waarschijnlijk gaat te willen 174 00:08:10,780 --> 00:08:14,580 met een functie die is gegenereerd gebruiken voor u, dat bestaat op het internet. 175 00:08:14,580 --> 00:08:17,240 Als je gewoon zeker om uw bronnen te citeren. 176 00:08:17,240 --> 00:08:21,740 Er is geen reden om plagiaat hier iets. 177 00:08:21,740 --> 00:08:25,370 >> De computer science gemeenschap is zeker groeien, en echt waarden 178 00:08:25,370 --> 00:08:28,796 open source, en het is echt belangrijk om uw bronnen citeren, zodat mensen 179 00:08:28,796 --> 00:08:30,670 kan attributie krijgen voor het werk dat ze 180 00:08:30,670 --> 00:08:32,312 doet in het voordeel van de gemeenschap. 181 00:08:32,312 --> 00:08:34,020 Dus altijd sure-- zijn en niet alleen voor hash 182 00:08:34,020 --> 00:08:37,270 functies, maar over het algemeen bij Gebruik de code van een externe bron, 183 00:08:37,270 --> 00:08:38,299 altijd citeren uw bron. 184 00:08:38,299 --> 00:08:43,500 Krediet aan de persoon die wel deel van het werk, zodat je niet hoeft te doen. 185 00:08:43,500 --> 00:08:46,720 >> OK dus laten we dit opnieuw hash tafel voor een tweede. 186 00:08:46,720 --> 00:08:48,780 Dit is waar we vertrokken off nadat we gestoken 187 00:08:48,780 --> 00:08:53,300 John en Paul in deze hash tabel. 188 00:08:53,300 --> 00:08:55,180 Heeft u een probleem hier te zien? 189 00:08:55,180 --> 00:08:58,410 Zie je misschien twee. 190 00:08:58,410 --> 00:09:02,240 Maar in het bijzonder, heb je zie dit mogelijk probleem? 191 00:09:02,240 --> 00:09:06,770 >> Wat als ik hash Ringo, en het blijkt dat na de verwerking 192 00:09:06,770 --> 00:09:14,000 dat gegevens via de hash-functie Ringo gegenereerd ook de hashcode 6. 193 00:09:14,000 --> 00:09:16,810 Ik heb al gegevens op hashcode-- scala locatie 6. 194 00:09:16,810 --> 00:09:22,000 Dus het is waarschijnlijk gaan om een ​​beetje te zijn een probleem voor mij nu, toch? 195 00:09:22,000 --> 00:09:23,060 >> We noemen dit een botsing. 196 00:09:23,060 --> 00:09:26,460 De botsing optreedt wanneer twee stukjes data lopen via dezelfde hash 197 00:09:26,460 --> 00:09:29,200 functie op dezelfde hashcode. 198 00:09:29,200 --> 00:09:32,850 Vermoedelijk willen we nog steeds allebei stukken van de gegevens in de hash-tabel, 199 00:09:32,850 --> 00:09:36,330 anders zouden we niet worden uitgevoerd Ringo arbitrair door de hash-functie. 200 00:09:36,330 --> 00:09:40,870 We willen vermoedelijk te krijgen Ringo in die array. 201 00:09:40,870 --> 00:09:46,070 >> Hoe doen we het wel, als hij en Paul zowel de opbrengst hashcode 6? 202 00:09:46,070 --> 00:09:49,520 We willen niet overschrijven Paul, we willen Paulus om daar te zijn. 203 00:09:49,520 --> 00:09:52,790 Dus we moeten een manier vinden om te krijgen elementen in de hash tabel die 204 00:09:52,790 --> 00:09:56,550 behoudt nog steeds onze snelle inbrengen en snelle blik omhoog. 205 00:09:56,550 --> 00:10:01,350 En een manier om te gaan met het is om een zogenaamde lineaire indringende doen. 206 00:10:01,350 --> 00:10:04,170 >> Met deze methode als we een botsing, nou ja, wat doen we? 207 00:10:04,170 --> 00:10:08,580 Goed we kunnen hem niet in serie locatie 6, of wat hashcode gegenereerd, 208 00:10:08,580 --> 00:10:10,820 laten we hem hashcode plus 1. 209 00:10:10,820 --> 00:10:13,670 En als dat vol laten we zet hem in hashcode plus 2. 210 00:10:13,670 --> 00:10:17,420 Het voordeel hiervan is als hij niet precies waar we denken dat hij is, 211 00:10:17,420 --> 00:10:20,850 en we moeten beginnen met zoeken, Misschien hoeven we niet te ver te gaan. 212 00:10:20,850 --> 00:10:23,900 Misschien hebben we niet hoeven te zoeken alle n elementen van de hash-tabel. 213 00:10:23,900 --> 00:10:25,790 Misschien moeten we zoeken een paar van hen. 214 00:10:25,790 --> 00:10:30,680 >> En zo zijn we nog steeds neigt naar dat de gemiddelde geval dicht bij 1 vs 215 00:10:30,680 --> 00:10:34,280 dicht bij n, dus misschien dat zal werken. 216 00:10:34,280 --> 00:10:38,010 Dus laten we zien hoe dit zou kunnen werken in de werkelijkheid. 217 00:10:38,010 --> 00:10:41,460 En laten we kijken of misschien kunnen we detecteren het probleem dat hier optreden. 218 00:10:41,460 --> 00:10:42,540 >> Laten we zeggen dat we hash Bart. 219 00:10:42,540 --> 00:10:45,581 Dus nu gaan we een nieuwe set draaien snaren door de hash-functie, 220 00:10:45,581 --> 00:10:48,460 en lopen we Bart door de hash functie, krijgen we hashcode 6. 221 00:10:48,460 --> 00:10:52,100 We nemen een kijkje, zien we 6 leeg, dus we kunnen Bart daar te zetten. 222 00:10:52,100 --> 00:10:55,410 >> Nu hash we Lisa en dat genereert ook hashcode 6. 223 00:10:55,410 --> 00:10:58,330 Nou nu dat we met behulp van deze lineaire indringende methode beginnen we op 6, 224 00:10:58,330 --> 00:10:59,330 we zien dat 6 vol. 225 00:10:59,330 --> 00:11:00,990 We kunnen niet zetten Lisa in 6. 226 00:11:00,990 --> 00:11:02,090 Dus waar gaan we heen? 227 00:11:02,090 --> 00:11:03,280 Laten we naar 7. 228 00:11:03,280 --> 00:11:04,610 7's leeg, dus dat werkt. 229 00:11:04,610 --> 00:11:06,510 Dus laten we Lisa daar. 230 00:11:06,510 --> 00:11:10,200 >> Nu hash we Homer en we krijgen 7. 231 00:11:10,200 --> 00:11:13,380 OK goed we weten dat 7 volledige nu, dus we kunnen niet daar te zetten Homer. 232 00:11:13,380 --> 00:11:14,850 Dus laten we naar 8. 233 00:11:14,850 --> 00:11:15,664 8 is beschikbaar? 234 00:11:15,664 --> 00:11:18,330 Ja, en 8, dicht bij 7, dus als we moeten beginnen met zoeken we 235 00:11:18,330 --> 00:11:20,020 niet van plan te hebben om te ver te gaan. 236 00:11:20,020 --> 00:11:22,860 En zo laten we Homer 8. 237 00:11:22,860 --> 00:11:25,151 >> Nu hash we Maggie en retourneert 3, godzijdank 238 00:11:25,151 --> 00:11:26,650 kunnen we gewoon Maggie daar. 239 00:11:26,650 --> 00:11:29,070 We hoeven niet elke doen soort indringende voor. 240 00:11:29,070 --> 00:11:32,000 Nu hash we Marge, en Marge keert ook 6. 241 00:11:32,000 --> 00:11:39,560 >> Goed 6 vol, vol 7, 8 vol is, 9, oke dank God, 9 is leeg. 242 00:11:39,560 --> 00:11:41,600 Ik kan Marge zetten op 9. 243 00:11:41,600 --> 00:11:45,280 Nu al kunnen we zien dat we beginnen om dit probleem, waar nu zijn we hebben 244 00:11:45,280 --> 00:11:48,780 begint om dingen soort rekken van ver weg van hun hash codes. 245 00:11:48,780 --> 00:11:52,960 En dat theta van 1, dat de gemiddelde Bij constant tijd, 246 00:11:52,960 --> 00:11:56,560 begint een beetje more-- krijgen begint een beetje meer de neiging 247 00:11:56,560 --> 00:11:58,050 richting theta van n. 248 00:11:58,050 --> 00:12:01,270 We beginnen te verliezen dat voordeel van hash tabellen. 249 00:12:01,270 --> 00:12:03,902 >> Dit probleem dat we net zagen is iets genaamd clustering. 250 00:12:03,902 --> 00:12:06,360 En wat is er echt slecht over clustering is dat zodra u nu 251 00:12:06,360 --> 00:12:09,606 twee elementen die kant zijn door kant maakt het nog waarschijnlijker, 252 00:12:09,606 --> 00:12:11,480 je moet het dubbele van de kans, dat je gaat 253 00:12:11,480 --> 00:12:13,516 nog een botsing hebben met die cluster, 254 00:12:13,516 --> 00:12:14,890 en het cluster zal groeien met een. 255 00:12:14,890 --> 00:12:19,640 En je zult blijven groeien en groeien je kans op een botsing. 256 00:12:19,640 --> 00:12:24,470 En uiteindelijk het is net zo slecht zo niet sorteren van de gegevens helemaal. 257 00:12:24,470 --> 00:12:27,590 >> Het andere probleem is echter dat we stil en zo ver op dit punt, 258 00:12:27,590 --> 00:12:30,336 we hebben net soort geweest begrijpen wat een hash-tabel is, 259 00:12:30,336 --> 00:12:31,960 we nog steeds slechts ruimte voor 10 snaren. 260 00:12:31,960 --> 00:12:37,030 Als we willen blijven hash de inwoners van Springfield, 261 00:12:37,030 --> 00:12:38,790 kunnen we alleen maar 10 van hen in. 262 00:12:38,790 --> 00:12:42,619 En als we proberen en voeg een 11e of 12e, we hebben geen plaats om ze te zetten. 263 00:12:42,619 --> 00:12:45,660 We konden gewoon spinnen rond in cirkels proberen om een ​​lege plek te vinden, 264 00:12:45,660 --> 00:12:49,000 en we misschien komen te zitten in een oneindige lus. 265 00:12:49,000 --> 00:12:51,810 >> Dus dit soort leent aan het idee van iets genaamd chaining. 266 00:12:51,810 --> 00:12:55,790 En dit is waar we gaan brengen gelinkte lijsten terug in beeld. 267 00:12:55,790 --> 00:13:01,300 Wat als in plaats van het opslaan van slechts de gegevens zelf in de array, 268 00:13:01,300 --> 00:13:04,471 elk element van de array kan Houd meerdere stukken van gegevens? 269 00:13:04,471 --> 00:13:05,970 Nou, dat heeft geen zin, toch? 270 00:13:05,970 --> 00:13:09,280 We weten dat een array kan alleen hold-- elk element van een array 271 00:13:09,280 --> 00:13:12,930 kan slechts één stuk van gegevens van dat soort gegevens. 272 00:13:12,930 --> 00:13:16,750 >> Maar wat als dat soort data is een gelinkte lijst, toch? 273 00:13:16,750 --> 00:13:19,830 Dus wat als elke element van de array was 274 00:13:19,830 --> 00:13:22,790 een verwijzing naar het hoofd van een gekoppelde lijst? 275 00:13:22,790 --> 00:13:24,680 En dan kunnen we bouwen die verbonden lijsten 276 00:13:24,680 --> 00:13:27,120 en groeien ze willekeurig, omdat gelinkte lijsten toestaan 277 00:13:27,120 --> 00:13:32,090 ons te groeien en krimpen veel meer flexibeler dan een matrix doet. 278 00:13:32,090 --> 00:13:34,210 Dus wat als we nu gebruiken, We benutten deze, toch? 279 00:13:34,210 --> 00:13:37,760 We beginnen deze ketens groeien uit deze reeks locaties. 280 00:13:37,760 --> 00:13:40,740 >> Nu kunnen we passen een oneindige hoeveelheid gegevens of niet oneindig, 281 00:13:40,740 --> 00:13:44,170 een willekeurig aantal data, in onze hash table 282 00:13:44,170 --> 00:13:47,760 zonder ooit te lopen in het probleem van de botsing. 283 00:13:47,760 --> 00:13:50,740 We hebben ook geëlimineerd clustering door dit te doen. 284 00:13:50,740 --> 00:13:54,380 En goed we weten dat wanneer we voegen in een gelinkte lijst, als je herinneren 285 00:13:54,380 --> 00:13:57,779 van onze video op gelinkte lijsten, afzonderlijk gelinkte lijsten en dubbel gelinkte lijsten, 286 00:13:57,779 --> 00:13:59,070 het is een constante tijd operatie. 287 00:13:59,070 --> 00:14:00,710 We gewoon toe te voegen aan de voorzijde. 288 00:14:00,710 --> 00:14:04,400 >> En voor het opzoeken, goed we weten die opzoeken in een gekoppelde lijst 289 00:14:04,400 --> 00:14:05,785 kan een probleem zijn, toch? 290 00:14:05,785 --> 00:14:07,910 We moeten zoeken door middel van het van begin tot einde. 291 00:14:07,910 --> 00:14:10,460 Er is geen willekeurige toegang in een gekoppelde lijst. 292 00:14:10,460 --> 00:14:15,610 Maar als plaats van één gekoppelde overzicht waar een lookup O van n zou zijn, 293 00:14:15,610 --> 00:14:19,590 we hebben nu 10 gelinkte lijsten, of 1000 gelinkte lijsten, 294 00:14:19,590 --> 00:14:24,120 Nu is het O n gedeeld door 10, of O n gedeeld door 1000. 295 00:14:24,120 --> 00:14:26,940 >> En terwijl we aan het praten waren theorie over de complexiteit 296 00:14:26,940 --> 00:14:30,061 We negeren constanten in de echte wereld deze dingen eigenlijk uit, 297 00:14:30,061 --> 00:14:30,560 toch? 298 00:14:30,560 --> 00:14:33,080 We eigenlijk zult merken dat dit gebeurt 299 00:14:33,080 --> 00:14:36,610 tot 10 keer sneller te lopen, of 1000 keer sneller, 300 00:14:36,610 --> 00:14:41,570 omdat we de distributie van één lange ketting in 1000 kleinere ketens. 301 00:14:41,570 --> 00:14:45,090 En zo elke keer dat we moeten zoeken door een van die ketens kunnen we 302 00:14:45,090 --> 00:14:50,290 negeren de 999 kettingen kan ons niet schelen over, en gewoon zoeken die ene. 303 00:14:50,290 --> 00:14:53,220 >> Die gemiddeld 1,000 korter. 304 00:14:53,220 --> 00:14:56,460 En dus hebben we nog steeds een soort van neigt naar dit gemiddelde geval 305 00:14:56,460 --> 00:15:01,610 van zijn constante tijd, maar alleen omdat we zijn hefboomwerking 306 00:15:01,610 --> 00:15:03,730 te delen door een aantal grote constante factor. 307 00:15:03,730 --> 00:15:05,804 Laten we eens kijken hoe dit zou kunnen eigenlijk kijken hoor. 308 00:15:05,804 --> 00:15:08,720 Dus dit was de hash tafel we hadden voordat we verklaarde een hash tabel die 309 00:15:08,720 --> 00:15:10,270 was kan opslaan 10 snaren. 310 00:15:10,270 --> 00:15:11,728 We zijn niet van plan om dat niet meer te doen. 311 00:15:11,728 --> 00:15:13,880 We weten al de beperkingen van deze methode. 312 00:15:13,880 --> 00:15:20,170 Nu onze hash tafel gaat worden een array van 10 knopen, pointers 313 00:15:20,170 --> 00:15:22,120 hoofden van gekoppelde lijsten. 314 00:15:22,120 --> 00:15:23,830 >> En nu is het nul. 315 00:15:23,830 --> 00:15:26,170 Elk van die 10 pointers is null. 316 00:15:26,170 --> 00:15:29,870 Er is niets in onze hash tafel nu. 317 00:15:29,870 --> 00:15:32,690 >> Laten we nu eens beginnen met een aantal zetten dingen in deze hash tabel. 318 00:15:32,690 --> 00:15:35,440 En laten we zien hoe deze methode is gaan profiteren ons een beetje. 319 00:15:35,440 --> 00:15:36,760 Laten we nu hash Joey. 320 00:15:36,760 --> 00:15:40,210 We zullen de string Joey doorlopen een hash-functie en we terug 6. 321 00:15:40,210 --> 00:15:41,200 Tja, wat moeten we nu doen? 322 00:15:41,200 --> 00:15:44,090 >> Welnu werken met gelinkte lijsten, we niet werken met arrays. 323 00:15:44,090 --> 00:15:45,881 En wanneer we werken met gekoppelde lijsten we 324 00:15:45,881 --> 00:15:49,790 weten dat we nodig hebben om dynamisch te beginnen toewijzing van ruimte en bouwen ketens. 325 00:15:49,790 --> 00:15:54,020 Dat is een soort van how-- dat zijn de kern elementen van het bouwen van een gekoppelde lijst. 326 00:15:54,020 --> 00:15:57,670 Dus laten we dynamisch toewijzen ruimte voor Joey, 327 00:15:57,670 --> 00:16:00,390 en dan laten we hem toe te voegen aan de keten. 328 00:16:00,390 --> 00:16:03,170 >> Dus nu kijken wat we hebben gedaan. 329 00:16:03,170 --> 00:16:06,440 Toen we hash Joey we de hashcode 6. 330 00:16:06,440 --> 00:16:11,790 Nu de wijzer op rij plaats 6 wijst op het hoofd van een gekoppelde lijst, 331 00:16:11,790 --> 00:16:14,900 en nu is het de enige element van een gekoppelde lijst. 332 00:16:14,900 --> 00:16:18,350 En het knooppunt, dat gekoppelde lijst is Joey. 333 00:16:18,350 --> 00:16:22,300 >> Dus als we moeten opzoeken Joey later, we hash weer Joey, 334 00:16:22,300 --> 00:16:26,300 krijgen we 6 weer omdat onze hash-functie is deterministisch. 335 00:16:26,300 --> 00:16:30,400 En dan beginnen we aan het hoofd van de gelinkte lijst wees 336 00:16:30,400 --> 00:16:33,360 Door scala locatie 6, en we kunnen herhalen 337 00:16:33,360 --> 00:16:35,650 over die proberen om Joey te vinden. 338 00:16:35,650 --> 00:16:37,780 En als we bouwen ons hash tafel effectief, 339 00:16:37,780 --> 00:16:41,790 en onze hash-functie effectief om gegevens goed te verdelen, 340 00:16:41,790 --> 00:16:45,770 gemiddeld elk van die verbonden lijsten bij elke reeks locatie 341 00:16:45,770 --> 00:16:50,110 zal de grootte van 1/10 als we net als een enorme 342 00:16:50,110 --> 00:16:51,650 gelinkte lijst met alles erin. 343 00:16:51,650 --> 00:16:55,670 >> Als we verdelen dat enorme gekoppeld lijst over 10 gelinkte lijsten 344 00:16:55,670 --> 00:16:57,760 elke lijst zal zijn 1/10 van de grootte. 345 00:16:57,760 --> 00:17:01,432 En dus 10 keer sneller te zoeken door. 346 00:17:01,432 --> 00:17:02,390 Dus laten we dit opnieuw doen. 347 00:17:02,390 --> 00:17:04,290 Laten we nu hash Ross. 348 00:17:04,290 --> 00:17:07,540 >> En laten we zeggen Ross, als we dat doen de hash-code die we weer terug is 2. 349 00:17:07,540 --> 00:17:10,630 Nou nu we dynamisch toewijzen een nieuw knooppunt, plaatsen we Ross in dat knooppunt, 350 00:17:10,630 --> 00:17:14,900 en we nu zeggen scala locatie 2, in plaats van te wijzen op null, 351 00:17:14,900 --> 00:17:18,579 wijst op het hoofd van een gekoppelde lijst wiens enige knooppunt is Ross. 352 00:17:18,579 --> 00:17:22,660 En kunnen we dit nog een keer te doen, we kan hash Rachel en krijg hashcode 4. 353 00:17:22,660 --> 00:17:25,490 malloc een nieuw knooppunt, zet Rachel in het knooppunt, en zeggen dat een reeks locatie 354 00:17:25,490 --> 00:17:27,839 4 wijst nu naar het hoofd van een gekoppelde lijst wiens 355 00:17:27,839 --> 00:17:31,420 enige element toevallig Rachel zijn. 356 00:17:31,420 --> 00:17:33,470 >> OK, maar wat gebeurt er als We hebben een botsing? 357 00:17:33,470 --> 00:17:38,560 Laten we eens kijken hoe wij omgaan met botsingen met aparte chaining methode. 358 00:17:38,560 --> 00:17:39,800 Laten we hash Phoebe. 359 00:17:39,800 --> 00:17:41,094 We krijgen de hashcode 6. 360 00:17:41,094 --> 00:17:44,010 In ons vorige voorbeeld waren we net opslaan van de snaren in de array. 361 00:17:44,010 --> 00:17:45,980 Dit was een probleem. 362 00:17:45,980 --> 00:17:48,444 >> We willen niet afranselen Joey, en we hebben al 363 00:17:48,444 --> 00:17:51,110 gezien dat we een clustering kunnen krijgen problemen als we proberen en stap 364 00:17:51,110 --> 00:17:52,202 door en sonde. 365 00:17:52,202 --> 00:17:54,660 Maar wat als we gewoon een soort van behandel deze op dezelfde manier, toch? 366 00:17:54,660 --> 00:17:57,440 Het is net als het toevoegen van een element aan het hoofd van een gekoppelde lijst. 367 00:17:57,440 --> 00:18:00,220 Laten we gewoon malloc ruimte voor Phoebe. 368 00:18:00,220 --> 00:18:04,764 >> We zullen zeggen Phoebe's volgende pointer punten om de oude hoofd van de gelinkte lijst, 369 00:18:04,764 --> 00:18:07,180 en vervolgens 6 gewoon verwijst naar de nieuwe hoofd van de gelinkte lijst. 370 00:18:07,180 --> 00:18:10,150 En kijk nu, hebben we Phoebe veranderd. 371 00:18:10,150 --> 00:18:14,210 We kunnen nu slaan twee elementen hashcode 6, 372 00:18:14,210 --> 00:18:17,170 en we hebben geen problemen hebben. 373 00:18:17,170 --> 00:18:20,147 >> Dat is vrijwel alle er te chaining. 374 00:18:20,147 --> 00:18:21,980 En chaining is zeker de methode die is 375 00:18:21,980 --> 00:18:27,390 gaat het meest effectief voor u als te zijn u gegevens opslaan in een hash tabel. 376 00:18:27,390 --> 00:18:30,890 Maar deze combinatie van arrays en gelinkte lijsten 377 00:18:30,890 --> 00:18:36,080 samen om een ​​hash tafel echt te vormen drastisch verbetert uw vermogen 378 00:18:36,080 --> 00:18:40,550 om grote hoeveelheden gegevens en snel en efficiënt zoeken 379 00:18:40,550 --> 00:18:41,630 door die data. 380 00:18:41,630 --> 00:18:44,150 >> Er is nog steeds een meer datastructuur die er zijn 381 00:18:44,150 --> 00:18:48,700 dat misschien zelfs een beetje te beter in termen van het waarborgen 382 00:18:48,700 --> 00:18:51,920 dat onze insertie, deletie, en opzoeken tijden zijn nog sneller. 383 00:18:51,920 --> 00:18:55,630 En we zullen zien dat in een video op pogingen. 384 00:18:55,630 --> 00:18:58,930 Ik ben Doug Lloyd, dit is CS50. 385 00:18:58,930 --> 00:19:00,214