[Мусиц плаиинг] Даг Ллоид: До сада сте Знам доста о низовима, и знате много о повезаним листама. И имамо разговарају о прос анд цонс смо о томе разговарали повезане листе можете добити већа и мања, али они заузимају више величина. Низови су много јасније да користити, али они су рестриктивно у колико јер имамо да подесите величину Низ на самом почетку и онда смо заглавили са њим. 

Али то је, имамо прилично исцрпљени сви наши тема о повезаним листама и низова. Или имамо? Можда можемо да урадимо нешто још креативнији. И та врста даје Идеја хеш табели. 

Дакле, у хасх табели ћемо покушати комбинују низ са повезане листе. Идемо да се предности од низа, као и случајним приступом, бити у стању да само идите на низ Елемент 4 или низ елемената 8 без потребе да преко поновити. То је прилично брзо, зар не? 

Али ми такође желимо да имамо наше податке структура моћи да расту и смањују. Не треба нам, не знамо Желим да буде ограничена. И ми желимо да будемо у стању да додате и уклоните ствари врло лако, што ако се сећате, је веома комплекс са низом. И можемо назвати нова ствар хасх табела. 

А ако правилно спроведен, ми смо на неки начин узимања предности оба података структуре сте већ видели, низови и повезане листе. Убацивање може да почне да нагињу тета 1. Тета нисмо баш разговарали, али тета је само просек случај, шта се заправо дешава да се деси. Нећеш увек да имају најгори могући сценарио, и не увек ће имати најбољи сценарио, па шта је просечна сценарију? 

Па у просеку уметање у хеш табели може да почне да се приближи сталном време. И брисање могу да добију затворити у сталном време. И ИП адресу могу да добију затворити у сталном време. Је-- немамо податак Структура али да могу то да урадим, па то већ звучи као прилично велику ствар. Заиста смо ублажило недостаци сваког по себи. 

Да бисте добили ову представу упграде иако, ми треба да се преиспита како додамо података у структури. Посебно желимо да Сама подаци да нам каже где је треба да иде у структури. А ако онда треба да видимо да ли је у структура, ако морамо да га нађемо, желимо да погледамо податке поново и бити у стању да ефикасно, користећи податке, насумично јој приступе. Само гледајући подаци које треба да има идеја где се тачно смо ће га наћи у хасх табеле. 

Сада је мана хашх табела је да су стварно прилично лоше, при наручивању, или сортирање података. У ствари, ако почнете да их користе да нареди или врста Подаци губите све од Предности које сте претходно имала у смислу уметање и брисања. Време постаје ближи тета од н, и имамо основи назадовала у повезане листе. И тако смо само желите да користите хасх столови, ако не стало да ли се подаци поредани. За контекста у којем ћете их користити у ЦС50 вероватно не занима да се подаци сортирана. 

Тако хасх табела представља комбинацију два различита комада са којима смо упознати. Први је функција, која што се обично назива хасх функцију. И то хасх функција ће се вратити неке не-негативан цео број, који обично зовемо хасхЦоде, у реду? Други део је низ, који је способан за складиштење података типа ве Желим да поставите у структуру података. Ми ћемо задржати на повезан елемент листе за сада и само почети са основама хасх табелу да спусти главу око тога, и онда можда ћеш потрошити ваш ум мало када смо комбинују низовима и линк листе заједно. 

Основна идеја иако је да узмемо неке податке. Ми смо покренули те податке кроз хасх функција. Тако подаци се обрађују и избацује број, у реду? И онда са тим бројем ми само складишти податке желимо да сачувате у Арраи на тој локацији. Тако, на пример да можда имамо ово хасх табела низова. Има 10 елемената у њој, тако можемо уклопити 10 конце у њој. 

Рецимо желимо да хасх Јохн. Дакле, Јована као података желимо да убаците у овом хасх табели негде. Где смо га ставили? Па обично са неким Арраи до сада смо вероватно би га ставите у арраи локацији 0. Али сада имамо ову нову функцију хасх. 

И рецимо да трчимо Јохн кроз овај хеш функције и то избацује 4. Па то је где смо хтети да стави Јохн. Желимо да стави Јована у арраи локацији 4, јер ако хасх Јохн Поново: хајде да касније да смо желите да претражите и види ако Џон постоји у овом хасх табле-- све што треба да урадите Да ли је пролазе кроз исти хасх функција, добити број 4 из, и бити у стању да нађем Џона одмах у нашој структури података. То је прилично добро. 

Рецимо сад да радимо ово опет, желимо да хасх Павла. Желимо да додате Паул у овом хасх табели. Рецимо да смо овај пут води Павле кроз хеш функције, хасхЦоде који се генерише је 6. Па сада можемо ставити Паул у низу локацији 6. А ако треба да се угледају ли Павле је у овом хасх табели, све што треба да урадите је да покренете Пол опет кроз хеш функције а ми ћемо добити 6 опет. 

И онда да погледамо на локацији низа 6. Паул тамо? Ако је тако, он је у хасх табели. Да ли је Павле не? Он није у хасх табели. То је прилично једноставан. 

Сада како се дефинише хасх функцију? Па заиста нема граница до Број могућих хеш функцијама. У ствари, постоји велики број заиста, стварно добри на Интернету. Постоји велики број заиста, стварно лоши на Интернету. Такође је прилично лако да напишем једну лошу. 

Шта чини А Гоод хасх функција, зар не? Па добро хасх функција треба користити само су подаци који се хеширану, и све податке који се хеширану. Тако да не желите да користите све-- не уграде ништа друго осим подацима. И желимо да користимо све податке. Ми не желимо само да користи комад од тога, желимо да користимо све то. Хеш функција треба да такође бити детерминистичка. Шта то значи? Па то значи да сваки пут ми проћи потпуно исти податак у хасх функцију увек добити исту хасхЦоде напоље. Ако прође Јохн Инто тхе хасх функција изађем 4. Требало би да могу то да урадим 10.000 пута, а ја ћу увек добити 4. Значи нема случајних бројева ефикасно могу бити укључени у нашој хасх таблес-- у нашим хеш функције. 

Хеш функција треба да се равномерно расподелити податке. Ако сваки пут када покренете податке кроз хасх функција добијете хасхЦоде 0, то је вероватно није толико велика, зар не? Вероватно Желиш да велики распон хеш кодова. Такође, ствари се могу ширити у цијелој табели. Такође било би сјајно ако стварно слични подаци, као што су Јован и Јонатхан, Можда су раширили да одмери различите локације у хасх табеле. То би било лепо предност. 

Ево примера хеш функције. Ја сам написао ово горе раније. То није посебно добра хасх функција због разлога који немају баш беар иде у сада. Али видиш шта се овде дешава? Чини се као да прогласи променљиву зове сума и постављање га једнако 0. А онда очигледно радим нешто све док стрстр [ј] није једнако да Бацксласх 0. Шта ја тамо? 

Ово је у суштини само једна начин спровођења [? СТРЛ?] и откривање када сте стигли до краја стринга. Дакле, не морам да стварно израчунати дужину стринга, Ја само користим када сам ударио обрнута коса црта 0 карактер Знам Ја сам стигао до краја стринга. И онда ћу задржати итератинг кроз тај низ, додајући стрстр [Ј] да сумирамо, а затим у крај дана ће се вратити сум мод ХАСХ_МАКС. 

У основи свега овога хасх Функција ради се саберу све АСЦИИ вредности мој стринг и онда је враћа неке хасхЦоде моддед од ХАСХ_МАКС. Вероватно је величине моје низа, зар не? Не желим да се добро хасх кодови ако је мој низ је величине 10, Ја не желим да будем добијање од хасх кодови 11, 12, 13, ја не могу да ствари у те локације низа, то би било незаконито. Ја бих претрпети сегментације грешку. 

Сада овде је још један брз страну. Генерално се вероватно неће Желим да напишем своје хеш функција. То је заправо мало уметност, а не наука. И има доста који иде у њих. Интернет, као што сам рекао, је пуна стварно добрих хеш функције, и требало би да користе интернет у финд хеш функција, јер је стварно некако непотребна губљење времена да створи свој. 

Можете писати једноставне оне за потребе тестирања. Али када ствари иду у старт хасхинг податке и складиштења у хасх табелу си Вероватно це хтети да користите неку функцију која је генерисана за вас, која постоји на интернету. Ако само буди сигуран да наведе своје изворе. Нема разлога да плагирају ништа овде. 

Рачунар наука заједница је дефинитивно расте, и заиста вредности опен соурце и то је заиста важно да наведе своје изворе, тако да људи можете добити приписивање за рад да су они раде за добробит заједнице. Дакле, увек бити суре-- и не само за хасх функције, али углавном када вас користити код са спољашњег извора, Увек ците свој извор. Дајте кредит особу која је урадила неке од рада, тако да не морате да. 

ОК, хајде поново ово хасх табела за секунду. Ово је место где смо оставили искључује након што уметнута Џон и Пол у овом хасх табели. Да ли видите проблем? Можда ћете видети два. Али конкретно, зар не погледајте овај могући проблем? 

Шта ако хасх Ринго, и то Испада да је након обраде да су подаци кроз хеш функције Ринго такође генерише на хасхЦоде 6. Већ имам податке на хасхцоде-- низ локација 6. Тако да је вероватно ће бити мало проблем за мене сада, зар не? 

Ми то називамо судар. И судара се јавља када два комада података пролазе кроз исти хасх Функција давати исти хасхЦоде. Претпоставља се и даље желимо да обоје комада података у хасх табеле, иначе не бисмо се ради Ринго произвољно кроз хеш функције. Ми вероватно желе да се Ринго у тај низ. 

Како ми то радимо, иако, ако је и Паул и принос хасхЦоде 6? Ми не желимо да замените Павла, желимо да Павле бити тамо. Зато морамо да нађемо начин да се елемената у хеш табели која и даље чува Наши брзи убацивање и брз поглед горе. А један од начина да се носи са тим је уради нешто што се зове линеарни прескок. 

Користећи овај метод ако имамо судар, па, шта да радимо? Па не можемо да га ставимо у арраи локацији 6, или било хасхЦоде је генерисана, хајде да га стави на хасхЦоде плус 1. И ако је то пуна Хајде да стави га у хасхЦоде плус 2. Предност овог бића ако је није тачно где ми мислимо да јесте, и морамо да бисте започели претрагу, Можда не морамо да идемо предалеко. Можда не морамо тражити све н елементи хасх табеле. Можда морамо тражити пар њих. 

И тако смо увек тежи ка да је просјечна случај био близу 1 ВС близу н, па можда да ће радити. Дакле, хајде да видимо како ово можда неће радити у стварности. И да видимо да ли можда можемо открити проблем који може доћи овде. 

Рецимо да хасх Барта. Дакле, сада ћемо покренути нови сет жица кроз хеш функције, и трчимо Барт кроз хасх функција, добијамо хасхЦоде 6. Ми погледамо, видимо 6 је празан, тако да можемо ставити Барт тамо. 

Сада хасх Лизу и да Такође генерише хасхЦоде 6. Па сад кад смо користећи овај линеарни прескок начин почињемо у 6, видимо да 6 је пуна. Не можемо ставити Лиса у 6. Па где идемо? Идемо до 7. 7 је празна, тако да ради. Дакле, хајде да ставимо Лиса тамо. 

Сада хасх Хомер и добијамо 7. У реду добро знамо да је пун 7 сада, тако да не могу да Хомер тамо. Дакле, идемо до 8. Да ли је 8 доступан? Да, и 8 блиски до 7, па ако морамо да почнемо потрази смо неће морати да иде предалеко. И тако ставимо Хомера у 8. 

Сада хасх Меги и враћа 3, хвала богу ми смо у стању да само стави Маггие тамо. Ми не треба да урадите било врста сондирање за то. Сада хасх Марџ, и Марџ такође враћа 6. 

Па 6 је пуна, 7 је пуна, 8 је пун, 9, у реду хвала Богу, 9 је празна. Ја могу ставити Марге на 9. Већ можемо видети да смо почели да се овај проблем где сада смо почевши да се протегне ствари некако од далеко од својих хасх кодова. И то тета 1, тај просек случај буде константна времена, почиње да се мало море-- Почињем да мало теже ка тхета н. Ми смо почели да губе да Предност хеш табеле. 

Овај проблем који смо управо видели је нешто што се зове груписање. И оно што је заиста лоше о груписање је да када тебе има два елемента који су раме уз стране то чини још вероватније, ви имате двоструко шанса да идеш да још један судар са тим кластер, и кластер ће порасти за један. А ти ћеш стално расте и расте ваш вероватноћа да судар. И на крају то је само тако лоше како не сортирање података уопште. 

Други проблем је што, иако даље, па сада до ове тачке, смо управо били некако разумевање шта хасх сто је, и даље само простор за 10 низова. Ако желимо да наставимо да хасх грађани Спрингфиелд, можемо само да њих 10 унутра. И ако покушамо и додај 11. или 12., немамо где да их стави. Могли би да се врти око у кругови покушавају да пронађу празан место, а ми можда запети у бескрајној петљи. 

Дакле, ова врста погодна за идеје нечега што се зове цхаининг. И ово је место где ћемо довести повезаних листа назад у слику. Шта ако уместо чувања само сама података у низу, сваки елемент низа могао држите више комада података? Па то нема смисла, зар не? Ми знамо да само низ цан холд-- сваки елемент низа могу само једну комад података те врсте података. 

Али шта ако је тип података је повезана листа, зар не? Па шта ако сваки елемент низа био је показивач на челу повезане листе? И онда бисмо могли изградити оне повезане листе и расте их произвољно, јер повезане листе дозвољавају да расте и смањују много више флексибилно него низ ради. Па шта ако сада користимо, ми искористити, зар не? Почињемо да расту ове ланце из ових арраи локација. 

Сада можемо да стане неограничен количина података, или не бесконачна, произвољна количина података, у нашем хасх табеле без икаквог налетим проблем судара. Такође смо елиминисани груписање радећи ово. И добро знамо да када смо убацили у повезане листе, ако се сећате из наше видео на повезаних листи, појединачно повезане листе и двоструко повезане листе, То је операција константа време. Ми само додавање на фронт. 

А за Погледам горе, па знамо да погледате у повезане листе може бити проблем, зар не? Морамо да претражујете је од почетка до краја. Нема случајно приступ у повезане листе. Али, ако уместо једног повезан Листа гдје би ИП адресу бити О Н, сада имамо 10 повезане листе, или 1.000 повезане листе, сада је о од н подељено са 10, или О од н подељено 1.000. 

И док смо причали теоретски о сложености занемаримо константе, у реалном свет те ствари заиста важно, jel tako? Ми ћемо заправо приметити да се то деси да ради 10 пута брже, или 1.000 пута брже, јер смо дистрибуирање један дуг ланац преко 1.000 мањих ланаца. И тако сваки пут морамо тражити кроз један од тих ланаца можемо игноришу 999 ланце не брину о, и само тражи тај. 

Који је у просеку бе 1.000 пута краће. И тако ми смо и даље некако тежи ка том случају просечне да буде константан времена, али само зато што су усклађивање дељењем неком огромном сталним фактором. Хајде да видимо како би ово могло заправо изгледају иако. Дакле, ово је тараба сто смо имали пре него што смо прогласили хасх табелу која био способан за складиштење 10 конце. Нећемо више да урадим. Ми већ знамо да ограничења тог метода. Сада наша хасх табела ће бити низ од 10 чворова, показивачи шефовима повезаних листи. 

И сада је нула. Сваки од тих 10 показивача нулл. Нема ништа у нашој хасх сто сада. 

Сада почнимо да се неке ствари у ову хасх табеле. И хајде да видимо како ова метода је да нам користи мало. Идемо сада хасх Јоеи. Ми ћемо се покренути низ Јоеи кроз хасх функција и враћамо 6. Па шта сада да радимо? 

Па сада раде са повезаним листама, не радимо са низовима. И када радимо са повезаним листама ми знам да треба да почне динамички додељивање простора и изградњу ланаца. То је врста Како-- оне су срж елементи изградње повезану листу. Тако је нека динамички доделити простор за Јоеи, а онда да га додате у ланцу. 

Дакле, сада погледајте шта смо урадили. Када смо хасх Јоеи имамо хасхЦоде 6. Сада је показивач на арраи локацији 6 указује на челу повезане листе, а сада је то једини елемент повезане листе. И чвор у томе линкед лист је Џои. 

Дакле, ако треба да се угледају Јоеи касније, управо смо хасх Јоеи опет, добијамо 6 поново јер наша хасх функција је детерминистички. А онда смо се крећу од главе од повезане листе указао да од низа локација 6, и можемо поновити преко које покушавају да пронађу Јоеи. А ако градимо наше хасх табле ефикасно, а наш хасх функција ефикасно добро дистрибуира податке, у просеку свакој од ових повезани Листе на сваком месту арраи ће бити 1/10 величине ако се Управо је имао као један велики линкед лист са свиме у њему. 

Ако ми дистрибуирамо да огромна повезан Листа преко 10 повезаних листи Свака листа ће бити 1/10 величина. И тако 10 пута брже за претраживање преко. Дакле, хајде да поновимо. Идемо сада хасх Росс. 

И рецимо Росс, када смо то хасх код вратимо је 2. Па сада имамо динамички додели нови чвор, ставимо Росс у том чвору, и сада рећи низ локација 2, уместо указујући на нулл, указује на челу повезан Листа чија је једина чвор је Рос. И можемо да урадимо ово још једном, ми може хасх Рејчел и да хасхЦоде 4. Маллоц нови чвор, пут Рацхел у чвор и изговорите арраи локације 4 сада указује на главу од повезане листе чији Једини елемент дешава да се Рејчел. 

У реду, али шта се дешава ако имамо судар? Хајде да видимо како можемо носити сударе користећи посебан метод цхаининг. Идемо хасх Фиби. Схватили смо хасхЦоде 6. У нашем претходном примеру смо били складиштење конце у низу. То је био проблем. 

Ми не желимо да разбије Џои, и већ смо види да можемо добити неки груписање Проблеми Ако покушамо и корак кроз и сонда. Али, шта ако смо некако третирати ово на исти начин, зар не? То је као додавање елемент на челу повезане листе. Хајде само маллоц простор за Фиби. 

Ми ћемо рећи Фиби је следећи показивача бодова старом главе повезане листе, и онда само 6 поена до нови шеф повезане листе. И сад погледај, променили смо Фиби у. Сада можете сачувати два елементи са хасхЦоде 6, и немамо никаквих проблема. 

То је отприлике све ту је уланчавања. И Уланчавање је дефинитивно метод који је ће бити најефикаснији за вас ако сте чувања података у хасх табели. Али ово комбинација низови и повезане листе заједно формирају хеш табели јако драматично побољшава ваше способности за складиштење велике количине података, и врло брзо и ефикасно претраживање кроз тих података. 

Има још још један структура података тамо да би чак бити мало боље смислу гарантовања да је наш уметање, брисање и Лоок Уп пута су још брже. И ми ћемо видети да у видео на покушаја. Ја сам Доуг Ллоид, ово је ЦС50.