У цьому підручнику ви дізнаєтесь, що таке хешування.
Хешування - це техніка відображення великого набору довільних даних у табличні індекси за допомогою хеш-функції. Це метод представлення словників для великих наборів даних.
Це дозволяє здійснювати пошук, оновлення та пошук за постійний час, тобто O(1).
Чому потрібен хешування?
Після зберігання великої кількості даних нам потрібно виконати різні операції з цими даними. Пошук даних неминучий для наборів даних. Лінійний пошук і двійковий пошук виконують пошук / пошук із часовою складністю O(n)та O(log n)відповідно. Зі збільшенням розміру набору даних ці складності також стають значно більшими, що є неприйнятним.
Нам потрібна техніка, яка не залежить від обсягу даних. Хешування дозволяє здійснювати пошук у постійний час, тобто O(1).
Хеш-функція
Хеш-функція використовується для відображення кожного елемента набору даних до індексів у таблиці.
Щоб отримати докладнішу інформацію про хеш-таблицю, методи розв’язання зіткнень та хеш-функції, відвідайте Хеш-таблицю.
