1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:01,900 [Грає музика] 3 00:00:01,900 --> 00:00:05,710 4 00:00:05,710 --> 00:00:09,150 >> ДАГ Lloyd: В даний час ви знаю багато про масивах, 5 00:00:09,150 --> 00:00:11,610 і ви знаєте, багато про пов'язаних списків. 6 00:00:11,610 --> 00:00:13,650 І ми обговоримо плюси і мінуси, ми 7 00:00:13,650 --> 00:00:16,620 обговорювали, що пов'язано списки може отримати більше і менше, 8 00:00:16,620 --> 00:00:18,630 але вони займають більше розмір. 9 00:00:18,630 --> 00:00:22,359 Масиви є набагато більш проста в використовувати, але вони обмежувальний стільки 10 00:00:22,359 --> 00:00:24,900 як ми повинні встановити розмір масив на самому початку 11 00:00:24,900 --> 00:00:26,910 і тоді ми застрягли з ним. 12 00:00:26,910 --> 00:00:30,470 >> Але це, ми значною мірою вичерпані всі наші теми 13 00:00:30,470 --> 00:00:33,040 про пов'язані списків і масивів. 14 00:00:33,040 --> 00:00:34,950 Або у нас? 15 00:00:34,950 --> 00:00:37,720 Може бути, ми можемо зробити щось ще більш творчим. 16 00:00:37,720 --> 00:00:40,950 І щось позичає Ідея хеш-таблиці. 17 00:00:40,950 --> 00:00:46,680 >> Таким чином, в хеш-таблиці, ми збираємося, щоб спробувати об'єднати масив з пов'язаного списку. 18 00:00:46,680 --> 00:00:49,520 Ми збираємося скористатися перевагами масиву, як довільного доступу, 19 00:00:49,520 --> 00:00:53,510 будучи в стані просто йти до масиву елемент 4 або елемент масиву 8 20 00:00:53,510 --> 00:00:55,560 без перебору всієї. 21 00:00:55,560 --> 00:00:57,260 Це досить швидко, чи не так? 22 00:00:57,260 --> 00:01:00,714 >> Але ми також хочемо, щоб наші дані Структура мати можливість рости і скорочуватися. 23 00:01:00,714 --> 00:01:02,630 Нам не потрібно, ми не хочу бути обмежене. 24 00:01:02,630 --> 00:01:04,588 І ми хочемо, щоб мати можливість додавати і видаляти речі 25 00:01:04,588 --> 00:01:08,430 дуже легко, що, якщо ви пам'ятаєте, є дуже складним з масивом. 26 00:01:08,430 --> 00:01:11,650 І ми можемо назвати це нова річ хеш-таблицю. 27 00:01:11,650 --> 00:01:15,190 >> І якщо все зроблено правильно, ми начебто прийняття 28 00:01:15,190 --> 00:01:18,150 переваги обох даних структури ви вже бачили, 29 00:01:18,150 --> 00:01:19,880 Масиви і зв'язані списки. 30 00:01:19,880 --> 00:01:23,070 Вставка може почати мають тенденцію до тета 1. 31 00:01:23,070 --> 00:01:26,207 Тета ми не обговорювали, але тета тільки в середньому випадку, 32 00:01:26,207 --> 00:01:27,540 що насправді станеться. 33 00:01:27,540 --> 00:01:29,680 Ви не завжди буде є найгірший сценарій, 34 00:01:29,680 --> 00:01:32,555 і ви не завжди будете мати в кращому випадку, так що 35 00:01:32,555 --> 00:01:33,900 середня сценарій? 36 00:01:33,900 --> 00:01:36,500 >> Ну в середньому вставки в хеш-таблиці 37 00:01:36,500 --> 00:01:39,370 може почати наближатися до постійної часу. 38 00:01:39,370 --> 00:01:41,570 І видалення можете отримати близько до постійної часу. 39 00:01:41,570 --> 00:01:44,440 І пошук можна отримати близько до постійної часу. 40 00:01:44,440 --> 00:01:48,600 That's-- ми не маємо даних Структура ще, що можна зробити, що, 41 00:01:48,600 --> 00:01:51,180 і таким чином це вже звучить як досить велика справа. 42 00:01:51,180 --> 00:01:57,010 Ми дійсно пом'якшила недоліки кожного на власну. 43 00:01:57,010 --> 00:01:59,160 >> Щоб отримати цю роботу оновити, хоча, ми 44 00:01:59,160 --> 00:02:03,580 потрібно переосмислити те, як ми додаємо Дані в структуру. 45 00:02:03,580 --> 00:02:07,380 Зокрема, ми хочемо, щоб Самі дані, щоб повідомити 46 00:02:07,380 --> 00:02:09,725 де вона повинна йти в структурі. 47 00:02:09,725 --> 00:02:12,850 І якщо ми тоді повинні бачити, якщо він знаходиться в структура, якщо нам потрібно, щоб знайти його, 48 00:02:12,850 --> 00:02:16,610 ми хочемо, щоб подивитися на дані знову і бути в змозі ефективно, 49 00:02:16,610 --> 00:02:18,910 з використанням даних, випадковим чином доступ до нього. 50 00:02:18,910 --> 00:02:20,700 Просто дивлячись на Дані, які ми повинні мати 51 00:02:20,700 --> 00:02:25,890 ідея, де саме ми збираюся знайти його в хеш-таблиці. 52 00:02:25,890 --> 00:02:28,770 >> Тепер нижня сторона хеш Таблиця є те, що вони насправді 53 00:02:28,770 --> 00:02:31,770 досить погано замовлення або сортування даних. 54 00:02:31,770 --> 00:02:34,970 І справді, якщо ви починаєте використовувати їх на замовлення або роду 55 00:02:34,970 --> 00:02:37,990 дані, які ви втратите всі з Переваги раніше 56 00:02:37,990 --> 00:02:40,710 була по вставки і видалення. 57 00:02:40,710 --> 00:02:44,060 Час стає ближче до тета п, і ми в основному 58 00:02:44,060 --> 00:02:45,530 регрес у зв'язаному списку. 59 00:02:45,530 --> 00:02:48,850 І тому ми хочемо використовувати тільки хеш Таблиці, якщо ми не дбаємо про 60 00:02:48,850 --> 00:02:51,490 Чи упорядковано дані. 61 00:02:51,490 --> 00:02:54,290 Для умов, в яких Ви будете використовувати їх в CS50 62 00:02:54,290 --> 00:02:58,900 Ви, ймовірно, не хвилює, що дані будуть відсортовані. 63 00:02:58,900 --> 00:03:03,170 >> Таким чином, хеш-таблиця являє собою поєднання з двох окремих частин 64 00:03:03,170 --> 00:03:04,980 з якою ми знайомі. 65 00:03:04,980 --> 00:03:07,930 По-перше, це функція, яка ми зазвичай називаємо хеш-функції. 66 00:03:07,930 --> 00:03:11,760 І, що хеш-функція буде повернутися деякий невід'ємне ціле число, що 67 00:03:11,760 --> 00:03:14,870 ми зазвичай називаємо хеш-код, ОК? 68 00:03:14,870 --> 00:03:20,230 Друга частина являє собою масив, який є здатний зберігати дані типу ми 69 00:03:20,230 --> 00:03:22,190 хоче розмістити в структурі даних. 70 00:03:22,190 --> 00:03:24,310 Ми утримати на пов'язані елемент списку зараз 71 00:03:24,310 --> 00:03:27,810 і просто почати з основами з хеш-таблиці, щоб отримати свою голову навколо нього, 72 00:03:27,810 --> 00:03:30,210 і тоді ми будемо, можливо, підірвати Ваш розум небагато, коли ми 73 00:03:30,210 --> 00:03:32,920 об'єднати масиви і списки посилань разом. 74 00:03:32,920 --> 00:03:35,590 >> Основна ідея, хоча це ми беремо деякі дані. 75 00:03:35,590 --> 00:03:37,860 Ми біжимо, що дані через хеш-функція. 76 00:03:37,860 --> 00:03:41,980 І так як дані оброблені і він випльовує номер, ОК? 77 00:03:41,980 --> 00:03:44,890 А потім з цим номером ми просто зберігати дані 78 00:03:44,890 --> 00:03:48,930 ми хочемо, щоб зберегти Масив в цьому місці. 79 00:03:48,930 --> 00:03:53,990 Так, наприклад, у нас є, може бути, це хеш-таблиці рядків. 80 00:03:53,990 --> 00:03:57,350 Він отримав 10 елементів у ньому, тому ми можемо відповідати 10 рядків в ньому. 81 00:03:57,350 --> 00:03:59,320 >> Скажімо, ми хочемо, щоб прояснити Іоанна. 82 00:03:59,320 --> 00:04:02,979 Так як Іоанн даних ми хочемо вставити в цьому хеш-таблиці десь. 83 00:04:02,979 --> 00:04:03,770 Де ми покласти його? 84 00:04:03,770 --> 00:04:05,728 Ну, як правило, з Масив цих пір ми, ймовірно, 85 00:04:05,728 --> 00:04:07,610 буде покласти його в масив розташування 0. 86 00:04:07,610 --> 00:04:09,960 Але тепер у нас є цей новий хеш-функції. 87 00:04:09,960 --> 00:04:13,180 >> І давайте скажемо, що ми біжимо від Іоанна через цей хеш-функції 88 00:04:13,180 --> 00:04:15,417 і це випльовує 4. 89 00:04:15,417 --> 00:04:17,500 Ну ось, де ми захоче поставити Іоанна. 90 00:04:17,500 --> 00:04:22,050 Ми хочемо, щоб покласти Іоанна в місці масиву 4, тому що якщо ми хешування Іоанна again-- 91 00:04:22,050 --> 00:04:23,810 скажемо пізніше ми хочете, щоб пошук і подивитися, 92 00:04:23,810 --> 00:04:26,960 якщо Джон існує в цьому хеш table-- все, що потрібно зробити, 93 00:04:26,960 --> 00:04:30,310 виконується його через той же хеш Функція, отримати номер 4 з, 94 00:04:30,310 --> 00:04:33,929 і бути в змозі знайти Джона негайно в нашій структурі даних. 95 00:04:33,929 --> 00:04:34,720 Це дуже добре. 96 00:04:34,720 --> 00:04:36,928 >> Скажімо, зараз ми це зробити знову ж таки, ми хочемо, щоб прояснити Павла. 97 00:04:36,928 --> 00:04:39,446 Ми хочемо, щоб додати Павла в цьому хеш-таблиці. 98 00:04:39,446 --> 00:04:42,070 Давайте припустимо, що на цей раз ми стикаємося Павло через хеш-функції, 99 00:04:42,070 --> 00:04:44,600 хеш, який генерується 6. 100 00:04:44,600 --> 00:04:47,340 Ну ми можемо поставити Павла в місці масиву 6. 101 00:04:47,340 --> 00:04:50,040 І якщо ми повинні дивитися на Чи Підлога в цьому хеш-таблиці, 102 00:04:50,040 --> 00:04:53,900 все, що потрібно зробити, це запустити Пол через хеш-функції знову 103 00:04:53,900 --> 00:04:55,830 і ми збираємося, щоб отримати 6 знову. 104 00:04:55,830 --> 00:04:57,590 >> А потім ми просто подивитися на місці масиву 6. 105 00:04:57,590 --> 00:04:58,910 Павло потрапити? 106 00:04:58,910 --> 00:05:00,160 Якщо це так, він в хеш-таблиці. 107 00:05:00,160 --> 00:05:01,875 Павло не так? 108 00:05:01,875 --> 00:05:03,000 Він не в хеш-таблиці. 109 00:05:03,000 --> 00:05:05,720 Це досить просто. 110 00:05:05,720 --> 00:05:07,770 >> Тепер, як ви визначаєте хеш-функції? 111 00:05:07,770 --> 00:05:11,460 Ну там насправді немає обмежень на число можливих хеш-функцій. 112 00:05:11,460 --> 00:05:14,350 Насправді є ряд дуже, дійсно хороші в Інтернеті. 113 00:05:14,350 --> 00:05:17,560 Там це кількість насправді, дійсно погані в Інтернеті. 114 00:05:17,560 --> 00:05:21,080 Це також досить легко написати поганий. 115 00:05:21,080 --> 00:05:23,760 >> Так що ж робить хорошу Хеш функція, вірно? 116 00:05:23,760 --> 00:05:27,280 Ну добре хеш-функція повинна використовувати тільки будучи хешіруется дані, 117 00:05:27,280 --> 00:05:29,420 і всі даних, хешірованного. 118 00:05:29,420 --> 00:05:32,500 Таким чином, ми не хочемо, щоб використовувати anything-- ми нічого не включати 119 00:05:32,500 --> 00:05:35,560 то в іншому місці, ніж дані. 120 00:05:35,560 --> 00:05:37,080 І ми хочемо, щоб використати всі дані. 121 00:05:37,080 --> 00:05:39,830 Ми не хочемо, щоб просто використовувати шматок це, ми хочемо, щоб використовувати все це. 122 00:05:39,830 --> 00:05:41,710 Хеш-функція повинна Також бути детермінованим. 123 00:05:41,710 --> 00:05:42,550 Що це означає? 124 00:05:42,550 --> 00:05:46,200 Ну це означає, що кожен раз, коли ми пройти той же шматок даних 125 00:05:46,200 --> 00:05:50,040 в хеш-функции ми завжди отримати той же хеш-код з. 126 00:05:50,040 --> 00:05:52,870 Якщо я проходжу Джона в Хеш функція я виходжу 4. 127 00:05:52,870 --> 00:05:56,110 Я повинен бути в змозі зробити це 10000 раз, і я завжди буду отримати 4. 128 00:05:56,110 --> 00:06:00,810 Ефективно, так не випадкові числа можуть бути залучені в нашій хеш tables-- 129 00:06:00,810 --> 00:06:02,750 в наших хеш-функцій. 130 00:06:02,750 --> 00:06:05,750 >> Хеш-функція повинна також рівномірно розподіляти дані. 131 00:06:05,750 --> 00:06:09,700 Якщо кожен раз, коли ви запустите дані через Хеш функція, яку ви отримаєте хеш 0, 132 00:06:09,700 --> 00:06:11,200 це, напевно, не так здорово, правда? 133 00:06:11,200 --> 00:06:14,600 Ви, напевно, хочете, щоб більша діапазон хеш-кодів. 134 00:06:14,600 --> 00:06:17,190 Також речі можна поширити з усієї таблиці. 135 00:06:17,190 --> 00:06:23,210 А також було б здорово, якби насправді аналогічні дані, такі як Джон і Джонатан, 136 00:06:23,210 --> 00:06:26,320 може бути, були поширені зважити різних місцях в хеш-таблиці. 137 00:06:26,320 --> 00:06:28,750 Це було б гарна перевага. 138 00:06:28,750 --> 00:06:31,250 >> Ось приклад з хеш-функції. 139 00:06:31,250 --> 00:06:33,150 Я написав це одне вгору раніше. 140 00:06:33,150 --> 00:06:35,047 Це не особливо хороша функція хешування 141 00:06:35,047 --> 00:06:37,380 з причин, які дійсно не нести вдаючись у прямо зараз. 142 00:06:37,380 --> 00:06:41,040 Але ви бачите, що тут відбувається? 143 00:06:41,040 --> 00:06:44,420 Схоже, ми оголошенні змінної називається сума і встановивши його рівним 0. 144 00:06:44,420 --> 00:06:50,010 А потім, мабуть, я роблю щось так довго, як strstr [J] НЕ дорівнює 145 00:06:50,010 --> 00:06:52,490 в зворотну косу риску 0. 146 00:06:52,490 --> 00:06:54,870 Що я там робив? 147 00:06:54,870 --> 00:06:57,440 >> Це в основному просто ще один спосіб реалізації [? strl?] 148 00:06:57,440 --> 00:06:59,773 та виявлення, коли ви досягли кінця рядка. 149 00:06:59,773 --> 00:07:02,480 Так що я не є насправді обчислити довжину рядка, 150 00:07:02,480 --> 00:07:05,640 Я тільки за допомогою, коли я потрапив в Зворотна коса риса характеру 0 Я знаю, 151 00:07:05,640 --> 00:07:07,185 Я досяг кінця рядка. 152 00:07:07,185 --> 00:07:09,560 А потім я збираюся тримати переборі цього рядка, 153 00:07:09,560 --> 00:07:15,310 додавши strstr [J], щоб підвести, а потім на Кінець дня збирається повернутися суми мод 154 00:07:15,310 --> 00:07:16,200 HASH_MAX. 155 00:07:16,200 --> 00:07:18,700 >> В основному все це хеш функція робить це додавання до 156 00:07:18,700 --> 00:07:23,450 всі значення ASCII в мій рядок, а потім це 157 00:07:23,450 --> 00:07:26,390 повернення деякий хеш Коментарі від HASH_MAX. 158 00:07:26,390 --> 00:07:29,790 Це, ймовірно, розмір моєї масиву, вірно? 159 00:07:29,790 --> 00:07:33,160 Я не хочу, щоб отримувати хеш коди, якщо мій масив має розмір 10, 160 00:07:33,160 --> 00:07:35,712 Я не хочу, щоб отримувати з хеш-коди 11, 12, 161 00:07:35,712 --> 00:07:38,690 13, я не можу покласти речі в ці місця масиву, 162 00:07:38,690 --> 00:07:39,790 що було б незаконним. 163 00:07:39,790 --> 00:07:42,130 Я страждаю помилку сегментації. 164 00:07:42,130 --> 00:07:45,230 >> Тепер ось ще один швидкий в сторону. 165 00:07:45,230 --> 00:07:48,470 Як правило, ви, ймовірно, не збирається хочу написати свої власні хеш-функції. 166 00:07:48,470 --> 00:07:50,997 Це насправді трохи мистецтво, а не наука. 167 00:07:50,997 --> 00:07:52,580 І є багато, що йде в них. 168 00:07:52,580 --> 00:07:55,288 Інтернет, як я вже сказав, це повний дійсно хороших хеш-функції, 169 00:07:55,288 --> 00:07:58,470 і ви повинні використовувати Інтернет для знайти хеш-функцій, тому що це дійсно 170 00:07:58,470 --> 00:08:03,230 тільки вид непотрібним марна трата часу, щоб створити свій власний. 171 00:08:03,230 --> 00:08:05,490 >> Ви можете написати прості з них для цілей тестування. 172 00:08:05,490 --> 00:08:08,323 Але коли ви дійсно збираєтеся почати хешування даних і зберігати його 173 00:08:08,323 --> 00:08:10,780 в хеш-таблицю ви знаходитесь ймовірно, хочете 174 00:08:10,780 --> 00:08:14,580 використовувати деякі функції, який був створений для вас, що існує в Інтернеті. 175 00:08:14,580 --> 00:08:17,240 Якщо ви тільки переконайтеся, що привести свої джерела. 176 00:08:17,240 --> 00:08:21,740 Там немає причин, щоб плагіатом тут нічого. 177 00:08:21,740 --> 00:08:25,370 >> Інформатика співтовариство безумовно, зростає, і справді значення 178 00:08:25,370 --> 00:08:28,796 з відкритим вихідним кодом, і це дійсно важливо привести свої джерела, так що люди 179 00:08:28,796 --> 00:08:30,670 може отримати атрибуцію робота, що вони 180 00:08:30,670 --> 00:08:32,312 робить на благо спільноти. 181 00:08:32,312 --> 00:08:34,020 Так завжди бути sure-- і не тільки для хеш 182 00:08:34,020 --> 00:08:37,270 функції, але, як правило, коли вам використовувати код з зовнішнього джерела, 183 00:08:37,270 --> 00:08:38,299 завжди наводжу своє джерело. 184 00:08:38,299 --> 00:08:43,500 Дайте кредит на людину, яка зробила деякі роботи, так що ви не повинні. 185 00:08:43,500 --> 00:08:46,720 >> ОТЖЕ, давайте повернутися до цього хеш-таблиця на секунду. 186 00:08:46,720 --> 00:08:48,780 Це де ми залишили від після того як ми вставлені 187 00:08:48,780 --> 00:08:53,300 Джон і Пол в цьому хеш-таблиці. 188 00:08:53,300 --> 00:08:55,180 Ви бачите тут проблему? 189 00:08:55,180 --> 00:08:58,410 Ви можете побачити два. 190 00:08:58,410 --> 00:09:02,240 Але зокрема, зробити вас подивитися можливі проблеми? 191 00:09:02,240 --> 00:09:06,770 >> Що робити, якщо я хеш Рінго, і це Виходить, що після обробки 192 00:09:06,770 --> 00:09:14,000 що дані через хеш-функції Рінго сформувала хеш 6. 193 00:09:14,000 --> 00:09:16,810 Я вже отримав дані в hashcode-- розташування масиву 6. 194 00:09:16,810 --> 00:09:22,000 Так що це, ймовірно, буде трохи проблеми для мене зараз, чи не так? 195 00:09:22,000 --> 00:09:23,060 >> Ми називаємо це зіткнення. 196 00:09:23,060 --> 00:09:26,460 І зіткнення відбувається, коли два фрагменти даних пропускали через той же хеш 197 00:09:26,460 --> 00:09:29,200 Функція дають однаковий хеш-код. 198 00:09:29,200 --> 00:09:32,850 Імовірно ми все ще хочемо, щоб і фрагменти даних в хеш-таблиці, 199 00:09:32,850 --> 00:09:36,330 в іншому випадку ми б не працює Рінго довільно через хеш-функції. 200 00:09:36,330 --> 00:09:40,870 Ми, ймовірно, хочете отримати Рінго в цьому масиві. 201 00:09:40,870 --> 00:09:46,070 >> Як ми це робимо, хоча, якщо він і Павло і вихід хеш 6? 202 00:09:46,070 --> 00:09:49,520 Ми не хочемо, щоб перезаписати Павла, ми хочемо, щоб Пол там теж. 203 00:09:49,520 --> 00:09:52,790 Таким чином, ми повинні знайти спосіб, щоб отримати елементи в хеш-таблиці, що 204 00:09:52,790 --> 00:09:56,550 все ще зберігає наше швидке вставка і швидкий погляд на. 205 00:09:56,550 --> 00:10:01,350 І один із способів боротьби з ним є зробити щось під назвою лінійний зондування. 206 00:10:01,350 --> 00:10:04,170 >> Використовуючи цей метод, якщо у нас є Зіткнення, ну, що ж нам робити? 207 00:10:04,170 --> 00:10:08,580 Ну, ми не можемо поставити його в місці масиву 6, або щось хеш-код був створений, 208 00:10:08,580 --> 00:10:10,820 давайте його на HashCode плюс 1. 209 00:10:10,820 --> 00:10:13,670 І якщо це повний давайте покласти його в HashCode плюс 2. 210 00:10:13,670 --> 00:10:17,420 Перевага цієї істоти, якщо він не точно, де ми думаємо, що він, 211 00:10:17,420 --> 00:10:20,850 і у нас є, щоб почати пошук, може бути, ми не повинні йти занадто далеко. 212 00:10:20,850 --> 00:10:23,900 Може бути, ми не повинні шукати всі п елементів хеш-таблиці. 213 00:10:23,900 --> 00:10:25,790 Може бути, ми повинні шукати пару з них. 214 00:10:25,790 --> 00:10:30,680 >> І тому ми все ще тенденцію до що середня справа бути близько до 1 проти 215 00:10:30,680 --> 00:10:34,280 близько до п, так що, може бути, буду працювати. 216 00:10:34,280 --> 00:10:38,010 Отже, давайте подивимося, як це може працювати в реальності. 217 00:10:38,010 --> 00:10:41,460 І давайте подивимося, якщо можливо, ми можемо виявити проблема, що може статися тут. 218 00:10:41,460 --> 00:10:42,540 >> Скажімо, ми хеш Барта. 219 00:10:42,540 --> 00:10:45,581 Так що тепер ми збираємося запустити новий набір рядків через хеш-функції, 220 00:10:45,581 --> 00:10:48,460 і ми біжимо Барта через хеш Функція, ми отримуємо хеш 6. 221 00:10:48,460 --> 00:10:52,100 Ми дивимося, ми бачимо 6 порожній, так що ми можемо поставити Барта є. 222 00:10:52,100 --> 00:10:55,410 >> Тепер ми хеш Лізу, і що також генерує хеш 6. 223 00:10:55,410 --> 00:10:58,330 Ну тепер, коли ми за допомогою цього лінійний метод зондування ми починаємо в 6, 224 00:10:58,330 --> 00:10:59,330 ми бачимо, що 6 заповнена. 225 00:10:59,330 --> 00:11:00,990 Ми не можемо Лізу в 6. 226 00:11:00,990 --> 00:11:02,090 Так куди ми йдемо? 227 00:11:02,090 --> 00:11:03,280 Давайте 7. 228 00:11:03,280 --> 00:11:04,610 7 порожньо, так що працює. 229 00:11:04,610 --> 00:11:06,510 Так давайте Лізі там. 230 00:11:06,510 --> 00:11:10,200 >> Тепер ми хеш Гомера, і ми отримуємо 7. 231 00:11:10,200 --> 00:11:13,380 ОК добре ми знаємо, що 7 повно Тепер, так ми не можемо поставити Гомера є. 232 00:11:13,380 --> 00:11:14,850 Отже, давайте по 8. 233 00:11:14,850 --> 00:11:15,664 Є 8 доступні? 234 00:11:15,664 --> 00:11:18,330 Так, і близько до 7, 8, так, якщо у нас є, щоб почати пошук ми 235 00:11:18,330 --> 00:11:20,020 не доведеться заходити надто далеко. 236 00:11:20,020 --> 00:11:22,860 І так давайте Гомера на 8. 237 00:11:22,860 --> 00:11:25,151 >> Тепер ми хеш Меггі і повертає 3, слава богу 238 00:11:25,151 --> 00:11:26,650 ми можемо просто поставити Меггі є. 239 00:11:26,650 --> 00:11:29,070 Ми не повинні робити нічого Сортувати зондування для цього. 240 00:11:29,070 --> 00:11:32,000 Тепер ми хеш Мардж, і Мардж також повертає 6. 241 00:11:32,000 --> 00:11:39,560 >> Ну 6 повний, 7 повний, 8 повний, 9, все в порядку, слава Богу, 9 порожній. 242 00:11:39,560 --> 00:11:41,600 Я можу поставити Мардж в 9. 243 00:11:41,600 --> 00:11:45,280 Вже зараз ми бачимо, що ми починаємо щоб мати цю проблему, де зараз ми 244 00:11:45,280 --> 00:11:48,780 починаючи розтягнути речі на зразок з далеко від своїх хеш-кодів. 245 00:11:48,780 --> 00:11:52,960 І, що тета 1, що середня Справа в тому, постійна часу, 246 00:11:52,960 --> 00:11:56,560 починає отримувати трохи more-- починають, як правило, трохи більше, 247 00:11:56,560 --> 00:11:58,050 до тета п. 248 00:11:58,050 --> 00:12:01,270 Ми починаємо втрачати, що Перевага хеш-таблиці. 249 00:12:01,270 --> 00:12:03,902 >> Це проблема, яку ми тільки що бачили це те, що називається кластеризації. 250 00:12:03,902 --> 00:12:06,360 І те, що дійсно погано кластеризація, що як тільки ви в даний час 251 00:12:06,360 --> 00:12:09,606 є два елементи, які сторона від сторону він робить це навіть скоріше, 252 00:12:09,606 --> 00:12:11,480 у вас є подвійний шанс, що ви збираєтеся 253 00:12:11,480 --> 00:12:13,516 щоб ще зіткнення з цього кластеру, 254 00:12:13,516 --> 00:12:14,890 і кластер зростатиме по одному. 255 00:12:14,890 --> 00:12:19,640 І ви будете тримати росте і росте ваш ймовірність наявності зіткнення. 256 00:12:19,640 --> 00:12:24,470 І врешті-решт це так само погано, а не сортування даних взагалі. 257 00:12:24,470 --> 00:12:27,590 >> Інша проблема, хоча це ми Тим не менше, і досі до цього моменту, 258 00:12:27,590 --> 00:12:30,336 Ми тільки щось розуміючи, що хеш-таблиця є, 259 00:12:30,336 --> 00:12:31,960 ми як і раніше є тільки номер для 10 рядків. 260 00:12:31,960 --> 00:12:37,030 Якщо ми хочемо продовжувати хеш громадяни Спрінгфілда, 261 00:12:37,030 --> 00:12:38,790 ми можемо отримати тільки 10 з них там. 262 00:12:38,790 --> 00:12:42,619 І якщо ми будемо намагатися додати 11 або 12, ми не є місце, щоб помістити їх. 263 00:12:42,619 --> 00:12:45,660 Ми могли б просто бути спінінг навколо в кола, намагаючись знайти порожнє місце, 264 00:12:45,660 --> 00:12:49,000 і ми, можливо, застрягли у нескінченному циклі. 265 00:12:49,000 --> 00:12:51,810 >> Так що це свого роду позичає ідеї про щось називається ланцюжка. 266 00:12:51,810 --> 00:12:55,790 І це, де ми збираємося, щоб принести зв'язані списки повернутися в картину. 267 00:12:55,790 --> 00:13:01,300 Що робити, якщо замість того, щоб зберігати тільки самі дані в масиві, 268 00:13:01,300 --> 00:13:04,471 кожен елемент масиву може провести кілька штук даних? 269 00:13:04,471 --> 00:13:05,970 Ну, що не має сенсу, чи не так? 270 00:13:05,970 --> 00:13:09,280 Ми знаємо, що масив може тільки hold-- кожен елемент масиву 271 00:13:09,280 --> 00:13:12,930 може мати тільки один шматок даних цього типу даних. 272 00:13:12,930 --> 00:13:16,750 >> Але що, якщо це тип даних це зв'язаний список, чи не так? 273 00:13:16,750 --> 00:13:19,830 Так що, якщо кожен елемент масиву був 274 00:13:19,830 --> 00:13:22,790 покажчик на голову пов'язаного списку? 275 00:13:22,790 --> 00:13:24,680 І тоді ми могли б побудувати ці зв'язані списки 276 00:13:24,680 --> 00:13:27,120 і вирощувати їх довільно, бо зв'язані списки дозволяють 277 00:13:27,120 --> 00:13:32,090 нам рости і скорочуватися набагато більше гнучко, ніж масив робить. 278 00:13:32,090 --> 00:13:34,210 Так що, якщо ми в даний час використовують, ми використовувати це, вірно? 279 00:13:34,210 --> 00:13:37,760 Ми починаємо вирощувати ці ланцюги З цих місцях масиву. 280 00:13:37,760 --> 00:13:40,740 >> Тепер ми можемо відповідати нескінченне Обсяг даних, або не безкінечне, 281 00:13:40,740 --> 00:13:44,170 довільну кількість Дані, у нашій хеш-таблиці 282 00:13:44,170 --> 00:13:47,760 ніколи не працює в Проблема зіткнення. 283 00:13:47,760 --> 00:13:50,740 Ми також усунені кластеризації, роблячи це. 284 00:13:50,740 --> 00:13:54,380 І добре відомо, що, коли ми вставляємо у зв'язаному списку, якщо ви пам'ятаєте, 285 00:13:54,380 --> 00:13:57,779 з нашого відео на пов'язаних списків, по одному зв'язані списки і двічі зв'язані списки, 286 00:13:57,779 --> 00:13:59,070 це постійна робота час. 287 00:13:59,070 --> 00:14:00,710 Ми просто додавши на фронт. 288 00:14:00,710 --> 00:14:04,400 >> І подивитися, добре ми знаємо які виглядають у вигляді пов'язаного списку 289 00:14:04,400 --> 00:14:05,785 може бути проблема, вірно? 290 00:14:05,785 --> 00:14:07,910 Ми повинні шукати через це від початку до кінця. 291 00:14:07,910 --> 00:14:10,460 Там немає випадкових доступ у зв'язаному списку. 292 00:14:10,460 --> 00:14:15,610 Але якщо замість того, один пов'язаний Список, де пошук буде O п, 293 00:14:15,610 --> 00:14:19,590 тепер у нас є 10 зв'язні списки, або 1000 зв'язані списки, 294 00:14:19,590 --> 00:14:24,120 тепер це О п ділиться на 10, або Про п ділиться на 1000. 295 00:14:24,120 --> 00:14:26,940 >> І в той час як ми говорили Теоретично про складність 296 00:14:26,940 --> 00:14:30,061 знехтувати константи, в реальному Світ ці речі насправді має значення, 297 00:14:30,061 --> 00:14:30,560 вірно? 298 00:14:30,560 --> 00:14:33,080 Ми насправді буде помітити що це відбувається 299 00:14:33,080 --> 00:14:36,610 для запуску 10 разів швидше, або в 1000 разів швидше 300 00:14:36,610 --> 00:14:41,570 бо ми поширенні один довгий ланцюг по 1000 дрібних ланцюгів. 301 00:14:41,570 --> 00:14:45,090 І так кожен раз, коли ми повинні шукати через один з цих ланцюгів ми може 302 00:14:45,090 --> 00:14:50,290 ігнорувати 999 ланцюгів Ми не дбаємо о, і просто шукати той. 303 00:14:50,290 --> 00:14:53,220 >> Яке в середньому 1000 разів коротше. 304 00:14:53,220 --> 00:14:56,460 І таким чином, ми як і раніше є свого роду тенденцію до цієї середньої випадку 305 00:14:56,460 --> 00:15:01,610 бути постійне час, але тільки тому, що ми використовуючи 306 00:15:01,610 --> 00:15:03,730 ділення якогось величезного постійного множника. 307 00:15:03,730 --> 00:15:05,804 Давайте подивимося, як це може насправді виглядають, хоча. 308 00:15:05,804 --> 00:15:08,720 Так що це було хеш-таблиці ми повинні були перш, ніж ми оголосили, що хеш-таблицю 309 00:15:08,720 --> 00:15:10,270 був здатний зберігати 10 рядків. 310 00:15:10,270 --> 00:15:11,728 Ми не збираємося цього робити. 311 00:15:11,728 --> 00:15:13,880 Ми вже знаємо, Обмеження цього методу. 312 00:15:13,880 --> 00:15:20,170 Тепер наша хеш-таблиці буде масив з 10 вузлів, покажчики 313 00:15:20,170 --> 00:15:22,120 керівникам пов'язаних списків. 314 00:15:22,120 --> 00:15:23,830 >> І зараз це нуль. 315 00:15:23,830 --> 00:15:26,170 Кожен з цих 10 покажчиків NULL. 316 00:15:26,170 --> 00:15:29,870 Там немає нічого в наших хеш-таблиці прямо зараз. 317 00:15:29,870 --> 00:15:32,690 >> Тепер давайте почнемо поставити деякі речі в цій хеш-таблиці. 318 00:15:32,690 --> 00:15:35,440 І давайте подивимося, як цей метод піде на користь нам небагато. 319 00:15:35,440 --> 00:15:36,760 Давайте тепер хеш Джоуї. 320 00:15:36,760 --> 00:15:40,210 Ми працюватиме рядок Джої через хеш-функція, і ми повертаємося 6. 321 00:15:40,210 --> 00:15:41,200 Ну, що ж нам тепер робити? 322 00:15:41,200 --> 00:15:44,090 >> Ну тепер працює зі зв'язаними списками, ми не працюємо з масивами. 323 00:15:44,090 --> 00:15:45,881 І коли ми працюємо зі зв'язаними списками ми 324 00:15:45,881 --> 00:15:49,790 знаю, що ми повинні почати динамічно виділення простору і будівельні ланцюгів. 325 00:15:49,790 --> 00:15:54,020 Це свого роду how-- ті ядро елементи побудови пов'язаного списку. 326 00:15:54,020 --> 00:15:57,670 Так давайте динамічно виділити місце для Joey, 327 00:15:57,670 --> 00:16:00,390 а потім давайте додамо його в ланцюзі. 328 00:16:00,390 --> 00:16:03,170 >> Так що тепер подивіться, що ми зробили. 329 00:16:03,170 --> 00:16:06,440 Коли ми хеш Джоуї ми отримали хеш 6. 330 00:16:06,440 --> 00:16:11,790 Тепер покажчик на місце масиву 6 вказує на голову пов'язаного списку, 331 00:16:11,790 --> 00:16:14,900 і зараз це єдиний елемент пов'язаного списку. 332 00:16:14,900 --> 00:16:18,350 І вузол в тому, що Зв'язаний список Джоуї. 333 00:16:18,350 --> 00:16:22,300 >> Так що, якщо ми повинні дивитися на Джоуї пізніше, ми просто хеш Джої знову, 334 00:16:22,300 --> 00:16:26,300 ми отримуємо 6 разів, тому що наші Хеш функція є детермінованою. 335 00:16:26,300 --> 00:16:30,400 І тоді ми починаємо в голову пов'язаного списку зазначив 336 00:16:30,400 --> 00:16:33,360 щоб по місцю розташування масиву 6, і ми можемо ітерації 337 00:16:33,360 --> 00:16:35,650 по, що, намагаючись знайти Джої. 338 00:16:35,650 --> 00:16:37,780 І якщо ми будуємо наш ефективно хеш-таблиці, 339 00:16:37,780 --> 00:16:41,790 і наша хеш-функція ефективно поширювати дані і, 340 00:16:41,790 --> 00:16:45,770 в середньому кожен з тих, які пов'язані Списки в будь-якому місці масиву 341 00:16:45,770 --> 00:16:50,110 буде 1/10 розмір, якщо ми тільки що його як один величезний 342 00:16:50,110 --> 00:16:51,650 Зв'язаний список з усім в ньому. 343 00:16:51,650 --> 00:16:55,670 >> Якщо ми розподіляємо, що величезна пов'язані Список по 10 пов'язаних списків 344 00:16:55,670 --> 00:16:57,760 кожен список буде 1/10 розмір. 345 00:16:57,760 --> 00:17:01,432 І таким чином в 10 разів швидше, шукати. 346 00:17:01,432 --> 00:17:02,390 Так давайте зробимо це знову. 347 00:17:02,390 --> 00:17:04,290 Давайте тепер хеш Росс. 348 00:17:04,290 --> 00:17:07,540 >> І, скажімо, Росс, коли ми робимо хеш-код повернемося 2. 349 00:17:07,540 --> 00:17:10,630 Ну тепер ми динамічно виділяти Новий вузол, ми ставимо Росс в цьому вузлі, 350 00:17:10,630 --> 00:17:14,900 і ми зараз сказати розташування масиву 2, а вказуючи на нуль, 351 00:17:14,900 --> 00:17:18,579 вказує на голову пов'язаний список, чиї тільки вузол Росс. 352 00:17:18,579 --> 00:17:22,660 І ми можемо зробити це ще раз, ми може хеш Рейчел і отримати хеш-код 4. 353 00:17:22,660 --> 00:17:25,490 Танос новий вузол, покласти в Рейчел вузол, і сказати осередок масиву 354 00:17:25,490 --> 00:17:27,839 4 тепер вказує на голові із зв'язаного списку, чиї 355 00:17:27,839 --> 00:17:31,420 Єдиний елемент, трапляється, Рейчел. 356 00:17:31,420 --> 00:17:33,470 >> ОК, але що станеться, якщо у нас є зіткнення? 357 00:17:33,470 --> 00:17:38,560 Давайте подивимося, як ми поводимося з зіткнень використовуючи окремий метод зчеплення. 358 00:17:38,560 --> 00:17:39,800 Давайте хеш Фібі. 359 00:17:39,800 --> 00:17:41,094 Ми отримуємо хеш 6. 360 00:17:41,094 --> 00:17:44,010 У нашому попередньому прикладі ми просто зберігання рядків у масиві. 361 00:17:44,010 --> 00:17:45,980 Це було проблемою. 362 00:17:45,980 --> 00:17:48,444 >> Ми не хочемо, щоб колошматити Джоуї, і ми вже 363 00:17:48,444 --> 00:17:51,110 видно, що ми можемо отримати деяке кластеризації проблеми, якщо ми спробуємо і крок 364 00:17:51,110 --> 00:17:52,202 через зонд і. 365 00:17:52,202 --> 00:17:54,660 Але що, якщо ми просто вид ставитися до цього так само, як, вірно? 366 00:17:54,660 --> 00:17:57,440 Це просто, як додавання елемента в голову пов'язаного списку. 367 00:17:57,440 --> 00:18:00,220 Давайте просто виділення пам'яті простір для Фібі. 368 00:18:00,220 --> 00:18:04,764 >> Ми скажемо, наступні пункти покажчик Фібі в старій голові пов'язаного списку, 369 00:18:04,764 --> 00:18:07,180 а потім 6 раз вказує на Новий глава пов'язаного списку. 370 00:18:07,180 --> 00:18:10,150 А тепер подивіться, що ми змінили Фібі в. 371 00:18:10,150 --> 00:18:14,210 Тепер ми можемо зберігати два елементи з HashCode 6, 372 00:18:14,210 --> 00:18:17,170 і ми не які-небудь проблеми. 373 00:18:17,170 --> 00:18:20,147 >> Це досить багато, всі є в ланцюжка. 374 00:18:20,147 --> 00:18:21,980 І, безумовно, ланцюжки метод, який це 375 00:18:21,980 --> 00:18:27,390 буде найбільш ефективним для вас, якщо Ви зберігаєте дані в хеш-таблиці. 376 00:18:27,390 --> 00:18:30,890 Але ця комбінація масиви і зв'язані списки 377 00:18:30,890 --> 00:18:36,080 разом, щоб сформувати хеш-таблицю насправді значно покращує вашу здатність 378 00:18:36,080 --> 00:18:40,550 для зберігання великих обсягів даних, і дуже швидко і ефективно шукати 379 00:18:40,550 --> 00:18:41,630 через цих даних. 380 00:18:41,630 --> 00:18:44,150 >> Там як і раніше ще один Структура даних там 381 00:18:44,150 --> 00:18:48,700 що, можливо, навіть буде трохи краще з точки зору забезпечення 382 00:18:48,700 --> 00:18:51,920 що наша вставка, видалення, і Подивіться пояс навіть швидше. 383 00:18:51,920 --> 00:18:55,630 І ми побачимо, що у відео на спроб. 384 00:18:55,630 --> 00:18:58,930 Я Дуг Ллойд, це CS50. 385 00:18:58,930 --> 00:19:00,214