[Музички] Даг LLOYD: До сега Знаеме многу за низи, и знаеш многу за поврзани листи. И ние сме се разговара за добрите и лошите страни, ние сме разговаравме за тоа дека поврзани листи може да добие поголеми и помали, но тие заземаат повеќе големина. Низи се многу лесно да се користат, но тие се рестриктивни во колку како што ние треба да го поставите големината на низата на самиот почеток а потоа ние сме заглавени со неа. Но, тоа е, ние сме доста исцрпени сите наши теми во врска со поврзани листи и низи. Или ние? Можеби и ние може да направи нешто дури и повеќе креативни. И тој вид на позајми идејата на хаш табелата. Па во хаш табелата ние ќе треба да се обиде комбинираат со низа поврзани листа. Ние ќе треба да ги искористат предностите што на низата, како случаен пристап, да биде во можност да се оди само до низа елемент на 4 или елемент од низата 8 без да iterate во пречник. Тоа е прилично брзо, нели? Но, ние, исто така, сакаат да имаат нашите податоци структура да биде во можност да расте и да се намали. Нам не ни треба, ние не сакаат да бидат ограничени. И ние сакаме да биде во можност да додадете и отстранувате работи многу лесно, што ако се сеќавате, е многу сложен со низа. И ние може да се јавите на оваа нова работа хаш табелата. И ако правилно се користи, ние сме вид на преземање предностите на податоци структури веќе сте го виделе, низи поврзани листи. Вметнување да почнете да стремат кон тета на 1. Тета не сме навистина дискутира, но тета е само просечна случај, она што всушност се случува да се случи. Вие не секогаш се случува да се имаат најлош случај сценарио, и вие не сте секогаш ќе има најдоброто сценарио, па што е просечната сценарио? И во просек вметнување во хаш табелата може да почне да се блиску до временска константа. И бришење може да се добие затвори на временска константа. Пребарување и да се добијат затвори на временска константа. That's-- немаме податоци структура сепак тоа може да го направат тоа, па така ова веќе звучи како прилично голема работа. Ние сме навистина ублажија недостатоците на секоја на свој. Да се ​​добие оваа изведба надградите иако, ние треба да се преиспита начинот на кој ќе се додаде податоци во структурата. Посебно сакаме податоци себе да ни каже каде треба да одам во структурата. И ако ние тогаш треба да се види дали тоа е во структурата, ако ние треба да го најде, ние сакаме да се погледне на податоци еднаш и да биде во состојба ефикасно, со користење на податоци, случајно дојде до неа. Само со гледање на податоци треба да имаме идеја за тоа каде точно сме нема да го најдете во хеш табелата. Сега во надолна линија на хаш маса е дека тие се навистина прилично лошо во наредување или подредување на податоците. И всушност, ако почнете да ги користите за да го нарачате или вид податоците ќе ги изгубите сите од предности што претходно имаше во однос на вметнување и бришење. Времето станува поблиску до тета на n, и ние сме во основа назадувале во поврзани листа. И така ние само сакате да го користите хаш маси, ако ние не се грижат за дали податоците се подредени. За контекстот во кој ќе ги користите во CS50 што веројатно не се грижат дека податоците се подредени. Па хаш табелата е комбинација од два различни парчиња со кои ние сме запознаени. Првиот е во функција, што ние обично ги именуваме хеш функција. Хеш функција и дека ќе врати некои не-негативен број, кој ние обично го нарекуваме hashCode, во ред? Вториот дел е низа, што е способен за чување на податоци од типот ние сакате да го ставите во структурата на податоците. Ние ќе се одржи надвор од поврзани листа елемент за сега и само да започнеме со основите на хаш табелата за да ја добиете вашата глава околу неа, а потоа ние ќе можеби удар главата малку, кога ние комбинираат низи и линк листи заедно. Основната идеја иако е ги некои податоци. Трчаме кои податоци преку на хаш функција. Така и на податоците се обработуваат и тоа плука голем број, во ред? А потоа со тој број ние само чување на податоци ние сакаме да се сместат во низа на таа локација. Така на пример имаме можеби ова хаш табелата на жици. Тоа е се здобија 10 елементи во него, па ние може да се вклопат 10 конци во него. Да речеме дека сакате да хаш Јован. Па Џон како на податоците што сакаме да го вметнете во оваа хаш табелата некаде. Каде да го стави? И обично се со Низа досега ние најверојатно ќе го стави во низа локација 0. Но, сега имаме оваа нова хеш функција. И да речеме дека ние се кандидира Џон преку овој хеш функција и тоа се плука од 4. Па тоа е каде сме ќе сакаат да се стави Јован. Ние сакаме да се стави во Јован локација низа 4, затоа што ако ние хаш Џон again-- да речеме подоцна ние сакате да пребарувате и да видиме ако Џон постои во овој хаш table-- сите ние треба да направите е го стартувате преку истиот хеш функција, го добиете бројот 4 надвор, и да бидат способни да се најде Џон веднаш во нашите податоци структура. Тоа е прилично добро. Да речеме дека ние сега да го направите ова повторно, ние сакаме да хаш Павле. Ние сакаме да додадете Пол во оваа хаш табелата. Да речеме дека овој пат се кандидира Павле преку функцијата за хашиш, на hashCode која е генерирана е 6. Па сега можеме да се стави Павле локација во низа 6. И ако ние треба да се погледне до тоа дали Павле е во овој хаш табелата, сите ние треба да направите е да извршите Пол преку функцијата на хаш повторно и ние ќе треба да се добие 6 повторно. А потоа ние само да се погледне на локација низа 6. Павле е таму? Ако е така, тој е во хеш табелата. Павле не е таму? Тој не е во хеш табелата. Тоа е прилично јасна. Сега како да се дефинира хеш функција? И таму е навистина нема ограничување на број на можни функција за дешифрирање. Всушност, има голем број на навистина, навистина добрите и на интернет. Има голем број на навистина, навистина лошо оние на интернет. Тоа е исто така многу лесно да се напише лоша. Значи она што го прави еден добар хеш функција, нели? И добра хеш функција треба користете само се hashed податоците, и сите на податоците кои се hashed. Така што не сакате да го користите anything-- ние не се вклучат ништо друг освен на податоци. И ние сакаме да ги користите сите на податоците. Ние не сакаме да се само користење на парче од него, ние сакаме да ги користите сите од неа. Хаш функција треба исто така, да биде детерминистичка. Што значи тоа? Па тоа значи дека секој пат кога ние помине иста парче на податоци во функција на хаш ние секогаш добиете истиот hashCode надвор. Ако поминувам Јован во хеш функција ќе излезам 4. Јас треба да биде во можност да го стори тоа 10.000 времиња и јас секогаш ќе го добие 4. Па нема случајни броеви ефикасно можат да бидат вклучени во нашата хаш tables-- во нашата хаш функции. Хаш функција исто така треба да рамномерно дистрибуираат податоци. Ако секој пат кога ќе се кандидира на податоци преку хеш функција ќе го добиете hashCode 0, Тоа веројатно не е толку голема, нели? Веројатно сакате да се големи голем број на хаш кодови. Исто така, работите може да се шири надвор во текот на табелата. А исто така тоа ќе биде одлично ако навистина слични податоци, како Џон и Јонатан, можеби се шират да тежат различни локации во хеш табелата. Тоа би било убаво предност. Еве еден пример на хеш функција. Напишав еден до порано. Тоа не е некој особено добра хеш функција од причини што не ми се носат случува во моментов. Но, гледате што се случува овде? Ми се чини дека ние сме прогласување на променлива наречен сума и поставување тоа еднаков на 0. И тогаш очигледно правам нешто па додека strstr [j] не е еднаква да црта 0. Што правам тука? Ова е во основа само уште еден начин на спроведување [? strl?] и откривање кога сте достигнала крајот на стрингот. Па јас не треба да се, всушност, пресмета должината на стрингот, Јас сум само со помош кога ќе се погоди на обратна коса црта 0 карактер знам Јас сте достигнавме крајот на стрингот. А потоа јас ќе одам да се задржи процесирањето преку таа низа, додавајќи strstr [j] да ги сумира, а потоа на крајот на денот ќе се врати сума МО HASH_MAX. Во суштина сето ова хаш функција го прави е да се збира сите вредности на ASCII мојата стринг, и тогаш тоа е враќаат некои hashCode modded страна HASH_MAX. Тоа е веројатно големина од моите низа, нели? Не сакам да се добива хаш кодови, ако моите низа е со големина 10, Не сакам да се добива надвор кодови хаш 11, 12, 13, не можам да се стави работите во тие локации на низата, дека ќе биде нелегално. Би страдаат дефект на сегментација. Сега тука е уште една брза настрана. Генерално најверојатно нема да го сакате да напишете своја сопствена функција за дешифрирање. Тоа е, всушност, малку уметност, а не наука. И има многу што оди во нив. На интернет, како што реков, е полна навистина добри функции хаш, а вие треба да го користат интернетот за да се најдете хаш функции бидејќи тоа е навистина само вид на непотребен губење на време да се создаде своја сопствена. Може да се пишуваат едноставни оние за тестирање цели. Но кога ќе всушност се случува да се почне hashing податоци и складирање во хаш табелата сте веројатно нема да сакате да се користи некоја функција која е генерирана за вас, кој постои на интернет. Ако само бидете сигурни дека ќе се да се цитираат извори. Нема причина да се плагиатствувам нешто тука. Компјутерски науки заедница е дефинитивно расте, и навистина вредности софтвер со отворен код, и тоа е навистина важно цитирањето на извори, така што луѓето да добиете заслуга за работата дека тие се прави за доброто на заедницата. Затоа секогаш бидете sure-- и не само за хаш функции, но, генерално, кога ќе користете кодот од надвор извор, секогаш цитирањето на изворот. Даде кредит на личноста кој го некои од работа, па вие не мора да се. OK, па ајде да го ревидира овој хаш табелата за една секунда. Ова е местото каде што ние ја напушти исклучува по што вметнува Јован и Павле во оваа хаш табелата. Гледате ли проблемот тука? Може да видите две. Но, особено, да се направи види ваквите проблеми? Што ако сум хаш Ринго, и тоа Излезе дека по обработката тие податоци преку функцијата на хаш Ринго исто така генерирана за hashCode 6. Јас веќе имам на податоци во hashcode-- локација низа 6. Па тоа не е веројатно ќе биде малку на проблем за мене сега, нели? Ние го нарекуваме овој судир. И судирот се случува кога две делови на податоци извршена во текот на истиот хеш функција се добие принос од истиот hashCode. Се претпоставува дека ние се уште сакаат да добијат двете делови на податоци во хаш табелата, во спротивно не ќе се работи Ринго произволно преку хаш функција. Ние веројатно ќе сакате да се добие Ринго во таа низа. Како ние да го направи тоа, иако, ако тој и Павле и принос hashCode 6? Ние не сакаме да ја пребришете Павле, Павле сакаме да бидеме таму. Значи ние треба да се најде начин да се добие елементи во хеш табелата што уште задржува нашиот брз вметнување и брз поглед нагоре. И еден начин да се справи со него е да се направи нешто што се нарекува линеарно љубопитство. Користењето на овој метод, ако имаме судир, добро, што ќе правиме? И ние не можеме да го стави во место низа 6, или што и hashCode е генерирана, ајде да го доведе во hashCode плус 1. И ако тоа е целосна ајде го стави во hashCode плус 2. Во корист на ова суштество, ако тој е не е точно каде што мислиме дека тој е, и ние треба да почнат да бараат, Можеби и ние не треба да се оди премногу далеку. Можеби и ние не треба да го бара сите n елементи од хаш табелата. Можеби и ние треба да го бара неколку од нив. И така ние сме уште се тежнее кон дека просечен случај да биде блиску до 1 vs во близина на n, па можеби тоа ќе работат. Значи, да се види како оваа би можеле да работат во реалноста. И ајде да видиме дали можеби и ние може да се открие проблемот што може да се случи тука. Да речеме дека ние хаш Барт. Па сега ние се случува да се кандидира за нов сет на жици преку функцијата за хашиш, и трчаме Барт преку хаш функција, да добиеме hashCode 6. Ги погледнеме, ќе видиме 6 е празно, за да може да се стави Барт таму. Сега ние хаш Лиза и дека исто така, генерира hashCode 6. Па сега дека ние сме со користење на овој метод Започнуваме во 6 линеарни љубопитство, гледаме дека 6 е полна. Ние не може да се стави во 6 Лиза. Значи каде да одиме? Ајде да одиме во 7. 7 е празна, па што работи. Значи, да се стави Лиза таму. Сега ние хаш Хомер и да добиеме 7. Добро добро знаеме дека 7 е полн сега, така што не може да се стави на Хомер таму. Па ајде да одиме до 8. Достапно е 8? Да, и 8 е блиску до 7, па ако ние треба да почнат да бараат ние сме не се случува да треба да одат премногу далеку. И така да се стави на Хомер во 8. Сега ние хаш Меги и се враќа 3, фала му на Бога ние сме во состојба да се ставив Меги таму. Ние не треба да направите било вид на љубопитство за тоа. Сега ние хаш Марџ, и Марџ, исто така, се враќа 6. И 6 е полна, 7 е полна, 8 е полна, 9, во ред, фала богу, 9 е празна. Можам да се стави Марџ во 9. Веќе можеме да видиме дека ние сме почнуваат да имаат овој проблем, каде што сега сме почнуваат да се водат работите вид од далеку од своите хаш кодови. И дека тета од 1, дека просечен случај на да се биде постојана време, почнува да се добие малку more-- почнуваат да имаат тенденција малку повеќе кон тета на n. Ние сме почнуваат да се изгуби тој Предноста на хаш маси. Овој проблем кој ние само видов нешто што се нарекува групирање. И она што е навистина лошо за кластеринг е дека некогаш сте сега има два елементи кои се рамо до страна тоа го прави уште поверојатно, имате двојно шанса, дека си оди да има друг судир со тоа кластер, и Кластерот ќе се зголеми за еден. И ќе продолжи да расте и расте вашиот веројатноста на постоење на судир. И на крајот тоа е исто толку лоша како да не сортирање на податоците на сите. Друг проблем е тоа што иако сепак, и досега се до оваа точка, ние само се вид на разбирање на она што е хаш табелата, ние се уште имаат само простор за 10 жици. Ако сакаме да продолжи да хаш граѓаните на Спрингфилд, ние може да се добие само 10 од нив во таму. И ако се обидеме и да додадете 11-ти или 12-ти, ние немаме каде да ги стави. Ние може само да се врти наоколу во кругови се обидува да најде празен простор, и ние можеби се заглавени во бесконечна јамка. Така овој вид на подложна на идејата на нешто што се нарекува врзувањето. И ова е местото каде што ние ќе треба да се донесе поврзани листи назад во сликата. Што ако, наместо на само чување самите податоци во низа, секој елемент од низата би можел се одржи на повеќе делови на податоци? Па тоа не дава никаква смисла, нели? Ние знаеме дека низа може само hold-- секој елемент од низата може да се одржи само едно парче на податоците од тој тип на податок. Но, што ако тој тип на податоци е поврзана листа, нели? Па што ако секој елемент од низата беше покажувач кон главата на поврзани листа? И потоа можеме да изградиме оние поврзани листи и да ги расте произволно, бидејќи поврзани листи дозволи ни да расте и да се намали многу повеќе флексибилно од низа го прави тоа. Па што ако ние сега се користи, Ние потпора ова, нели? Ние почне да расте овие синџири Од овие локации низа. Сега ние може да се вклопат бесконечно износот на податоци, или не е бесконечна, произволен износ на податоци, во нашата хаш табелата без воопшто да работи во проблемот на судир. Ние сме, исто така, елиминирани групирање со тоа. И добро знаеме дека кога ние вметнете во поврзани листа, ако се потсетиме од нашата видео на поврзани листи, поединечно поврзани листи и двојно поврзани листи, тоа е постојана време операција. Ние сме само додавање на фронт. И гледам нагоре, и ние го знаеме дека погледнеме во поврзани листа може да биде проблем, нели? Ние треба да го бара преку тоа од почеток до крај. Нема случаен пристап во поврзани листа. Но, ако наместо да се има еден поврзан листа, каде што еден пребарување ќе биде O на n, сега имаме 10 поврзани листи, или 1.000 поврзани листи, сега тоа е О од n поделено со 10, или O од n поделено со 1.000. И додека ние се зборува теоретски за комплексноста ние непочитување константи, во реалниот светот овие работи навистина важно, нели? Ние, всушност, ќе се забележи дека тоа се случи за да работи 10 пати побрзо, или 1.000 пати побрзо, затоа што ние сме дистрибуира еден долг синџирот низ 1.000 помали синџири. И така секој пат кога мораме да пребарување преку еден од оние што можеме синџири игнорира 999 синџири што не се грижат за, и само да пребарувате оној. Кој е во просек до биде 1.000 пати пократко. И така ние се уште се вид на тежнее кон овој просек случај биде постојана време, но само затоа што ние се проширува делење со некои големи константен фактор. Ајде да видиме како може ова да всушност изгледаат, секако. Па ова беше хаш табелата имавме пред да се прогласи дека хаш табелата е способен за чување на 10 жици. Ние нема да го направи тоа повеќе. Ние веќе го знаеме ограничувањата на тој метод. Сега нашата хаш табелата ќе биде низа од 10 јазли, показалки до шефовите на поврзани листи. И во моментов тоа е нула. Секој еден од овие 10 совети е нула. Нема ништо во нашата хаш табелата во моментов. Сега ајде да почнеме да се стави некои работите во оваа хаш табелата. И да видиме како овој метод е ќе ни корист малку. Ајде сега хаш Џои. Ќе се работи на низа Џои преку хеш функција и се враќаме 6. Па што ќе правиме сега? И сега работи со поврзани листи, ние не работиме со низи. И кога ние работиме со поврзани листи ние знаеме ние треба да почне да се динамички распределба на простор и изградба на синџири. Тоа е вид на how-- тие се јадрото елементи на градење на поврзани листа. Па да се динамички одвои простор за Џои, и тогаш ајде да го додадете во синџирот. Па сега се погледне она што го направиле. Кога ние хаш Џои добивме hashCode 6. Сега на покажувачот на локацијата низа 6 укажува на главата на поврзани листа, и во моментов тоа е единствениот елемент на поврзани листа. И јазол во кој поврзани листа е Џои. Значи, ако ние треба да се погледне до Џои подоцна, ние само хаш Џои повторно, добиеме 6 еднаш, бидејќи нашите хеш функција е детерминистички. А потоа ќе почнеме на чело на поврзани листа посочи да по локација низа 6, а ние може да iterate преку кои се обидува да најде Џои. И ако можеме да ја градиме нашата хаш табелата ефикасно, и нашите хеш функција ефикасно за дистрибуција на податоците добро, во просек секој од оние кои се поврзани листи на секоја локација низа ќе биде со големина на 1/10 ако ние само што го имаше како една огромна поврзани листа со сè во него. Ако ние се дистрибуираат таа огромна поврзани список низ 10 поврзани листи секоја листа ќе биде 1/10 големината. А со тоа и 10 пати побрзо да пребарувате низ. Па ајде да го направите ова повторно. Ајде сега хаш Рос. И да речеме Рос, кога тоа го правиме кодот хаш ќе се вратам е 2. Па сега ние динамички да се издвои нов јазол, ќе стави Рос во тој јазол, и ние велиме сега локација низа 2, наместо да укажува на нула, укажува на чело на една врска листа чиј единствен јазол е Рос. И можеме да го направиме ова уште еднаш, ние може хаш Рејчел и да добијат hashCode 4. Примерок нов јазол, се стави во Рејчел на куп, и да каже на локација низа 4 сега укажува на главата на поврзани листа чии единствениот елемент се случува да биде Рејчел. Во ред, но она што се случува ако имаме судир? Ајде да видиме како ќе се справи судири користење на одделни методот на врзувањето. Ајде хаш Фиби. Добиеме hashCode 6. Во претходниот пример бевме само складирање на жиците во низа. Ова беше проблем. Ние не сакаме да clobber Џои, и ние сме веќе види дека ние може да се добијат некои кластеринг проблеми ако се обидеме и чекор преку и сонда. Но што ако ние само вид на лекување на овој ист начин, така? Тоа е исто како додавајќи елемент на главата на поврзани листа. Ајде само Примерок простор за Фиби. Ние ќе се каже следното покажувачот поени на Фиби на стариот шеф на поврзани листа, и потоа 6 само укажува на Новиот шеф на поврзани листа. И сега изгледа, ние сме промениле Фиби во. Сега ние може да се сместат двајца елементи со hashCode 6, и немаме никакви проблеми. Тоа е доста на сите таму е да се врзувањето. И врзувањето е дефинитивно методот што е ќе бидат најефективни за вас, ако сте складирање на податоци во хаш табелата. Но оваа комбинација на низи поврзани листи заедно за да формираат хаш табелата навистина драматично ја подобрува вашата способност за чување на големи количини на податоци, и многу брзо и ефикасно пребарување преку кои податоците. Сеуште постои уште еден податочна структура таму дека дури и може да биде малку подобро во однос на гарантирањето дека нашите вметнување, бришење, и гледам нагоре Времето е дури и побрзо. И ќе видиме дека во видео на обидува. Јас сум Даг Лојд, ова е CS50.