[ШУМУ].
Перед зануренням в хеш-таблиць, давайте
спочатку розглянемо плюси і мінуси деяких
прості структури даних, починаючи з
масиви.
Нагадаємо, що масиви дозволяють нам зберігати
елементи одного типу даних
безперервно в пам'яті.
Оскільки кожен елемент пов'язаний з
індекс, або місце,
у нас є випадковий доступ до всіх
елементи масиву.
Іншими словами, ми можемо отримати доступ до будь-якого елементу
в одному кроці від індексації в
масивом.
Це велика справа, тому що алгоритми
як бінарного пошуку залежать від випадкових
доступу.
Недоліком масивів є те, що їх розмір
фіксоване.
Оскільки дані масиви магазин безперервно в
пам'яті, необхідно вказати розмір масиву
при оголошенні масиву.
Ви ефективно питаючи операційної
Система зарезервувати відповідну кількість
пам'яті для елементів масиву.
Там немає ніякої гарантії, що більше пам'яті,
поруч з вашого масиву, будуть доступні
для подальшого використання.
Так масиви не можуть легко зростати.
Нагадаємо, що ми також дізналися про пов'язані
списки, які можуть рости, тому що їх
елементи не є суміжними в пам'яті.
Кожен вузол у зв'язаному списку містить
елемент, який ми хочемо зберігати, а також
покажчик на наступного елемента в
список.
На жаль, ціна, яку ми заплатили за
динамічний розмір довільний доступ до
елементи.
Для того, щоб отримати доступ певний елемент,
необхідно пройти по всьому
список, поки шуканий елемент не є
досягнуті.
Так що, якщо я шукаю числа 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.