Глоссарий

Хеш-таблица

Хеш-таблица — структура данных, обеспечивающая доступ по ключу за 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) доступ, но элементы отсортированы. Выбор зависит от необходимости сортировки.