🗝 Хеш‑таблицы — быстрый поиск по ключу без магии
Самурай приходит в додзё, называет своё имя — хранитель сразу выдаёт катану из нужной ячейки. Как он нашёл меч в огромной оружейной за долю секунды? Ответ — хеш‑таблица.
🔔 Выпуск выходит каждый вторник. Делитесь постом, чтобы путь код‑самурая рос!
⸻
1. Что такое хеш‑функция
Берём ключ → запускаем быструю математическую функцию → получаем число‑индекс.
Ключи разных размеров (строки, числа) превращаем в фиксированное целое. Главное требование — быстро и примерно равномерно распределять ключи.
2. Как работает поиск O(1)
1. Вычислить индекс: index = hash(key) % N (N — длина внутреннего массива).
2. Перейти по указателю сразу к ячейке index.
3. Сравнить хранимый ключ с искомым: если совпал — возвращаем значение.
Важно: O(1) — среднее время. В крайних случаях (все ключи столкнулись) может вырасти до O(n), но при хорошей хеш‑функции это редкость.
3. Коллизии — когда два ключа падают в один индекс
Способы лечения:
• Цепочки (Chaining) — в ячейке храним список записей.
• Открытая адресация — ищем соседнюю свободную ячейку (линейное или квадратичное пробирование).
• Двойное хеширование — используем вторую функцию, если первая занята.
4. Простой пример на PHP (ассоц‑массив уже хеш‑таблица)
$userScores = [
'ryu' => 42,
'ken' => 39,
'akira' => 50,
];
// Чтение O(1)
$score = $userScores['ryu'];
Своя хеш‑таблица с цепочками
class HashTable {
private array $buckets;
public function __construct(private int $size = 8) {
$this->buckets = array_fill(0, $size, []);
}
private function hash(string $key): int {
return crc32($key) % $this->size; // простая хеш‑функция
}
public function put(string $key, mixed $value): void {
$i = $this->hash($key);
foreach ($this->buckets[$i] as &$pair) {
if ($pair[0] === $key) { $pair[1] = $value; return; }
}
$this->buckets[$i][] = [$key, $value];
}
public function get(string $key): mixed {
$i = $this->hash($key);
foreach ($this->buckets[$i] as $pair) {
if ($pair[0] === $key) return $pair[1];
}
return null; // not found
}
}
5. Плюсы и минусы
+ мгновенный доступ по ключу (среднее O(1))
+ гибкость ключей (строки, числа, UUID)
− нет упорядоченности, нельзя итерировать «в отсортированном виде»
− требует больше памяти (пустые ячейки, списки коллизий)
− нужно следить за load factor (> 0.75 — расширяем массив)
6. Мини‑чек‑лист: когда брать хеш‑таблицу?
• Нужно быстро искать, вставлять, удалять по ключу.
• Размер данных растёт — расширение массива дешевле, чем сортировка.
• Порядок элементов не важен.
• Память не в дефиците (или критичен именно доступ).
🌐 Практический кейс: фильтр дубликатов при импорте CSV
Приходит файл в 100 000 строк: user_id;email. Нужно загрузить пользователей, игнорируя дубликаты по email.Без хеш‑таблицы пришлось бы на каждый новый email делать in_array() по растущему списку (O(n²)).С хеш‑таблицей (ассоциативным массивом‑множество) проверяем наличие за O(1).
$seen = [];
foreach ($rows as $row) {
[$id, $email] = $row;
if (isset($seen[$email])) {
// уже импортировали — пропускаем
continue;
}
$seen[$email] = true; // mark
saveUser($id, $email);
}
PHP‑массив здесь и есть хеш‑таблица: ключ email прогоняется через встроенную хеш‑функцию, движок сразу знает, в какой «корзине» хранить метку. На практике такой приём ускоряет импорт с минут до секунд.
⸻
❓ Вопрос к читателям: какие неожиданные хеш‑функции встречали в проектах? Делитесь в комментариях!
#алгоритмы #хештаблица #php #кодСамурая
