🗝 Хеш‑таблицы — быстрый поиск по ключу без магии

🗝 Хеш‑таблицы — быстрый поиск по ключу без магии

Самурай приходит в додзё, называет своё имя — хранитель сразу выдаёт катану из нужной ячейки. Как он нашёл меч в огромной оружейной за долю секунды? Ответ — хеш‑таблица.

🔔 Выпуск выходит каждый вторник. Делитесь постом, чтобы путь код‑самурая рос!

⸻

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 #кодСамурая