Хеш-таблица
Хеш-таблица — структура, которая находит значение по ключу почти мгновенно, без перебора. Это теоретическая основа HashMap/HashSet в Java (подробное устройство — в теме «Устройство HashMap»).
Идея простая: ключ через хеш-функцию превращается в число — индекс ячейки массива, где хранится значение:
"Артур" → hash() → 37 → ячейка [37] → значениеПоэтому map.get("Артур") не перебирает все записи — он сразу вычисляет, в какой ячейке искать.
Копнуть глубже
Хорошая хеш-функция:
- Детерминирована — один и тот же ключ всегда даёт один и тот же хеш;
- Равномерно распределяет ключи по ячейкам — иначе все попадут в одну корзину, и преимущество в скорости исчезнет;
- Быстро вычисляется — иначе теряется смысл экономии времени на поиске.
Коллизии неизбежны. Разных ключей больше, чем возможных ячеек — рано или поздно два разных ключа получат один хеш. Решают это по-разному: цепочками (список значений в одной ячейке — так делает HashMap) или открытой адресацией (ищем следующую свободную ячейку).
🎤 Закрыл тему, если можешь объяснить:
• идею хеш-таблицы — как ключ превращается в индекс ячейки;
• что такое коллизия и почему она неизбежна (если дошёл до 2-го слоя).
• что такое коллизия и почему она неизбежна (если дошёл до 2-го слоя).