Хеш-таблиці
Хешування — це техніка для унікальної ідентифікації конкретного об’єкта з групи подібних об’єктів.
Використання хешування в житті:
-
в університетах кожному студенту надається унікальний номер, за яким можна отримати інформацію про нього;
-
у бібліотеках кожна книга має власний номер, за яким можна знайти інформацію про неї. Наприклад, про її точне місце в бібліотеці, про користувачів, яким її було видано, тощо.
В обох прикладах студенти та книги були хешовані до унікального номера.
Припустимо, що у нас є об’єкт і ми хочемо призначити йому ключ (унікальний ідентифікатор), щоб полегшити пошук. Щоб зберегти пару «ключ — значення», можна використовувати простий масив, де ключі (цілі числа) використовувати як індекс для зберігання значень. Однак у випадках, коли ключі — великі й не можуть застосовуватися безпосередньо як індекс, слід використовувати хешування.
Під час хешування великі ключі перетворюються на маленькі за допомогою хеш-функцій. Потім значення зберігаються в структурі даних, що називається хеш-таблицею.
Ідея хешування полягає в рівномірному розподілі записів (пар «ключ — значення») у масиві. Кожному елементу призначається перетворений ключ. Використовуючи ключ, алгоритм (хеш-функція) обчислює індекс, який передбачає, де можна знайти або вставити запис.
Хешування реалізується у два етапи:
1. Елемент перетворюється на ціле число за допомогою хеш-функції. Цей елемент можна використовувати як індекс для зберігання вихідного елемента, який потрапляє в хеш-таблицю.
2. Елемент зберігається в хеш-таблиці, де його можна швидко отримати за допомогою хешованого ключа.
* Бренди та/або ресурси надаються за вибором партнера та не є закликом до купівлі/відвідування даних ресурсів, а зображуються лише з освітньою метою.