Як хеш-таблиця зберігає дані?

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

#Покроково

1. При додаванні елемента обчислюється хеш ключа:

де N - розмір масиву. 2. Елемент розміщується в комірці з цим індексом. 3. При пошуку або видаленні використовується та сама хеш-функція: за ключем обчислюється індекс, і доступ до елемента відбувається напряму.

#Приклад

Нехай розмір таблиці - 10, і hash("dog") = 23. Тоді 23 % 10 = 3, і пара ("dog", "animal") зберігається в комірці №3.

#Якщо колізія (два ключі дають один індекс)

• при ланцюжках (chaining) у комірці зберігається список усіх елементів з цим індексом;
• при відкритій адресації таблиця шукає наступну вільну комірку.

Таким чином, хеш-таблиця - це по суті масив + хеш-функція + спосіб обробки колізій, що дозволяє швидко знаходити дані за ключем без повного перебору.