[Шуму].
Перад апусканнем у хэш-табліц, давайце
спачатку разгледзім плюсы і мінусы некаторых
простыя структуры дадзеных, пачынаючы з
масівы.
Нагадаем, што масівы дазваляюць нам захоўваць
элементы аднаго тыпу дадзеных
бесперапынна ў памяці.
Паколькі кожны элемент звязаны з
індэкс, або месца,
у нас ёсць выпадковы доступ да ўсіх
элементы масіва.
Іншымі словамі, мы можам атрымаць доступ да любога элементу
ў адным кроку ад індэксацыі ў
масівам.
Гэта вялікая справа, таму што алгарытмы
як бінарнага пошуку залежаць ад выпадковых
доступу.
Недахопам масіваў з'яўляецца тое, што іх памер
фіксавана.
Паколькі дадзеныя масівы магазін бесперапынна ў
памяці, неабходна ўказаць памер масіва
пры аб'яўленні масіва.
Вы эфектыўна пытаючыся аперацыйнай
Сістэма зарэзерваваць адпаведную колькасць
памяці для элементаў масіва.
Там няма ніякай гарантыі, што больш памяці,
побач з вашага масіва, будуць даступныя
для наступнага выкарыстання.
Так масівы не могуць лёгка расці.
Нагадаем, што мы таксама даведаліся пра звязаныя
спісы, якія могуць расці, таму што іх
элементы не з'яўляюцца сумежнымі ў памяці.
Кожны вузел у звязаным спісе ўтрымлівае
элемент, які мы хочам захоўваць, а таксама
паказальнік на наступнага элемента ў
спіс.
На жаль, цана, якую мы заплацілі за
дынамічны памер адвольны доступ да
элементы.
Для таго, каб атрымаць доступ пэўны элемент,
неабходна прайсці па ўсім
спіс, пакуль шуканы элемент не з'яўляецца
дасягнуты.
Так што, калі я шукаю колькасці 9, я б
прытрымлівайцеся паказальнікі ад вузла да вузла,
праверкі, ці з'яўляецца значэнне кожнага вузла
роўна 9.
Такім чынам, у горшым выпадку, паглядзець гэта
O (N), якое далёка не эфектыўнымі.
Ці можам мы зрабіць лепш, чым O (N) у той жа час
дазваляе наша структура дадзеных расці на працягу
раз?
Хэш-табліцы прапанаваць рашэнне.
Выкарыстоўваюцца Хэш-табліцы, калі хуткі
ўстаўкі, выдалення і пошуку з
элементы з'яўляецца прыярытэтным.
У тэорыі, устаўка, выдаленне і пошук
можа нават быць дасягнута ў пастаяннай
Час.
Такім чынам, што ж уяўляе сабой хэш-табліцу ў любым выпадку?
Хэш-табліца проста масіў у спалучэнні
з функцыяй, якую мы будзем называць хэш
функцыя.
Хэш-функцыя прымае частка дадзеных
у якасці ўваходных дадзеных, мы будзем называць гэта ключавы, і
выводзіць цэлы лік, звычайна званы
ў якасці хэш-значэння.
Значэнне хэш-карты наш ключ да
вызначаны індэкс ў хэш-табліцы.
Вы б спачатку выкарыстоўваць хэш-функцыю для
вызначыць, дзе ў хэш-табліцы, каб
захоўваць зададзены ключ.
Пазней, вы б выкарыстоўваць той жа хэш-функцыю
каб вызначыць, дзе ў хэш-табліцы, каб
пошук для дадзенага ключа.
Па гэтай прычыне, важна, што хэш
функцыя паводзіць сябе паслядоўна і выхады
тое ж значэнне хэша для аднолькавых ключоў.
Ведайце, што хэш-табліцы можа быць выкарыстаны для
захоўваць дадзеныя ўсіх тыпаў.
Але спрасціць рэчы, мы засяродзімся на
Струны для цяпер.
Вось просты хэш-функцыя для радкоў.
Гэта хэш-функцыя вылічае хэш
функцыя, заснаваная на першай літары
ключ.
"Яблык" пачынаецца з літары "А", так што гэта
супастаўляецца з індэксам 0 у хэш-табліцы.
Акрамя таго, "банан" супастаўляецца з індэксам 1,
і "кошка" супастаўляецца з індэксам 2.
Калі сябар пытаецца, калі слова "сабака" знаходзіцца ў
табліца, мы будзем ўваходных "сабака" ў хэш
Функцыя, якая будзе выводзіць значэнне хэш-функцыі
3.
З "сабака" ня захоўваецца з індэксам 3, мы
Можна з упэўненасцю сказаць, што "сабака" ня
ў табліцы,
хоць мы толькі праверылі адно з
хэш 26 індэксаў табліцы.
Час кідаць ключ ў рэчах.
Што рабіць, калі мы хочам захаваць "мурашкі" у
табліца, а?
"Мурашка" хэшы для індэкса 0, гэтак жа, як "яблык" зрабіў.
Гэта з'яўляецца прыкладам сутыкнення,
Вынікам двух ключоў хэшавання, каб тое ж самае
індэкс.
Нават калі ваш хэш-табліцы больш, чым
ўсталяваць Вашы дадзеныя, і вы выбралі добры
хэш-функцыя,
Вы ўсё яшчэ патрэбен план для барацьбы з
сутыкнення, калі і калі яны ўзнікаюць.
Давайце абмяркуем плюсы і мінусы двух
агульныя метады для вырашэння калізій:
лінейная зандзіравання і асобны ланцужкі.
З лінейным зандзіраваннем, калі ключ хэшы для
аналагічны паказчык, як раней захаваныя
ключ, яму прысвойваецца наступны даступны
слот ў табліцы.
Так, "мурашка" зараз захоўваецца з індэксам 3, так як
індэксы 0, 1, і 2 ўжо былі ў выкарыстанні.
І калі мы спрабуем захаваць трэцяе слова, што
пачынаецца з літары "А", ён прызначаецца
індэксаваць 4, так як індэксы 0, 1, 2 і 3
поўныя.
Як вы можаце бачыць нават з гэтага простага
Напрыклад, як толькі ўзнікае калізія, вам
значна павялічыць шанцы таго, што
іншы сутыкнення будуць адбывацца ў той жа самы
плошчу.
Гэта называецца кластарызацыі, і гэта
Сур'ёзным недахопам да лінейным зандзіравання.
Акрамя таго, у горшым выпадку ўстаўкі, выдалення,
і раз падстаноўкі ўжо перададзеныя O (N),
як на наступны свабодны слот можа мець
патэнцыйна быў апошнім слот ў табліцы.
Можа быць, асобныя ланцужкі прапануе больш
прывабным рашэннем.
У асобнай мадэлі цепочечной хэш
табліца на самай справе масіў паказальнікаў на
звязаныя спісы.
Пры ўзнікненні сутыкненняў, ключ можа быць
ўстаўляецца ў пастаянным час на чале
адпаведная звязаны спіс.
Што адбываецца цяпер, калі мы шукаем "яблык"
ў хэш-табліцы?
У горшым выпадку, мы павінны прайсці
Ўвесь звязаны спіс, пачынаючы з індэкса 0.
Найгоршы час пошуку для хэш
табліца, якая выкарыстоўвае паасобнага звязвання з'яўляецца
Таму Аб (п / к), дзе да
памер хэш-табліцы.
Секундочку, да-пастаянная.
Так O (п / к) на самай справе проста Аб (п),
які быў найгоршы час пошуку для
звязаны спіс.
Ці сапраўды мы прайшлі праз усе
Бяда даведацца пра хэш-табліцы
толькі ў канчатковым выніку туды, дзе мы пачалі?
Гэта можа быць у выпадку з тэарэтычнай
перспектыва, але ў рэальным свеце,
Аб (п / к) можа быць велізарнае паляпшэнне ў параўнанні
O (N).
Падумайце пра гэта так: лічыць да
10 - вы б аддалі перавагу чакаць 100 секунд
або 100 / да?
10 секунд ад Microsoft Word, каб скончыць
праверка арфаграфіі дакумента.
Як вы толькі што бачылі, вырашэння канфліктаў
цягне за сабой адзін від лінейнага пошуку або
іншы, што запавольвае працу
значна.
Такім чынам, вы хочаце, каб выбраць хэш
функцыя, якая зводзіць да мінімуму верагоднасць
сутыкнення, якія адбываюцца ў першую чаргу.
Вось некаторыя ўласцівасці добрай хэш
функцыі, мець на ўвазе.
Добры хэш-функцыя павінна выкарыстоўваць
ўся інфармацыя, прадстаўленая дадзенага ключа
каб максымізаваць колькасць
Магчымыя значэнні хэш-функцыі.
Напрыклад, калі ў нас было два радкі, "кошка"
і "Вусень", мы хацелі б, каб яны хэш
у розныя месцы на стале.
Калі хэш-функцыя толькі ўлічылі
першы раз, два, ці нават тры літары
з радкоў, сутыкненне адбудзецца,
так як абодва словы пачынаюцца з той жа
тры літары.
Значэнні хэш варта раўнамерна
праз хэш-табліцы.
Гэта дазволіць скараціць даўжыню звязаны
спісы павінны сутыкнення адбываюцца.
Гэта таксама добры знак, калі ваш хэш-значэнне
здольны генераваць вельмі розныя
хэш значэння для аналагічных ключоў,
робячы сутыкненняў значна радзей.
Наша мэта хутчэйшага ўстаўкі, выдалення,
і пошук.
Хэш-функцыя гуляе важную ролю ў
кожны з гэтых працэсаў і будзе
называецца вельмі часта.
Такім чынам, пераканайцеся, што ён працуе толькі вельмі
Проста, хутка аперацый, каб мінімізаваць прабег
Час.
Я спадзяюся, вам спадабалася гэта рэзюмэ
ўвядзенне на хеши.
Мяне клічуць Ларэн, і гэта CS50.