1 00:00:06,979 --> 00:00:07,479 [ШУМУ]. 2 00:00:07,479 --> 00:00:09,367 Перед зануренням в хеш-таблиць, давайте 3 00:00:09,367 --> 00:00:11,196 спочатку розглянемо плюси і мінуси деяких 4 00:00:11,196 --> 00:00:13,202 прості структури даних, починаючи з 5 00:00:13,202 --> 00:00:14,739 масиви. 6 00:00:14,739 --> 00:00:16,869 Нагадаємо, що масиви дозволяють нам зберігати 7 00:00:16,869 --> 00:00:18,644 елементи одного типу даних 8 00:00:18,644 --> 00:00:21,259 безперервно в пам'яті. 9 00:00:21,259 --> 00:00:24,115 Оскільки кожен елемент пов'язаний з 10 00:00:24,115 --> 00:00:26,513 індекс, або місце, 11 00:00:26,513 --> 00:00:27,661 у нас є випадковий доступ до всіх 12 00:00:27,661 --> 00:00:28,860 елементи масиву. 13 00:00:28,860 --> 00:00:31,308 Іншими словами, ми можемо отримати доступ до будь-якого елементу 14 00:00:31,308 --> 00:00:33,468 в одному кроці від індексації в 15 00:00:33,468 --> 00:00:35,112 масивом. 16 00:00:35,112 --> 00:00:37,224 Це велика справа, тому що алгоритми 17 00:00:37,224 --> 00:00:39,204 як бінарного пошуку залежать від випадкових 18 00:00:39,204 --> 00:00:40,570 доступу. 19 00:00:40,570 --> 00:00:43,130 Недоліком масивів є те, що їх розмір 20 00:00:43,130 --> 00:00:44,380 фіксоване. 21 00:00:44,380 --> 00:00:46,630 Оскільки дані масиви магазин безперервно в 22 00:00:46,630 --> 00:00:49,490 пам'яті, необхідно вказати розмір масиву 23 00:00:49,490 --> 00:00:50,600 при оголошенні масиву. 24 00:00:50,600 --> 00:00:53,510 Ви ефективно питаючи операційної 25 00:00:53,510 --> 00:00:55,600 Система зарезервувати відповідну кількість 26 00:00:55,600 --> 00:00:58,080 пам'яті для елементів масиву. 27 00:00:58,080 --> 00:01:00,240 Там немає ніякої гарантії, що більше пам'яті, 28 00:01:00,240 --> 00:01:02,370 поруч з вашого масиву, будуть доступні 29 00:01:02,370 --> 00:01:03,480 для подальшого використання. 30 00:01:03,480 --> 00:01:05,550 Так масиви не можуть легко зростати. 31 00:01:05,550 --> 00:01:07,715 Нагадаємо, що ми також дізналися про пов'язані 32 00:01:07,715 --> 00:01:09,630 списки, які можуть рости, тому що їх 33 00:01:09,630 --> 00:01:12,430 елементи не є суміжними в пам'яті. 34 00:01:12,430 --> 00:01:14,680 Кожен вузол у зв'язаному списку містить 35 00:01:14,680 --> 00:01:16,620 елемент, який ми хочемо зберігати, а також 36 00:01:16,620 --> 00:01:18,976 покажчик на наступного елемента в 37 00:01:18,976 --> 00:01:19,756 список. 38 00:01:19,756 --> 00:01:22,560 На жаль, ціна, яку ми заплатили за 39 00:01:22,560 --> 00:01:24,945 динамічний розмір довільний доступ до 40 00:01:24,945 --> 00:01:26,460 елементи. 41 00:01:26,460 --> 00:01:28,760 Для того, щоб отримати доступ певний елемент, 42 00:01:28,760 --> 00:01:30,810 необхідно пройти по всьому 43 00:01:30,810 --> 00:01:32,910 список, поки шуканий елемент не є 44 00:01:32,910 --> 00:01:33,950 досягнуті. 45 00:01:33,950 --> 00:01:36,450 Так що, якщо я шукаю числа 9, я б 46 00:01:36,450 --> 00:01:39,340 дотримуйтесь покажчики від вузла до вузла, 47 00:01:39,340 --> 00:01:41,350 перевірки, чи є значення кожного вузла 48 00:01:41,350 --> 00:01:42,584 дорівнює 9. 49 00:01:42,584 --> 00:01:46,303 Таким чином, в гіршому випадку, подивитися це 50 00:01:46,303 --> 00:01:48,400 O (N), яке далеко не ефективними. 51 00:01:49,690 --> 00:01:51,630 Чи можемо ми зробити краще, ніж O (N) в той же час 52 00:01:51,630 --> 00:01:53,470 дозволяє наша структура даних рости протягом 53 00:01:53,470 --> 00:01:54,560 раз? 54 00:01:54,560 --> 00:01:56,810 Хеш-таблиці запропонувати рішення. 55 00:01:56,810 --> 00:01:58,730 Використовуються Хеш-таблиці, коли швидкий 56 00:01:58,730 --> 00:02:00,820 вставки, видалення та пошуку з 57 00:02:00,820 --> 00:02:01,910 елементи є пріоритетним. 58 00:02:01,910 --> 00:02:05,500 У теорії, вставка, видалення і пошук 59 00:02:05,500 --> 00:02:07,275 може навіть бути досягнуто в постійній 60 00:02:07,275 --> 00:02:08,890 Час. 61 00:02:08,890 --> 00:02:11,120 Отже, що ж являє собою хеш-таблицю в будь-якому випадку? 62 00:02:11,120 --> 00:02:13,170 Хеш-таблиця просто масив у поєднанні 63 00:02:13,170 --> 00:02:14,940 з функцією, яку ми будемо називати хеш 64 00:02:14,940 --> 00:02:15,440 функція. 65 00:02:16,440 --> 00:02:18,610 Хеш-функція приймає частина даних 66 00:02:18,610 --> 00:02:20,778 в якості вхідних даних, ми будемо називати це ключовий, і 67 00:02:20,778 --> 00:02:23,700 виводить ціле число, зазвичай званий 68 00:02:23,700 --> 00:02:24,895 в якості хеш-значення. 69 00:02:24,895 --> 00:02:28,810 Значення хеш-карти наш ключ до 70 00:02:28,810 --> 00:02:30,840 певний індекс в хеш-таблиці. 71 00:02:32,080 --> 00:02:34,330 Ви б спочатку використовувати хеш-функцію для 72 00:02:34,330 --> 00:02:36,410 визначити, де в хеш-таблиці, щоб 73 00:02:36,410 --> 00:02:38,430 зберігати заданий ключ. 74 00:02:38,430 --> 00:02:41,030 Пізніше, ви б використовувати той же хеш-функцію 75 00:02:41,030 --> 00:02:42,950 щоб визначити, де в хеш-таблиці, щоб 76 00:02:42,950 --> 00:02:45,010 пошук для даного ключа. 77 00:02:45,010 --> 00:02:47,190 З цієї причини, важливо, що хеш 78 00:02:47,190 --> 00:02:49,840 функція поводиться послідовно і виходи 79 00:02:49,840 --> 00:02:53,130 те ж значення хеша для однакових ключів. 80 00:02:53,130 --> 00:02:54,970 Знайте, що хеш-таблиці може бути використаний для 81 00:02:54,970 --> 00:02:56,310 зберігати дані всіх типів. 82 00:02:56,310 --> 00:02:58,330 Але спростити речі, ми зосередимося на 83 00:02:58,330 --> 00:02:59,830 Струни для тепер. 84 00:02:59,830 --> 00:03:01,630 Ось простий хеш-функція для рядків. 85 00:03:03,570 --> 00:03:05,590 Це хеш-функція обчислює хеш 86 00:03:05,590 --> 00:03:07,410 функція, заснована на першій букві 87 00:03:07,410 --> 00:03:07,910 ключ. 88 00:03:09,090 --> 00:03:11,300 "Яблуко" починається з букви "А", так що це 89 00:03:11,300 --> 00:03:13,200 зіставляється з індексом 0 в хеш-таблиці. 90 00:03:14,270 --> 00:03:17,402 Крім того, "банан" зіставляється з індексом 1, 91 00:03:17,402 --> 00:03:19,829 і "кішка" зіставляється з індексом 2. 92 00:03:21,750 --> 00:03:23,790 Якщо друг запитує, якщо слово "собака" знаходиться в 93 00:03:23,790 --> 00:03:26,150 таблиця, ми будемо вхідний "собака" в хеш 94 00:03:26,150 --> 00:03:28,390 Функція, яка буде виводити значення хеш-функції 95 00:03:28,390 --> 00:03:29,790 3. 96 00:03:29,790 --> 00:03:33,150 С "собака" не зберігається з індексом 3, ми 97 00:03:33,150 --> 00:03:35,330 Можна з упевненістю сказати, що "собака» не 98 00:03:35,330 --> 00:03:36,340 в таблиці, 99 00:03:36,340 --> 00:03:38,260 хоча ми тільки перевірили одне з 100 00:03:38,260 --> 00:03:40,120 хеш 26 індексів таблиці. 101 00:03:42,170 --> 00:03:44,280 Час кидати ключ в речах. 102 00:03:44,280 --> 00:03:46,130 Що робити, якщо ми хочемо зберегти "мурашки" в 103 00:03:46,130 --> 00:03:47,820 таблиця, а? 104 00:03:47,820 --> 00:03:51,730 "Муравей" хеши для індексу 0, так само, як "яблуко" зробив. 105 00:03:51,730 --> 00:03:53,890 Це є прикладом зіткнення, 106 00:03:53,890 --> 00:03:56,419 Результатом двох ключів хеширования, щоб те ж саме 107 00:03:56,419 --> 00:03:57,080 індекс. 108 00:03:58,140 --> 00:04:00,040 Навіть якщо ваш хеш-таблиці більше, ніж 109 00:04:00,040 --> 00:04:01,980 встановити Ваші дані, і ви вибрали хороший 110 00:04:01,980 --> 00:04:03,060 хеш-функція, 111 00:04:03,060 --> 00:04:04,560 Ви все ще потрібен план для боротьби з 112 00:04:04,560 --> 00:04:06,420 зіткнення, якщо і коли вони виникають. 113 00:04:07,440 --> 00:04:09,810 Давайте обговоримо плюси і мінуси двох 114 00:04:09,810 --> 00:04:12,360 загальні методи для вирішення колізій: 115 00:04:12,360 --> 00:04:15,230 лінійна зондування і окремий ланцюжка. 116 00:04:15,230 --> 00:04:17,430 З лінійним зондуванням, якщо ключ хеши для 117 00:04:17,430 --> 00:04:19,340 аналогічний показник, як раніше збережені 118 00:04:19,340 --> 00:04:21,840 ключ, йому присвоюється наступний доступний 119 00:04:21,840 --> 00:04:22,862 слот в таблиці. 120 00:04:22,862 --> 00:04:27,353 Так, "мураха" тепер зберігається з індексом 3, так як 121 00:04:27,353 --> 00:04:30,850 індекси 0, 1, і 2 вже були у використанні. 122 00:04:32,780 --> 00:04:34,610 І якщо ми намагаємося зберегти третє слово, що 123 00:04:34,610 --> 00:04:36,410 починається з букви "А", він призначається 124 00:04:36,410 --> 00:04:41,263 індексувати 4, так як індекси 0, 1, 2 і 3 125 00:04:41,263 --> 00:04:42,530 повні. 126 00:04:42,530 --> 00:04:44,300 Як ви можете бачити навіть з цього простого 127 00:04:44,300 --> 00:04:46,580 Наприклад, як тільки виникає колізія, вам 128 00:04:46,580 --> 00:04:48,400 значно збільшити шанси того, що 129 00:04:48,400 --> 00:04:50,370 другий зіткнення будуть відбуватися в той же самий 130 00:04:50,370 --> 00:04:51,630 площу. 131 00:04:51,630 --> 00:04:53,530 Це називається кластеризації, і це 132 00:04:53,530 --> 00:04:56,200 Серйозним недоліком до лінійних зондування. 133 00:04:56,200 --> 00:04:59,240 Крім того, в гіршому випадку вставки, видалення, 134 00:04:59,240 --> 00:05:02,008 і раз підстановки вже передані O (N), 135 00:05:02,008 --> 00:05:04,200 як наступного вільний слот може мати 136 00:05:04,200 --> 00:05:06,225 потенційно був останнім слот в таблиці. 137 00:05:06,225 --> 00:05:09,210 Може бути, окремі ланцюжки запропонує більш 138 00:05:09,210 --> 00:05:10,220 привабливим рішенням. 139 00:05:10,220 --> 00:05:13,060 В окремій моделі цепочечном хеш 140 00:05:13,060 --> 00:05:14,930 таблиця насправді масив покажчиків на 141 00:05:14,930 --> 00:05:16,220 зв'язані списки. 142 00:05:16,220 --> 00:05:18,350 При виникненні зіткнень, ключ може бути 143 00:05:18,350 --> 00:05:20,760 вставляється в постійному час на чолі 144 00:05:20,760 --> 00:05:22,270 відповідна зв'язаний список. 145 00:05:23,420 --> 00:05:25,310 Що відбувається зараз, коли ми шукаємо "яблуко" 146 00:05:25,310 --> 00:05:26,900 в хеш-таблиці? 147 00:05:26,900 --> 00:05:28,940 У гіршому випадку, ми повинні пройти 148 00:05:28,940 --> 00:05:32,530 Весь зв'язаний список, починаючи з індексу 0. 149 00:05:32,530 --> 00:05:34,210 Найгірший час пошуку для хеш 150 00:05:34,210 --> 00:05:35,890 таблиця, що використовує роздільного зв'язування є 151 00:05:35,890 --> 00:05:38,580 Тому О (п / к), де до 152 00:05:38,580 --> 00:05:39,687 розмір хеш-таблиці. 153 00:05:39,687 --> 00:05:42,940 Секундочку, к-постійна. 154 00:05:42,940 --> 00:05:46,280 Так O (п / к) насправді просто О (п), 155 00:05:46,280 --> 00:05:47,940 який був найгірший час пошуку для 156 00:05:47,940 --> 00:05:49,320 зв'язаний список. 157 00:05:49,320 --> 00:05:50,770 Чи справді ми пройшли через все 158 00:05:50,770 --> 00:05:52,370 Біда дізнатися про хеш-таблиці 159 00:05:52,370 --> 00:05:54,927 тільки в кінцевому підсумку туди, де ми почали? 160 00:05:54,927 --> 00:05:56,975 Це може бути у випадку з теоретичної 161 00:05:56,975 --> 00:05:59,087 перспектива, але в реальному світі, 162 00:05:59,087 --> 00:06:01,199 О (п / к) може бути величезне поліпшення в порівнянні 163 00:06:01,199 --> 00:06:03,257 O (N). 164 00:06:03,257 --> 00:06:05,687 Подумайте про це так: вважати до 165 00:06:05,687 --> 00:06:08,360 10 - ви б віддали перевагу чекати 100 секунд 166 00:06:08,360 --> 00:06:11,076 або 100 / к? 167 00:06:11,076 --> 00:06:13,252 10 секунд від Microsoft Word, щоб закінчити 168 00:06:13,252 --> 00:06:15,608 перевірка орфографії документа. 169 00:06:15,608 --> 00:06:17,368 Як ви тільки що бачили, вирішення конфліктів 170 00:06:17,368 --> 00:06:19,018 тягне за собою один вид лінійного пошуку або 171 00:06:19,018 --> 00:06:20,558 другий, що уповільнює роботу 172 00:06:20,558 --> 00:06:23,280 значно. 173 00:06:23,280 --> 00:06:25,470 Таким чином, ви хочете, щоб вибрати хеш 174 00:06:25,470 --> 00:06:27,470 функція, яка зводить до мінімуму ймовірність 175 00:06:27,470 --> 00:06:29,170 зіткнення, що відбуваються в першу чергу. 176 00:06:30,540 --> 00:06:32,120 Ось деякі властивості хорошою хеш 177 00:06:32,120 --> 00:06:33,400 функції, мати на увазі. 178 00:06:34,610 --> 00:06:36,590 Хороший хеш-функція повинна використовувати 179 00:06:36,590 --> 00:06:38,830 вся інформація, надана даного ключа 180 00:06:38,830 --> 00:06:40,890 щоб максимізувати кількість 181 00:06:40,890 --> 00:06:42,960 Можливі значення хеш-функції. 182 00:06:42,960 --> 00:06:45,540 Наприклад, якщо у нас було два рядки, "кішка" 183 00:06:45,540 --> 00:06:47,980 і "Гусениця", ми хотіли б, щоб вони хеш 184 00:06:47,980 --> 00:06:50,190 в різні місця на столі. 185 00:06:50,190 --> 00:06:52,410 Якщо хеш-функція тільки врахували 186 00:06:52,410 --> 00:06:54,860 перший раз, два, або навіть три букви 187 00:06:54,860 --> 00:06:57,290 з рядків, зіткнення відбудеться, 188 00:06:57,290 --> 00:06:58,970 оскільки обидва слова починаються з тієї ж 189 00:06:58,970 --> 00:06:59,560 три букви. 190 00:07:01,110 --> 00:07:03,100 Значення хеш слід рівномірно 191 00:07:03,100 --> 00:07:04,790 через хеш-таблиці. 192 00:07:04,790 --> 00:07:06,300 Це дозволить скоротити довжину пов'язані 193 00:07:06,300 --> 00:07:08,050 списки повинні зіткнення відбуваються. 194 00:07:09,390 --> 00:07:11,490 Це також хороший знак, якщо ваш хеш-значення 195 00:07:11,490 --> 00:07:13,600 здатний генерувати дуже різні 196 00:07:13,600 --> 00:07:15,660 хеш значення для аналогічних ключів, 197 00:07:15,660 --> 00:07:17,250 роблячи зіткнень набагато рідше. 198 00:07:18,420 --> 00:07:21,110 Наша мета якнайшвидшого вставки, видалення, 199 00:07:21,110 --> 00:07:22,100 і пошук. 200 00:07:22,100 --> 00:07:24,060 Хеш-функція відіграє важливу роль в 201 00:07:24,060 --> 00:07:25,520 кожен з цих процесів і буде 202 00:07:25,520 --> 00:07:26,735 називається дуже часто. 203 00:07:26,735 --> 00:07:29,620 Таким чином, переконайтеся, що він працює тільки дуже 204 00:07:29,620 --> 00:07:32,160 Просто, швидко операцій, щоб мінімізувати пробіг 205 00:07:32,160 --> 00:07:33,360 Час. 206 00:07:33,360 --> 00:07:34,560 Я сподіваюся, вам сподобалося це резюме 207 00:07:34,560 --> 00:07:36,540 введення на хеши. 208 00:07:36,540 --> 00:07:41,189 Мене звуть Лорен, і це CS50.