Глосарій

Хеш-таблиця

Хеш-таблиця — структура даних, що забезпечує доступ за ключем за O(1) у середньому. Ключ передається через хеш-функцію, результат вказує на «кошик» (bucket), де зберігається значення. Асоціативні масиви в PHP і dict у Python — хеш-таблиці.

Колізії

Різні ключі можуть дати однаковий хеш — це колізія. Вирішується двома способами:

Chaining — кожен bucket — список елементів з однаковим хешем
Open addressing — при колізії шукається наступний вільний bucket

Load factor

Співвідношення кількості елементів до кількості buckets. При перевищенні порогу (зазвичай 0.75) — рехешування (збільшення таблиці і перерозподіл елементів). Дороге, але рідке.

Vs дерево пошуку

Hash table: O(1) доступ, але немає порядку. BST: O(log n) доступ, але елементи відсортовані. Вибір залежить від потреби в сортуванні.