Хешування відноситься до процесу генерування вихідних даних фіксованого розміру з вхідних даних змінного розміру за допомогою математичних формул, відомих як хеш-функції. Ця техніка визначає індекс або розташування для зберігання елемента в структурі даних.

avl обертання дерева

Необхідність структури хеш-даних

Обсяг даних в Інтернеті зростає в геометричній прогресії щодня, що ускладнює їх ефективне зберігання. У повсякденному програмуванні цей обсяг даних може бути не таким великим, але все одно їх потрібно зберігати, отримувати доступ і обробляти легко й ефективно. Дуже поширеною структурою даних, яка використовується для такої мети, є структура даних Array.

Тепер виникає питання, якщо Array вже був там, яка була потреба в новій структурі даних! Відповідь на це питання криється в слові ефективність. Хоча збереження в Array займає О(1) час, пошук у ньому займає мінімум O(log n) час. Цей час здається малим, але для великого набору даних це може спричинити багато проблем, а це, у свою чергу, робить структуру даних масиву неефективною.

Отже, зараз ми шукаємо структуру даних, яка може зберігати дані та шукати в них у постійному часі, тобто в О(1) час. Ось як у гру вступила структура даних хешування. З появою структури даних Hash тепер можна легко зберігати дані в постійному часі та отримувати їх також у постійному часі.

Компоненти хешування

Існує в основному три компоненти хешування:

1. ключ: А ключ може бути будь-яким рядком або цілим числом, яке подається як вхідні дані для хеш-функції. Техніка, яка визначає індекс або розташування для зберігання елемента в структурі даних.
2. Хеш-функція: The хеш-функція отримує вхідний ключ і повертає індекс елемента в масиві, що називається хеш-таблицею. Індекс відомий як хеш-індекс .
3. Хеш-таблиця: Хеш-таблиця — це структура даних, яка зіставляє ключі зі значеннями за допомогою спеціальної функції, яка називається хеш-функцією. Хеш зберігає дані в асоціативному вигляді в масиві, де кожне значення даних має власний унікальний індекс.

Компоненти хешування

Що таке зіткнення?

Процес хешування генерує невелике число для великого ключа, тому існує ймовірність того, що два ключі можуть давати однакове значення. Ситуація, коли щойно вставлений ключ зіставляється з уже зайнятим, і його потрібно обробляти за допомогою певної технології обробки зіткнень.

Зіткнення в хешуванні

суміжні кути

Переваги хешування в структурах даних

• Підтримка ключ-значення: Хешування ідеально підходить для реалізації структур даних ключ-значення.
• Швидкий пошук даних: Хешування дозволяє отримати швидкий доступ до елементів із постійною складністю часу.
• Ефективність: Операції вставки, видалення та пошуку дуже ефективні.
• Зменшення використання пам'яті: Хешування потребує менше пам’яті, оскільки воно виділяє фіксований простір для зберігання елементів.
• Масштабованість: Хешування добре працює з великими наборами даних, зберігаючи постійний час доступу.
• Безпека та шифрування: Хешування є важливим для безпечного зберігання даних і перевірки цілісності.

Щоб дізнатися більше про хешування, зверніться до Вступ до хешування – навчальні посібники зі структури даних і алгоритмів