[За възпроизвеждане на музика] Дъг LLOYD: До сега ти знаете много за масиви, и вие знаете много за свързани списъци. И ние сме се обсъди плюсове и минуси, ние сме обсъдено, че свързани списъци може да получи по-големи и по-малки, но те заемат повече размери. Масивите са много по-лесно да се използвате, но те са рестриктивни дотолкова тъй като ние трябва да зададете размера на масива в самото начало и след това ние си остана с него. 

Но това е, ние сме доста много изчерпани всички наши теми за свързани списъци и масиви. Или имаме? Може би можем да направим нещо дори и по-креативни. И това нещо поддава идеята за хеш таблица. 

Така че в хеш таблица ние ще се опитаме комбинирате масив с свързан списък. Отиваме да вземат предимствата на масива, като произволен достъп, е в състояние да просто отидете на масив елемент 4 или елемент от масива 8 без да се налага да превъртите цяла. Това е доста бързо, нали? 

Но ние също така искаме да имаме нашите данни структура да може да расте и да се свие. Ние не се нуждаем, не го правим Искам да бъде ограничено. И ние искаме да бъде в състояние за добавяне и премахване неща много лесно, което, ако си спомняте, е много сложна с масив. И ние можем да наречем това нещо ново хеш таблица. 

И ако се прилагат правилно, ние сме нещо като предимствата на двата данни структури, които вече сте видели, масиви и свързани списъци. Въвежда се да започнете да склонни към тета 1. Theta ние наистина не са обсъдени, но тета е само средния случай, какво всъщност ще се случи. Не винаги започваш да имат най-лошия сценарий, и не винаги ще има най-добрия случай, така че това, което е Средната сценарий? 

Ами средно вмъкване в хеш таблица може да започне да се доближи до константно време. И заличаване може да получите близо до константно време. И за справка може да получите близо до константно време. That's-- ние не разполагаме с данни структура, все още, че може да направи това, и така това вече звучи като доста голямо нещо. Ние сме наистина смекчило недостатъците на всеки по своя собствена. 

За да получите този спектакъл ъпгрейд пак, ние трябва да преосмислим как ние добавяме данни в структурата. Конкретно искаме Самата данни, за да ни каже където трябва да отидете в структурата. И ако ние след това трябва да се види дали това е в структурата, ако ние трябва да го намерите, ние искаме да разгледаме данните отново и да бъде в състояние ефективно, въз основа на данните, на случаен принцип достъп до него. Само чрез разглеждане на данните трябва да имаме представа къде точно сме Ще го намерите в хеш таблица. 

Сега Недостатъкът на хеш таблица е, че те са наистина доста зле при поръчване или сортиране на данни. И всъщност, ако започнете да ги използвате, за да поръчате или сортиране данни губи всички на предимства ви предварително имаше по отношение на вмъкване и изтриване. Времето става по-близо до тета N, и ние сме основно регресира в свързан списък. И така, ние искаме само да използват хеш маси, ако ние не се грижи за дали данните се сортират. За контекста, в който вие ще ги използвате в CS50 най-вероятно не ме интересува че данните са подредени. 

Така че хеш таблица е комбинация на две отделни парчета с които сме запознати. Първият е функция, която което обикновено наричаме хеш функция. И това хеш функция ще върне някои неотрицателно цяло число, което ние обикновено наричаме хеш-код, OK? Втората част е масив, което е с възможност за съхраняване на данни от тип WE искате да поставите в структурата на данните. Ние ще държи на разстояние за по свързан списък елемент за сега и просто започнете с основите на една хеш таблица, за да получите главата си около него, и тогава ще може взриви ума си малко, когато ние комбинирате масиви и линк списъци заедно. 

Основната идея че е вземем някои данни. В момента тече, че данните чрез на разбъркваща функция. И така, данните се обработват и да го изплюе редица, OK? И след това с този номер ние просто се съхраняват данните ние искаме да се съхранява в масив на това място. Така например ние имаме може би този хеш таблица на низове. Той има 10 елементи в нея, така че ние можем да се поберат 10 струни в него. 

Да кажем, че искаме да хеш Джон. Така John като данните, които искате да вмъкнете в този хеш таблица някъде. Къде сме ние го сложите? Ами обикновено с масив досега ние вероятно ще го сложи в масив място 0. Но сега имаме тази нова хеш функция. 

И нека да кажем, че ще свършим John чрез този хеш-функция и това е изплюва 4. Ами това е, когато сме ще искате да поставите Джон. Ние искаме да се сложи John в населено място масив 4, защото ако хеш John again-- нека да кажем, по-късно ние искате да търсите и да видим ако John съществува в този хеш table-- всички ние трябва да направим е да го ползвате през една и съща хеш функция, получи номер 4, и да бъде в състояние да намери John веднага в нашата структура на данните. Това е доста добър. 

Да кажем, че ние сега да направите това отново, искаме да хеш Paul. Искаме да добавим Paul в този хеш-таблица. Да кажем, че този път ще свършим Paul чрез хеш функция, на хеш-код, който се генерира е 6. Е, сега можем да сложим Paul в мястото на масива 6. И ако трябва да погледнем нагоре дали Павел е в този хеш таблица, всичко, което трябва да направите, е да стартирате Paul чрез функцията за сегментиране отново и ние ще получим 6 отново. 

И тогава ние просто погледнете в населено място масив 6. Дали Павел там? Ако е така, той е в хеш таблица. Дали Павел не съществува? Той не е в хеш таблица. Това е доста ясен. 

Сега, как да се определи хеш функция? Ами там е наистина няма ограничение за брой възможни хеш функции. В действителност има няколко наистина, наистина добри в интернет. Има редица наистина, наистина лоши в интернет. То също е доста лесно да напише една лоша. 

Така че това, което прави един добър хеш функция, нали? Ами добра хеш функция трябва използвате само се хеширани данните, и всички данни, които се сегментира. Така че ние не искаме да използваме anything-- ние не ще приеме нищо друго, различно от данните. И ние искаме да използваме всички данни. Ние не искаме да се използва само едно парче от него, искаме да използваме всички от него. Функция A хеш следва също така да бъде детерминирана. Какво означава това? Ами това означава, че всеки път, когато мине точно същото парче от данни в хеш функция ние винаги получите същия хеш-код навън. Ако минавам John в хеш функция изляза 4. Аз би трябвало да може да се направи, че 10 000 пъти и аз винаги ще получите 4. Така че няма случайни числа ефективно могат да участват в нашата хеш tables-- в нашите хеш функции. 

Функция A хеш следва също равномерно разпространение на данни. Ако всеки път, когато стартирате данни чрез хеш функция можете да получите на хеш-код 0, че вероятно не е толкова голяма, нали? Може би искате да голяма диапазон от хеш кодове. Също така нещата могат да се разпространяват от цялата маса. И също така, че би било чудесно, ако наистина подобни данни, като Джон и Джонатан, може би са били разпределени да се претегля различни места в хеш таблица. Това би било хубаво предимство. 

Ето един пример за хеш функция. Аз написах това по-рано. Това не е особено добра хеш функция по причини, които не го правят наистина понесе навлиза в момента. Но виждаш ли какво става тук? Тя изглежда като ние сме за обявяване на променлива нарича сума и определя равен на 0. И тогава очевидно аз правя нещо докато strstr [J] не е равно да обратно наклонена черта 0. Какво правя там? 

Това е в общи линии просто още начин на изпълнение [? strl?] и откриване, когато сте достигнал края на низа. Така че аз не трябва да всъщност изчисли дължината на низа, Аз съм просто се използва, когато се удари наклонена черта 0 характер Знам Аз бях стигнал края на низа. И тогава аз ще се запази итерации през тази струна, добавяне strstr [к], за да обобщим, а след това в края на деня ще се върне сума мод HASH_MAX. 

По принцип всичко това хеш функция се прави е добавяне всички стойности на ASCII ми низ и след това е връщане на някои хеш-код Modded от HASH_MAX. Това е може би размера на моя масив, нали? Аз не искам да бъдат намалени хеш кодове, ако ми масив е с размер 10, Аз не искам да бъдат намалени освобождава кодове хеш 11, 12, 13, не мога да постави нещата в тези места на масива, че би било незаконно. Бих страдат вина сегментация. 

Сега тук е още един бърз настрана. Като цяло най-вероятно няма да искам да пиша собствени хеш функции. Всъщност, това е малко изкуство, а не наука. А има и много, които отиват в тях. В интернет, както казах, е пълна наистина добри хеш функции, и вие трябва да използват интернет, за да намерите хеш функции, защото това е наистина просто вид ненужна загуба на време, за да създадете свой собствен. 

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

Компютърни науки общност е Определено расте, и наистина стойности с отворен код, и това е наистина важно да се цитират източниците си, така че хората може да получите признание за работата, която те са прави в полза на общността. Така че винаги да бъде sure-- а не само за хеш функции, но по принцип, когато използвате кода от външен източник, винаги се цитират източника. Дайте кредит на лицето, което е направил част от работата, така че не е нужно да. 

OK така че нека да преразгледа този хеш-таблица за секунда. Това е мястото, където ние напуснахме на разстояние, след като сме вмъква Джон и Пол в този хеш-таблица. Виждате ли проблем тук? Може да видите две. Но по-специално, което правите виж този вероятен проблем? 

Какво става, ако хеш Ringo, и то Оказва се, че след преработка че данните през разбъркващата функция Ringo също генерира хеш-код 6. Аз вече имам данни hashcode-- местоположение масив 6. Така че това е най-вероятно ще бъде малко по- на проблем за мен сега, нали? 

Ние наричаме това сблъсък. И сблъскването се случва, когато двама парчета от данни преминават през същата хеш функция получава същото хеш-код. Предполага се, че ние все още искате да получите и двете парчета от данни в хеш таблица, в противен случай ние няма да се работи Ringo произволно чрез хеш функция. Ние вероятно искате да получите Ринго в тази гама. 

Как да го направя пак, ако той и Павел двете добив хеш-код 6? Ние не искаме да презапишете Paul, искаме Павел да бъде там също. Така че ние трябва да се намери начин да се измъкне елементи в хеш таблица, която запазила нашата бърза вмъкване и бърз поглед нагоре. И един от начините да се справим с него е да се направя нещо, наречено линейно сондиране. 

Използвайки този метод, ако имаме сблъсък, добре, какво ще правим? Ами ние не можем да го сложи в населено място масив 6, или каквото и хеш-код се генерира, нека да го сложи в хеш-код плюс 1. И ако това е пълна нека да го сложи в хеш-код, плюс 2. Ползата от това същество, ако той е не точно там, където смятаме, че е той, и ние трябва да започне да търси, може би не е нужно да отидете твърде далеч. Може би не е нужно да търсите всички наш елементи на хеш таблица. Може би ние трябва да търсите Няколко от тях. 

И така, ние сме все още с тенденция към че средната случай е близък до 1 срещу в близост до п, така че може би, че ще работим. Така че нека да видим как това може да работи в реалност. И нека да видим дали можем да се открият може би проблемът, че може да се случи тук. 

Да кажем, че хеш Барт. Така че сега отиваме да тече нов комплект на низове чрез хеш функция, и бягаме Bart чрез хеш функция, получаваме хеш-код 6. Ние да погледнем, виждаме, е 6 празна, така че можем да сложим Bart там. 

Сега ние хеш Лиза и че също генерира хеш-код 6. Е, сега, че ние сме с помощта на този метод ние започне в 6 линейни сондиране, ние виждаме, че 6 е пълна. Ние не можем да сложи Lisa в 6. Е, къде да отидем? Нека да отидем до 7. 7 е празна, така че работи. Така че нека да поставим Lisa там. 

Сега ние хеш Омир и получаваме 7. OK добре знаем, че 7 е пълен сега, така че не можем да сложи Homer там. Така че нека да отидем до 8. Налична ли е 8? Да, и 8 в близост до 7, така че ако ние трябва да започне да търси сме не ще трябва да отидете твърде далеч. И така, нека да поставим Омир в 8. 

Сега ние хеш Маги и връща 3, слава богу ние сме в състояние да съм сложил Маги там. Ние не трябва да направите всеки сортиране на сондиране за това. Сега ние хеш Мардж, и Мардж се завръща и 6. 

Ами 6 е пълна, 7 е пълен, 8 е пълна, 9, всичко е наред слава богу, 9 е празна. Мога да сложа Мардж в 9. Вече можем да видим, че ние започваме за да получите този проблем, където сега сме като се започне да се простират неща вид от далеч от техните хеш кодове. И това тета на 1, че средният случай, че са константно време, започва да става малко по-MORE- като се започне да се погрижи малко повече към тета п. Ние започваме да губят, че възползвате от хеш таблици. 

Този проблем, че ние просто видях е нещо, наречено клъстери. И това, което е наистина лошо за групиране е, че след като сега има два елемента, които са страна по натам го прави още по-вероятно, имате удвои шанс, че започваш да имаме още едно сблъскване с тази клъстер, и клъстера ще нарасне с една. И ще продължи да се увеличава и отглеждане Вашата вероятност да има сблъсък. И в крайна сметка това е също толкова лошо като не сортиране на данните на всички. 

Другият проблем е, че ние Все още, и досега до този момент, Току-що бил нещо като разбиране какво е хеш таблица, ние все още само има място за 10 струни. Ако искаме да продължим да хеш гражданите на Springfield, можем да получим само 10 от тях там. И ако ние се опитваме и добавете 11 или 12, ние нямаме място, където да ги пуснат. Бихме могли просто да се върти в кръгове се опитват да намерят празно място, и ние може би се заби в един безкраен цикъл. 

Така че този вид на поддава на идеята на нещо, наречено верижното. И това е мястото, където отиваме, за да донесе свързани списъци обратно в картината. Какво става, ако вместо просто съхраняване самите данни в масива, всеки елемент на масива могат задръжте няколко парчета на данни? Добре, че не е логично, нали? Ние знаем, че само може масив hold-- всеки елемент от масив може да има само едно парче на данните от този тип данни. 

Но какво, ако този тип данни е свързан списък, нали? И какво, ако всеки елемент на масива е указател към главата на свързан списък? И тогава бихме могли да изградим тези свързани списъци и им растат произволно, защото свързани списъци позволяват нас, за да растат и да се свие много повече гъвкаво от масив прави. И какво, ако ние сега се използва, ние използваме това, нали? Започваме да растат тези вериги от тези места масив. 

Сега можем да се поберат един безкраен количество данни, или не безкрайна, произволно количество от данни, в нашата хеш-таблица без изобщо да работи в проблема на сблъсък. Ние сме също така елиминира групиране по този начин. И добре знаем, че когато ние вмъкнете в свързан списък, ако си спомняте от нашия видео на свързани списъци, поединично свързани списъци и двойно свързани списъци, това е една постоянна работа време. Ние просто добавяне на фронта. 

И за поглед нагоре, както знаем, че гледам в свързан списък може да е проблем, нали? Ние трябва да търсим в то от началото до края. Няма по случаен принцип достъп в свързан списък. Но ако вместо да се налага една свързана списък за справка, където ще бъде O на п, сега имаме 10 свързани списъци, или 1000 свързани списъци, сега това е О п делено на 10, О или N, разделена на 1,000. 

И докато ние говорим теоретично за сложност се абстрахираме от константи, в реалния свят тези неща действително имат значение, нали? Ние всъщност ще забележите че това се случва да тече 10 пъти по-бързо, или 1000 пъти по-бързо, защото ние сме разпространение на една дълга верига през 1000-малки вериги. И така всеки път, когато трябва да се търси през една от тези вериги, които можем игнорират 999 вериги ние не им пука за това и просто търсене, че един. 

Което е средно до да бъде 1000 пъти по-кратък. И така, ние сме все още нещо с тенденция към тази средна случай да бъдеш постоянно време, но само защото ние сме деблокирането дели на някакво огромно постоянен фактор. Нека да видим как това би могло всъщност изглеждат все пак. Така че това е хеш таблицата имахме преди да сме обявен за хеш таблица, която е с възможност за съхраняване 10 струни. Ние няма да го направя повече. Вече знаем ограничения на този метод. Сега нашата хеш-таблица ще бъде масив от 10 възли, показалки на ръководителите на свързани списъци. 

И точно сега това е нищожна. Всеки един от тези 10 указатели е нищожна. Няма нищо в нашата хеш таблица в момента. 

Сега нека да започнем да се въведе някакъв неща в този хеш-таблица. И нека да видим как този метод е Ще ни се възползват малко. Нека сега хеш Джоуи. Ние ще ще се проведе на низа Joey чрез хеш функция и да се върнем 6. Е, какво ще правим сега? 

Е, сега работя с свързани списъци, ние не работим с масиви. И когато ние работим със свързани списъци ние знам, че трябва да започне динамично разпределението на място и изграждане на вериги. Това е нещо като how-- това са сърцевината елементи за изграждане на свързан списък. Така че нека да е динамично разпредели пространство за Джоуи, и след това нека да го добавите към веригата. 

Така че сега вижте какво сме направили. Когато се разискват Joey ние имаме хеш-код 6. Сега показалеца на място при масив 6 сочи към главата на свързан списък, и в момента това е единственото елемент от свързан списък. И в този възел свързан списък е Джоуи. 

Така че, ако трябва да погледнем нагоре Joey по-късно, ние просто хеш Джоуи отново, получаваме 6 отново, защото ни хеш функция е детерминирана. И тогава ние започваме начело на свързания списък посочи до по местоположение масив 6, и ние можем да превъртите през които се опитват да намерят Джоуи. И ако ние градим хеш таблица ефективно, и нашата хеш функция ефективно да разпространява информация и, средно всеки от тези, свързани списъци на всяко населено място масив ще бъде 1/10 от размера на ако просто го имаше като един огромен свързан списък с всичко в него. 

Ако разпространявате този огромен свързана списък през 10 свързани списъци всеки списък ще бъде 1/10 от размера. И по този начин 10 пъти по-бързо да се търси чрез. Така че нека да направим това отново. Нека сега хеш Ross. 

И нека да кажем, Ross, когато го правим, че кода за сегментиране се върнем е 2. Е, сега сме динамично разпредели нов възел, ние поставяме Ross в този възел, и ние казваме сега местоположение масив 2, вместо да сочи към нула, сочи към главата на свързан списък, чийто единствен възел е Ross. И ние можем да направим това още един път, ние може хеш Рейчъл и да получите хеш-код 4. изчистване на нов възел, постави Rachel в възела, и да кажа на местоположение масив 4 вече сочи към главата на свързан списък, чието само елемент се случва да бъде Рейчъл. 

ОК, но какво ще стане, ако имаме сблъсък? Нека да видим как се справяме с колизии използване на отделни метода на верижното. Нека хеш Фийби. Качваме се на хеш-код 6. В предишния ни пример бяхме просто съхраняване на струните в масива. Това беше проблем. 

Ние не искаме да смажат Джоуи, и вече сме Вижда се, че можем да вземем някои клъстери проблеми, ако ние се опитваме и стъпка през и сонда. Но какво, ако ние просто вид лечение на това по същия начин, нали? Това е точно като добавяне на елемент до началника на свързан списък. Нека просто изчистване пространство за Фийби. 

Ще кажа следващите показалеца точки на Фийби до стария главата на свързан списък, и след това просто 6 пункта към Новият шеф на свързан списък. А сега погледнете, ние променихме Фийби инча Сега можем да се съхранява две елементи с хеш-код 6, и ние нямаме никакви проблеми. 

Това е почти всичко, има да верижното. И определено е верижното метода, който е ще бъдат най-ефективни за вас, ако Вие съхраняване на данни в таблица на хашиш. Но тази комбинация от масиви и свързани списъци заедно, за да образуват хеш таблица наистина значително подобрява способността Ви за съхранение на големи обеми от данни, и много бързо и ефективно търсене чрез тези данни. 

Все още има още една структура на данните, там че дори може да бъде малко по- по-добре от гледна точка на гарантиране че нашата вмъкване, изтриване, и гледат нагоре времена са дори по-бързо. И ние ще видим, че по време на видео на опит. Аз съм Дъг Лойд, това е CS50.