Skip to main content

Що робить операція модуль (%) при хешуванні? Як вона пов'язана з індексами?

Структури данихJunior~1 хв читання
Запропонувати правку

Операція модуль (%) при хешуванні використовується для того, щоб перетворити велике значення хешу на допустимий індекс масиву, де зберігаються дані хеш-таблиці.

Як це працює

  1. Хеш-функція повертає ціле число, іноді дуже велике.
  2. Таблиця має обмежений розмір N (наприклад, 100 комірок).
  3. Щоб "вписати" хеш у діапазон індексів [0 ... N-1], обчислюють:
javascript
index = hash(key) % N
  1. У результаті виходить індекс - позиція в масиві, куди буде поміщено елемент.

Приклад

javascript
hash("dog") = 123456 N = 10 index = 123456 % 10 = 6

Отже, елемент з ключем "dog" потрапить у комірку №6.

Чому саме модуль

  • % дає рівномірний розподіл по діапазону індексів;
  • гарантує, що індекс ніколи не вийде за межі масиву.

Підсумок

Операція модуль зв'язує "абстрактний" хеш із конкретним місцем зберігання в таблиці: вона робить хеш реальним індексом масиву, де лежать дані.

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку