Що таке колізія в хеш-таблиці? Чому вони неминучі?

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

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

Приклад:

javascript

hash("dog") % 10 = 3
hash("cat") % 10 = 3

Обидва ключі будуть записані в кошик №3 - це і є колізія.

Чому вони неминучі:

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

Важливо: Колізії - це нормальне явище, їх неможливо повністю усунути. Головне - вміти ефективно з ними працювати (через ланцюжки чи відкриту адресацію), щоб при великій кількості елементів таблиця все одно зберігала швидкість доступу, близьку до O(1).

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

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

Premium

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