[Гуляе музыка] Даг Lloyd: У цяперашні час вы ведаю шмат пра масівах, і вы ведаеце, шмат аб звязаных спісаў. І мы абмяркуем плюсы і мінусы, мы абмяркоўвалі, што звязана спісы можа атрымаць больш і менш, але яны займаюць больш памер. Масівы з'яўляюцца значна больш простая ў выкарыстоўваць, але яны абмежавальны столькі як мы павінны ўсталяваць памер масіў у самым пачатку і тады мы затрымаліся з ім. 

Але гэта, мы ў значнай ступені вычарпаныя ўсе нашы тэмы аб звязаных спісаў і масіваў. Ці ў нас? Можа быць, мы можам зрабіць што-то яшчэ больш творчым. І што-то дае ў пазыку Ідэя хэш-табліцы. 

Такім чынам, у хэш-табліцы, мы збіраемся, каб паспрабаваць аб'яднаць масіў з звязанага спісу. Мы збіраемся скарыстацца перавагамі масіва, як адвольнага доступу, будучы ў стане проста ісці да масіву элемент 4 ці элемент масіва 8 без перабору ўсёй. Гэта даволі хутка, ці не так? 

Але мы таксама хочам, каб нашы дадзеныя Структура мець магчымасць расці і скарачацца. Нам не трэба, мы не хачу быць абмежавана. І мы хочам, каб мець магчымасць дадаваць і выдаляць рэчы вельмі лёгка, што, калі вы памятаеце, з'яўляецца вельмі складаным з масівам. І мы можам назваць гэта новая рэч хэш-табліцу. 

І калі ўсё зроблена правільна, мы накшталт прыняцця перавагі абодвух дадзеных структуры вы ўжо бачылі, Масівы і звязаныя спісы. Устаўка можа пачаць маюць тэндэнцыю да тэта 1. Тэта мы не абмяркоўвалі, але тэта толькі ў сярэднім выпадку, што на самой справе адбудзецца. Вы не заўсёды будзе ёсць найгоршы сцэнар, і вы не заўсёды будзеце мець у лепшым выпадку, так што сярэдняя сцэнар? 

Ну ў сярэднім ўстаўкі у хэш-табліцы можа пачаць набліжацца да сталай часу. І выдаленне можаце атрымаць блізка да сталай часу. І пошук можна атрымаць блізка да сталай часу. That's-- мы не маем дадзеных Структура яшчэ, што можна зрабіць, што, і такім чынам гэта ўжо гучыць як даволі вялікая справа. Мы сапраўды змякчыла недахопы кожнага на ўласную. 

Каб атрымаць гэтую працу абнавіць, хоць, мы трэба пераасэнсаваць тое, як мы дадаем Дадзеныя ў структуру. У прыватнасці, мы хочам, каб Самі дадзеныя, каб паведаміць нам дзе яна павінна ісці ў структуры. І калі мы тады павінны бачыць, калі ён знаходзіцца ў структура, калі нам трэба, каб знайсці яго, мы хочам, каб паглядзець на дадзеныя зноў і быць у стане эфектыўна, з выкарыстаннем дадзеных, выпадковым чынам доступ да яго. Проста гледзячы на Дадзеныя, якія мы павінны мець ідэя, дзе менавіта мы збіраюся знайсці яго ў хэш-табліцы. 

Цяпер ніжняя бок хэш Табліца з'яўляецца тое, што яны на самой справе даволі дрэнна замовы або сартавання дадзеных. І на самай справе, калі вы пачынаеце выкарыстоўваць іх на заказ або роду дадзеныя, якія вы страціце ўсе з Перавагі раней была па ўстаўкі і выдаленні. Час становіцца бліжэй да тэта п, і мы ў асноўным рэгрэс у звязаным спісе. І таму мы хочам выкарыстоўваць толькі хэш Табліцы, калі мы не клапоцімся пра Ці сартуюцца дадзеныя. Для ўмоў, у якіх Вы будзеце выкарыстоўваць іх у CS50 Вы, верагодна, не хвалюе, што дадзеныя будуць адсартаваныя. 

Такім чынам, хэш-табліца ўяўляе сабой спалучэнне з двух асобных частак з якой мы знаёмыя. Па-першае, гэта функцыя, якая мы звычайна называем Хэш-функцыі. І, што хэш-функцыя будзе вярнуцца некаторы неадмоўнае цэлы лік, што мы звычайна называем хэш-код, ОК? Другая частка ўяўляе сабой масіў, які з'яўляецца здольны захоўваць дадзеныя тыпу мы хоча размясціць у структуры дадзеных. Мы ўтрымаць на звязаны элемент спісу зараз і проста пачаць з асновамі з хэш-табліцы, каб атрымаць сваю галаву вакол яго, і тады мы будзем, можа быць, падарваць Ваш розум трохі, калі мы аб'яднаць масівы і спісы спасылак разам. 

Асноўная ідэя, хоць гэта мы бярэм некаторыя дадзеныя. Мы бяжым, што дадзеныя праз Хэш-функцыя. І так як дадзеныя апрацаваны і ён выплёўвае нумар, ОК? А потым з гэтым нумарам мы проста захоўваць дадзеныя мы хочам, каб захаваць у Масіў у гэтым месцы. Так, напрыклад, у нас ёсць, можа быць, гэта хэш-табліцы радкоў. Ён атрымаў 10 элементаў у ім, таму мы можам адпавядаць 10 радкоў у ім. 

Скажам, мы хочам, каб праясніць Іаана. Так як Ян дадзеных мы хочам ўставіць у гэтым хэш-табліцы недзе. Дзе мы пакласці яго? Ну, як правіла, з Масіў гэтага часу мы, верагодна, будзе пакласці яго ў масіў размяшчэння 0. Але цяпер у нас ёсць гэты новы хэш-функцыі. 

І давайце скажам, што мы бяжым ад Іаана праз гэты хэш-функцыі і гэта выплёўвае 4. Ну вось, дзе мы захоча паставіць Іаана. Мы хочам, каб пакласці Іаана ў месцы масіва 4, таму што калі мы хэшавання Іаана again-- скажам пазней мы хочаце, каб пошук і паглядзець, калі Джон існуе ў гэтым хэш table-- усё, што трэба зрабіць, выконваецца яго праз той жа хэш Функцыя, атрымаць нумар 4 з, і быць у стане знайсці Джона неадкладна ў нашай структуры дадзеных. Гэта вельмі добра. 

Скажам, зараз мы гэта зрабіць зноў жа, мы хочам, каб праясніць Паўла. Мы хочам, каб дадаць Паўла у гэтым хэш-табліцы. Давайце выкажам здагадку, што на гэты раз мы сутыкаемся Павел праз хэш-функцыі, хэш, які генеруецца 6. Ну мы можам паставіць Паўла ў месцы масіва 6. І калі мы павінны глядзець на Ці Падлогу ў гэтым хэш-табліцы, усё, што трэба зрабіць, гэта запусціць Пол праз хэш-функцыі зноў і мы збіраемся, каб атрымаць 6 зноў. 

А потым мы проста паглядзець на месцы масіва 6. Павел трапіць? Калі гэта так, ён у хэш-табліцы. Павел ці не так? Ён не ў хэш-табліцы. Гэта даволі проста. 

Цяпер, як вы вызначаеце хэш-функцыі? Ну там на самой справе няма абмежаванняў на лік магчымых хэш-функцый. На самай справе ёсць шэраг вельмі, сапраўды добрыя ў Інтэрнэце. Там гэта колькасць на самай справе, сапраўды дрэнныя ў Інтэрнэце. Гэта таксама даволі лёгка напісаць дрэнны. 

Так што ж робіць добрую Хэш функцыя, праўда? Ну добра хэш-функцыя павінна выкарыстоўваць толькі будучы хэшируется дадзеныя, і ўсе дадзеных, хэшированного. Такім чынам, мы не хочам, каб выкарыстоўваць anything-- мы нічога не ўключаць то ў іншым месцы, чым дадзеныя. І мы хочам, каб выкарыстаць усе дадзеныя. Мы не хочам, каб проста выкарыстоўваць кавалак гэта, мы хочам, каб выкарыстоўваць усе гэта. Хэш-функцыя павінна Таксама быць дэтэрмінаваных. Што гэта азначае? Ну гэта азначае, што кожны раз, калі мы прайсці той жа кавалак дадзеных у хэш-функцыі мы заўсёды атрымаць той жа хэш-код з. Калі я праходжу Джона ў Хэш функцыя я выходжу 4. Я павінен быць у стане зрабіць гэта 10000 раз, і я заўсёды буду атрымаць 4. Эфектыўна, так не выпадковыя ліку могуць быць ўцягнутыя ў нашай хэш tables-- у нашых хэш-функцый. 

Хэш-функцыя павінна таксама раўнамерна размяркоўваць дадзеныя. Калі кожны раз, калі вы запусціце дадзеныя праз Хэш функцыя, якую вы атрымаеце хэш 0, гэта, напэўна, не так выдатна, праўда? Вы, напэўна, хочаце, каб большая дыяпазон хэш-кодаў. Таксама рэчы можна распаўсюдзіць з усёй табліцы. А таксама было б выдатна, калі б на самай справе аналагічныя дадзеныя, такія як Джон і Джонатан, можа быць, былі распаўсюджаныя ўзважыць розных месцах у хэш-табліцы. Гэта было б добрае перавага. 

Вось прыклад з хэш-функцыі. Я напісаў гэта адно ўверх раней. Гэта не асабліва добрая функцыя хэшавання па прычынах, якія сапраўды ня несці ўдаючыся ў прама цяпер. Але вы бачыце, што тут адбываецца? Падобна на тое, мы аб'яўленні зменнай называецца сума і усталяваўшы яго роўным 0. А потым, мабыць, я раблю нешта так доўга, як strstr [J] ня роўны у зваротны слэш 0. Што я там рабіў? 

Гэта ў асноўным проста яшчэ адзін спосаб рэалізацыі [? strl?] і выяўлення, калі вы дасягнулі канца радка. Так што я не ёсць на самой справе вылічыць даўжыню радка, Я толькі з дапамогай, калі я трапіў у Зваротная касая рыса характару 0 Я ведаю, Я дасягнуў канца радка. А потым я збіраюся трымаць пераборы гэтага радка, дадаўшы strstr [J], каб падвесці, а затым на Канец дня збіраецца вярнуцца сумы мод HASH_MAX. 

У асноўным усё гэта хэш функцыя робіць гэта даданне да усе значэння ASCII ў мой радок, а затым гэта вяртанне некаторы хэш Каментары ад HASH_MAX. Гэта, верагодна, памер маёй масіва, праўда? Я не хачу, каб атрымліваць хэш коды, калі мой масіў мае памер 10, Я не хачу, каб атрымліваць з хэш-коды 11, 12, 13, я не магу пакласці рэчы ў гэтыя месцы масіва, што было б незаконным. Я пакутую памылку сегментацыі. 

Цяпер вось яшчэ адзін хуткі ў бок. Як правіла, вы, верагодна, не збіраецца хачу напісаць свае ўласныя хэш-функцыі. Гэта на самай справе трохі мастацтва, а не навука. І ёсць шмат, што ідзе ў іх. Інтэрнэт, як я ўжо сказаў, гэта поўны сапраўды добрых хэш-функцыі, і вы павінны выкарыстоўваць Інтэрнэт для знайсці хэш-функцый, таму што гэта сапраўды толькі выгляд непатрэбным пустая трата часу, каб стварыць свой уласны. 

Вы можаце напісаць простыя з іх для мэт тэставання. Але калі вы сапраўды збіраецеся пачаць хэшавання дадзеных і захоўваць яго у хэш-табліцу вы знаходзіцеся верагодна, хочаце выкарыстоўваць некаторыя функцыі, які быў створаны для вас, што існуе ў Інтэрнэце. Калі вы толькі пераканайцеся, што прывесці свае крыніцы. Там няма прычын, каб плагіятам тут нічога. 

Інфарматыка супольнасць безумоўна, расце, і на самай справе значэння з адкрытым зыходным кодам, і гэта сапраўды важна прывесці свае крыніцы, так што людзі можа атрымаць атрыбуцыю праца, што яны робіць на карысць супольнасці. Так заўсёды быць sure-- і не толькі для хэш функцыі, але, як правіла, калі вам выкарыстоўваць код з вонкавай крыніцы, заўсёды прыводжу сваю крыніцу. Дайце крэдыт на чалавека, які зрабіў некаторыя працы, так што вы не павінны. 

ТАКІМ ЧЫНАМ, давайце вярнуцца да гэтага Хэш-табліца на секунду. Гэта дзе мы пакінулі ад пасля таго як мы устаўленыя Джон і Пол ў гэтым хэш-табліцы. Вы бачыце тут праблему? Вы можаце ўбачыць два. Але ў прыватнасці, зрабіць вас паглядзець магчымыя праблемы? 

Што рабіць, калі я хэш Рынга, і гэта Атрымліваецца, што пасля апрацоўкі што дадзеныя праз хэш-функцыі Рынга сфармавала хэш 6. Я ўжо атрымаў дадзеныя ў hashcode-- размяшчэнне масіва 6. Так што гэта, верагодна, будзе крыху праблемы для мяне цяпер, ці не так? 

Мы называем гэта сутыкненне. І сутыкненне адбываецца, калі два фрагменты дадзеных прапускалі праз той жа хэш Функцыя даюць аднолькавы хэш-код. Меркавана мы ўсё яшчэ хочам, каб і фрагменты дадзеных у хэш-табліцы, у адваротным выпадку мы б не працуе Рынга адвольна праз хэш-функцыі. Мы, верагодна, хочаце атрымаць Рынга ў гэтым масіве. 

Як мы гэта робім, хоць, калі ён і Павел і выхад хэш 6? Мы не хочам, каб перазапісаць Паўла, мы хочам, каб Пол там таксама. Такім чынам, мы павінны знайсці спосаб, каб атрымаць элементы ў хэш-табліцы, што усё яшчэ захоўвае наша хуткае устаўка і хуткі погляд на. І адзін са спосабаў барацьбы з ім з'яўляецца зрабіць што-то пад назвай лінейны зандзіравання. 

Выкарыстоўваючы гэты метад, калі ў нас ёсць Сутыкненне, ну, што ж нам рабіць? Ну, мы не можам паставіць яго ў месцы масіва 6, ці нешта хэш-код быў створаны, давайце яго на HashCode плюс 1. І калі гэта поўны давайце пакласці яго ў HashCode плюс 2. Перавага гэтага істоты, калі ён не дакладна, дзе мы думаем, што ён, і ў нас ёсць, каб пачаць пошук, можа быць, мы не павінны ісці занадта далёка. Можа быць, мы не павінны шукаць усе п элементаў хэш-табліцы. Можа быць, мы павінны шукаць пару з іх. 

І таму мы ўсё яшчэ тэндэнцыю да што сярэдняя справу быць блізка да 1 супраць блізка да п, так што, можа быць, буду працаваць. Такім чынам, давайце паглядзім, як гэта можа працаваць у рэальнасці. І давайце паглядзім, калі магчыма, мы можам выявіць праблема, што можа адбыцца тут. 

Скажам, мы хэш Барта. Так што цяпер мы збіраемся запусціць новы набор радкоў праз хэш-функцыі, і мы бяжым Барта праз хэш Функцыя, мы атрымліваем хэш 6. Мы глядзім, мы бачым 6 пусты, так што мы можам паставіць Барта ёсць. 

Цяпер мы хэш Лізу, і што таксама генеруе хэш 6. Ну цяпер, калі мы з дапамогай гэтага лінейны метад зандзіравання мы пачынаем у 6, мы бачым, што 6 запоўненая. Мы не можам Лізу ў 6. Дык куды мы ідзем? Давайце 7. 7 пуста, так што працуе. Так давайце Лізе там. 

Цяпер мы хэш Гамера, і мы атрымліваем 7. ОК добра мы ведаем, што 7 поўна Цяпер, так мы не можам паставіць Гамера ёсць. Такім чынам, давайце па 8. Ёсць 8 даступныя? Так, і блізка да 7, 8, так, калі у нас ёсць, каб пачаць пошук мы не прыйдзецца заходзіць занадта далёка. І так давайце Гамера на 8. 

Цяпер мы хэш Мэгі і вяртае 3, дзякуй Богу мы можам проста паставіць Мэгі ёсць. Мы не павінны рабіць нічога Сартаваць зандзіравання для гэтага. Цяпер мы хэш Мардж, і Мардж таксама вяртае 6. 

Ну 6 поўны, 7 поўны, 8 поўны, 9, усё ў парадку, дзякуй Богу, 9 пусты. Я магу паставіць Мардж ў 9. Ужо цяпер мы бачым, што мы пачынаем каб мець гэтую праблему, дзе цяпер мы пачынаючы расцягнуць рэчы накшталт з удалечыні ад сваіх хэш-кодаў. І, што тэта 1, што сярэдняя Справа ў тым, пастаянная часу, пачынае атрымліваць трохі more-- пачынаюць, як правіла, крыху больш, да тэта п. Мы пачынаем губляць, што Перавага хэш-табліцы. 

Гэта праблема, якую мы толькі што бачылі гэта тое, што называецца кластарызацыі. І тое, што сапраўды дрэнна кластарызацыя, што як толькі вы ў цяперашні час ёсць два элемента, якія бок ад бок ён робіць гэта нават хутчэй, ў вас ёсць двайны шанец, што вы збіраецеся каб яшчэ сутыкнення з гэтага кластара, і кластар будзе расці па адным. І вы будзеце трымаць расце і расце ваш верагоднасць наяўнасці сутыкнення. І ў рэшце рэшт гэта так жа дрэнна, а не сартавання дадзеных наогул. 

Іншая праблема, хоць гэта мы Тым не менш, і да гэтага часу да гэтага моманту, Мы толькі што-то разумеючы, што хэш-табліца з'яўляецца, мы па-ранейшаму ёсць толькі нумар для 10 радкоў. Калі мы хочам працягваць хэш грамадзяне Спрынгфілда, мы можам атрымаць толькі 10 з іх там. І калі мы будзем спрабаваць дадаць 11 або 12, мы не ёсць месца, каб змясціць іх. Мы маглі б проста быць спінінг вакол у кругі, спрабуючы знайсці пустое месца, і мы, магчыма, затрымаліся ў бясконцым цыкле. 

Так што гэта свайго роду дае ў пазыку ідэі пра нешта называецца ланцужкі. І гэта, дзе мы збіраемся, каб прынесці звязаныя спісы вярнуцца ў карціну. Што рабіць, калі замест таго, каб захоўваць толькі самі дадзеныя ў масіве, кожны элемент масіва можа правесці некалькі штук дадзеных? Ну, што не мае сэнсу, ці не так? Мы ведаем, што масіў можа толькі hold-- кожны элемент масіва можа мець толькі адзін кавалак дадзеных гэтага тыпу дадзеных. 

Але што, калі гэта тып дадзеных гэта звязаны спіс, ці не так? Так што, калі кожны элемент масіва быў паказальнік на галаву звязанага спісу? І тады мы маглі б пабудаваць гэтыя звязаныя спісы і вырошчваць іх адвольна, таму што звязаныя спісы дазваляюць нам расці і скарачацца нашмат больш гнутка, чым масіў робіць. Так што, калі мы ў цяперашні час выкарыстоўваюць, мы выкарыстоўваць гэта, праўда? Мы пачынаем вырошчваць гэтыя ланцугу З гэтых месцах масіва. 

Цяпер мы можам адпавядаць бясконцае Аб'ём дадзеных, ці не бясконца, адвольную колькасць Дадзеныя, у нашай хэш-табліцы ніколі не працуе ў Праблема сутыкнення. Мы таксама ліквідаваны кластарызацыі, робячы гэта. І добра вядома, што, калі мы ўстаўляем у звязаным спісе, калі вы памятаеце, з нашага відэа на звязаных спісаў, па адным звязаныя спісы і двойчы звязаныя спісы, гэта пастаянная праца час. Мы проста дадаўшы на фронт. 

І паглядзець, добра мы ведаем якія выглядаюць у выглядзе звязанага спісу можа быць праблема, дакладна? Мы павінны шукаць праз гэта ад пачатку да канца. Там няма выпадковых доступ у звязаным спісе. Але калі замест таго, адзін звязаны Спіс, дзе пошук будзе O п, цяпер у нас ёсць 10 сувязныя спісы, або 1000 звязаныя спісы, цяпер гэта Аб п дзеліцца на 10, ці Аб п дзеліцца на 1000. 

І ў той час як мы казалі Тэарэтычна аб складанасці занядбаць канстанты, у рэальным Свет гэтыя рэчы на ​​самай справе мае значэння, дакладна? Мы на самай справе будзе заўважыць што гэта адбываецца для запуску 10 разоў хутчэй, або ў 1000 разоў хутчэй таму што мы распаўсюдзе адзін доўгі ланцуг па 1000 дробных ланцугоў. І так кожны раз, калі мы павінны шукаць праз адзін з гэтых ланцугоў мы можа ігнараваць 999 ланцугоў Мы не клапоцімся о, і проста шукаць той. 

Які ў сярэднім 1000 разоў карацей. І такім чынам, мы па-ранейшаму з'яўляюцца свайго роду тэндэнцыю да гэтай сярэдняй выпадку быць пастаяннае час, але толькі таму, што мы выкарыстоўваючы дзялення нейкага вялізнага пастаяннага множніка. Давайце паглядзім, як гэта можа на самай справе выглядаюць, хоць. Так што гэта было хэш-табліцы мы павінны былі перш, чым мы абвясцілі, што хэш-табліцу быў здольны захоўваць 10 радкоў. Мы не збіраемся гэтага рабіць. Мы ўжо ведаем, Абмежаванні гэтага метаду. Цяпер наша хэш-табліцы будзе масіў з 10 вузлоў, паказальнікі кіраўнікам звязаных спісаў. 

І цяпер гэта нуль. Кожны з гэтых 10 паказальнікаў NULL. Там няма нічога ў нашых хэш-табліцы прама цяпер. 

Зараз давайце пачнем паставіць некаторыя рэчы ў гэтай хэш-табліцы. І давайце паглядзім, як гэты метад пойдзе на карысць нам няшмат. Давайце зараз хэш Джоуі. Мы будзе працаваць радок Джоі праз хэш-функцыя, і мы вяртаемся 6. Ну, што ж нам цяпер рабіць? 

Ну цяпер працуе са звязанымі спісамі, мы не працуем з масівамі. І калі мы працуем са звязанымі спісамі мы ведаю, што мы павінны пачаць дынамічна вылучэнне прасторы і будаўнічыя ланцугоў. Гэта свайго роду how-- тыя ядро элементы пабудовы звязанага спісу. Так давайце дынамічна вылучыць месца для Joey, а затым давайце дадамо яго ў ланцугі. 

Так што цяпер паглядзіце, што мы зрабілі. Калі мы хэш Джоуі мы атрымалі хэш 6. Цяпер паказальнік на месца масіва 6 паказвае на галаву звязанага спісу, і цяпер гэта адзіны элемент звязанага спісу. І вузел у тым, што Звязаны спіс Джоуі. 

Так што, калі мы павінны глядзець на Джоуі пазней, мы проста хэш Джоі зноў, мы атрымліваем 6 разоў, таму што нашы Хэш функцыя з'яўляецца дэтэрмінаванай. І тады мы пачынаем у галаву звязанага спісу адзначыў каб па месцазнаходжанні масіва 6, і мы можам ітэрацыі па, што, спрабуючы знайсці Джоі. І калі мы будуем наш эфектыўна хэш-табліцы, і наша хэш-функцыя эфектыўна распаўсюджваць дадзеныя і, у сярэднім кожны з тых, якія звязаны Спісы ў любым месцы масіва будзе 1/10 памер, калі мы толькі што яго як адзін велізарны Звязаны спіс з усім ў ім. 

Калі мы размяркоўваем, што велізарная звязаны Спіс па 10 звязаных спісаў кожны спіс будзе 1/10 памер. І такім чынам у 10 разоў хутчэй, шукаць. Так давайце зробім гэта зноў. Давайце зараз хэш Рос. 

І, скажам, Рос, калі мы робім што хэш-код вернемся 2. Ну цяпер мы дынамічна вылучаць Новы вузел, мы ставім Рос у гэтым вузле, і мы зараз сказаць размяшчэнне масіва 2, а паказваючы на ​​нуль, паказвае на галаву звязаны спіс, чые толькі вузел Рос. І мы можам зрабіць гэта яшчэ раз, мы можа хэш Рэйчел і атрымаць хэш-код 4. Таноса новы вузел, пакласці ў Рэйчел вузел, і сказаць вочка масіва 4 зараз паказвае на галаве з звязанага спісу, чые Адзіны элемент, здараецца, Рэйчел. 

ОК, але што адбудзецца, калі у нас ёсць сутыкненне? Давайце паглядзім, як мы звяртаемся з сутыкненняў выкарыстоўваючы асобны метад счаплення. Давайце хэш Фібі. Мы атрымліваем хэш 6. У нашым папярэднім прыкладзе мы проста захоўвання радкоў у масіве. Гэта было праблемай. 

Мы не хочам, каб калашмаціць Джоуі, і мы ўжо відаць, што мы можам атрымаць некаторы кластарызацыі праблемы, калі мы паспрабуем і крок праз зонд і. Але што, калі мы проста выгляд ставіцца да гэтага так жа, як, праўда? Гэта проста, як даданне элемента ў галаву звязанага спісу. Давайце проста выдзялення памяці прастору для Фібі. 

Мы скажам, наступныя пункты паказальнік Фібі у старой галаве звязанага спісу, а затым 6 разоў паказвае на Новы кіраўнік звязанага спісу. А цяпер паглядзіце, што мы змянілі Фібі ст. Цяпер мы можам захоўваць два элементы з HashCode 6, і мы не якія-небудзь праблемы. 

Гэта даволі шмат, усё ёсць у ланцужкі. І, безумоўна, ланцужкі метад, які гэта будзе найбольш эфектыўным для вас, калі Вы захоўваеце дадзеныя ў хэш-табліцы. Але гэтая камбінацыя масівы і звязаныя спісы разам, каб сфармаваць хэш-табліцу на самай справе значна паляпшае вашу здольнасць для захоўвання вялікіх аб'ёмаў дадзеных, і вельмі хутка і эфектыўна шукаць праз гэтых дадзеных. 

Там па-ранейшаму яшчэ адзін Структура дадзеных там што, магчыма, нават будзе трохі лепш з пункту гледжання забеспячэння што наша ўстаўка, выдаленне, і Паглядзіце пояс нават хутчэй. І мы ўбачым, што ў відэа на спробаў. Я Дуг Лойд, гэта CS50.