Хешування - Problem Solving with Algorithms and Data Structures
У попередніх розділах ми змогли вдосконалити наші алгоритми пошуку, використовуючи переваги інформації про те, де елементи зберігаються один до одного. Наприклад, знаючи, що список упорядкований, ми можемо шукати логарифмічний час, використовуючи бінарний алгоритм. У цьому розділі ми спробуємо піти ще крок далі: побудувати таку структуру даних, у якій можна буде здійснювати пошук за час \(O(1)\) . Цю концепцію називаютьхешуванням.
Тепер нам треба знати більше, ніж просто розташування елемента, коли ми шукаємо його в колекції. Якщо кожен елемент знаходиться там, де йому слід бути, то пошук може використовувати лише порівняння для виявлення присутності шуканого. Однак далі ми побачимо, що це, як правило, не єдиний вихід.
Хеш-таблиця - це колекція елементів, які зберігаються таким чином, щоб пізніше їх було легко знайти. Кожна позиція в хеш-таблиці (часто званаслотом ) може містити власне елемент і ціле число, що починається з нуля. Наприклад, у нас є слот 0, слот 1, слот 2 і таке інше. Спочатку хеш-таблиця не містить елементів, тому кожен з них порожній. Ми можемо зробити реалізацію хеш-таблиці, використовуючи список, у якому кожен елемент ініціалізований спеціальним значенням Python None. Малюнок 4 демонструє хеш-таблицю розміром \(m=11\). Інакше кажучи, у ній є \(m\) слотів, пронумерованих від 0 до 10.
Малюнок 4: Хеш-таблиця з 11 порожніми слотами
Зв'язок між елементом і слотом, який він кладеться, називаєтьсяхеш-функцією. Вона приймає будь-який елемент із колекції та повертає ціле число з діапазону імен слотів (від 0 до \(m-1\) ). Припустимо, що ми маємо набір цілих чисел 54, 26, 93, 17, 77 і 31. Нашаперша хеш-функція, іноді звана "методом залишків", просто бере елемент і ділить його на розмір таблиці, повертаючи залишок як хеш-значення ( \(h(item)=item \% 11\) ). У таблиці 4 представлені всі хеш-значення чисел нашого прикладу. Зверніть увагу: метод залишків (модульна арифметика) зазвичай присутня у тій чи іншій формі у всіх хеш-функціях, оскільки результат повинен лежати в діапазоні імен слотів.
Оскільки хеш-значення можуть бути пораховані, ми можемо вставити кожен елемент у хеш-таблицю на певне місце, як це показано на малюнку 5. Зверніть увагу, що тепер зайнято 6 із 11 слотів. Це називаєтьсяфактором завантаження і зазвичай позначається \(\lambda = \frac \). У цьому прикладі \(\lambda = \frac \).
Малюнок 5: Хеш-таблиця із шістьма елементами
Тепер, коли ми хочемо знайти елемент, ми просто використовуємо хеш-функцію, щоб обчислити ім'я слота елемента, а потім перевірити по таблиці його наявність. Ця операція пошуку має \(O(1)\), оскільки на обчислення хеш-значення потрібен константний час, як і на перехід за знайденим індексом. Якщо все знаходиться там, де йому належить, ми отримуємо алгоритм пошуку за константний час.
Можливо, ви вже помітили, що така техніка працює тільки, якщо кожен елемент відображається на унікальну позицію в хеш-таблиці. Наприклад, якщо наступним у нашій колекції буде елемент 44, він матиме хеш-значення 0 ( \(44 \% 11 == 0\) ). Оскільки 77 теж має хеш-значення 0, то ми маємо проблеми. Відповідно до хеш-функції два або більше елементів повинні мати один слот. Це називаєтьсяколізією (іноді “зіткненням”). Очевидно, що колізії створюють проблеми для техніки хешування. Пізніше ми обговоримо їх у деталях.
Хеш-функції¶
Для заданої колекціїелементів хеш-функція, що зв'язує кожен із них з унікальним слотом, називаєтьсяідеальною хеш-функцією. Якщо ми знаємо, що жоден елемент колекції ніколи не зміниться, можливо створити ідеальну хеш-функцію (див. вправи, щоб дізнатися про це більше). На жаль, для довільного набору елементів немає систематичного способу сконструювати ідеальну хеш-функцію. На щастя, для ефективної роботи вона нам і не потрібна.
Наша мета: створити хеш-функцію, яка б мінімізувала кількість колізій, легко вважалася і рівномірно розподіляла елементи в хеш-таблиці. Існує кілька поширених способів розширити найпростіший метод залишків. Розглянемо деякі з них.
Інша числова техніка до створення хеш-функцій називаєтьсяметодом середніх квадратів. Спочатку значення елемента зводиться в квадрат, а потім з цифр, що вийшли в результаті, виділяється деяка порція. Наприклад, якщо елемент дорівнює 44, то ми насамперед обчислимо \(44 ^ = 1,936\) . Виділивши дві середні цифри (93) і виконавши крок отримання залишку, ми отримаємо 5 ((93% 11)). Таблиця 5 показує елементи, до яких застосували обидва методи: залишків та середніх квадратів. Переконайтеся, що знаєте, як ці значення були отримані.