Mediumhashtable
Что такое хеш-таблица и как обрабатывает коллизии?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Хеш-таблица — структура key → value через hash function: hash(key) → bucket index. Операции O(1) average, O(n) worst. Коллизии — разные ключи с одинаковым hash.
Методы разрешения коллизий:
- Chaining — каждый bucket это linked list (в Java 8+ — tree при длинной цепи);
- Open addressing (linear/quadratic probing, double hashing) — ищем следующий пустой слот; лучшая cache locality, но cluster problem;
- Cuckoo hashing — два hash functions, при коллизии выселяет существующий элемент; O(1) worst lookup.
# Пример: linear probing
bucket = (hash(key) + i) % size # i = 1, 2, 3 ...
# Quadratic probing
bucket = (hash(key) + i*i) % sizeLoad factor — элементов / размер массива; resize (rehash) при превышении (~0.7 для open addressing, 1.0 для chaining). Python dict — open addressing с pseudo-random probing; Java HashMap — chaining + treeify при длине ≥ 8.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.