[Грає музика] ДАГ 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.