Мы уже знаем, как искать элементы в массиве — перебором за O(n), или бинарным поиском за O(log n) если массив отсортирован. Деревья дали нам O(log n) даже без сортировки. Неплохо. Но есть задачи, где и это медленно.

Представьте: вы пишете систему для интернет-магазина. Каждую секунду приходят тысячи запросов вида «есть ли товар с артикулом SKU-48291 на складе?». Товаров на складе — миллион. Бинарный поиск сделает около 20 сравнений. Умножьте на тысячи запросов в секунду — и сервер начнёт задыхаться. Хочется что-то принципиально быстрее.

А что если поиск занимал бы ровно один шаг, вне зависимости от размера склада? Не 20, не 10 — а один. Это и есть идея хеш-таблицы. А хеш-функция — ключевой механизм, который делает это возможным.

Чтобы оценить разницу — вот сравнение временной сложности операций поиска:

Массив без сортировки: O(n) — перебираем каждый элемент.

Отсортированный массив, бинарный поиск: O(log n) — делим пространство поиска пополам.

Бинарное дерево поиска: O(log n) в среднем.

Хеш-таблица: O(1) в среднем — прямой переход по индексу. Идея простая: возьмём обычный массив фиксированного размера — скажем, 1000 ячеек. Нам нужно хранить пары «ключ — значение»: артикул товара → количество на складе. Если бы ключи были числами от 0 до 999, всё было бы просто: кладём значение в ячейку с нужным номером, достаём за O(1). Но ключи — произвольные строки вроде "SKU-48291". Как превратить строку в индекс от 0 до 999?

Именно это и делает хеш-функция.

Посмотрим на самый простой пример. Строку можно «свернуть» в число, просуммировав коды её символов:

// Очень упрощённая хеш-функция для строки
int SimpleHash(string key)
{
    int sum = 0;
    foreach (char c in key)
        sum += (int)c;
    return sum;
}

string sku = "SKU-48291";
int hashCode = SimpleHash(sku);      // например, 756
int index = hashCode % 1000;         // индекс в массиве: 756

Строка "SKU-48291" превращается в число 756. Оператор % (остаток от деления) гарантирует, что результат не выйдет за границы массива — сколько бы большим ни было исходное число, после % 1000 получим значение от 0 до 999.

Запись: кладём значение в ячейку 756. Чтение: снова вычисляем хеш от ключа, получаем 756, идём прямо туда. Никакого перебора — один шаг.

Обратите внимание на то, что происходит при чтении: мы не храним «где лежит SKU-48291». Мы просто снова вычисляем хеш — и всегда получаем тот же самый индекс. Вот почему детерминированность хеш-функции так важна: если при записи получили 756, при чтении тоже должны получить 756, а не 912.

Вот и вся суть: ключ → хеш-функция → индекс → массив. Запись и чтение за O(1). Теперь посмотрим, как это работает в реальном C#. Каждый тип данных в .NET умеет вычислять свой хеш-код — через метод GetHashCode(), который унаследован от базового класса object.

string username = "alice";
int hashCode = username.GetHashCode();
Console.WriteLine(hashCode);         // например, -1558733584
Console.WriteLine(hashCode % 1000);  // индекс: 416 (или отрицательный!)

Конкретное число зависит от реализации и версии .NET — не удивляйтесь, если у вас будет другое. Важно другое: метод есть у любого объекта — строки, числа, пользовательского класса.

Что делает хорошую хеш-функцию? У неё три ключевых свойства.

Детерминированность. Один и тот же ключ всегда даёт одно и то же число. Если сегодня "alice" даёт 416, завтра она тоже должна дать 416 — иначе мы просто не найдём, куда положили данные. Это единственное жёсткое требование: нарушить его — значит сломать всю структуру.

Равномерное распределение. Разные ключи должны давать разные индексы, равномерно разбросанные по всему массиву. Если все 10 000 товаров окажутся в ячейке 0, а остальные 999 будут пустыми — никакой пользы от хеш-таблицы нет. Наш простой «сумма кодов символов» страдает именно этим: строки "abc" и "cab" и "bca" дают одинаковую сумму и попадают в одну ячейку. Реальные хеш-функции учитывают позицию символа, чтобы этого избежать.

Скорость. Вычисление должно быть быстрым — константным O(1) или хотя бы O(длины ключа). Смысл теряется, если сама хеш-функция медленнее линейного поиска. Хорошая реализация обрабатывает строку за микросекунды.

Теперь посмотрим, как всё это выглядит в реальной задаче. Классический пример — подсчёт слов в тексте. Нужно для каждого слова хранить, сколько раз оно встречается.

string text = "кот сел на кот и кот ушёл";
string[] words = text.Split(' ');

Dictionary<string, int> wordCount = new Dictionary<string, int>();

foreach (string word in words)
{
    if (wordCount.ContainsKey(word))
        wordCount[word]++;
    else
        wordCount[word] = 1;
}

foreach (var pair in wordCount)
    Console.WriteLine($"{pair.Key}: {pair.Value}");

Вывод:

кот: 3
сел: 1
на: 1
и: 1
ушёл: 1

Dictionary<string, int> в C# — это и есть хеш-таблица под капотом. Когда вы пишете wordCount["кот"] = 3, Dictionary вычисляет хеш от строки "кот", находит нужный «бакет» (ячейку) и кладёт туда пару ключ-значение. Поиск по ключу работает точно так же — за O(1).

Хеш-функция — функция, которая превращает ключ произвольного типа в целое число (хеш-код). Хеш-код используется как индекс в массиве, что позволяет находить элементы за O(1).

Хеш-таблица работает так: при записи вычисляем index = Math.Abs(key.GetHashCode()) % arraySize и кладём значение по этому индексу. При чтении — снова вычисляем тот же индекс и идём прямо туда.

Три свойства хорошей хеш-функции: детерминированность (один ключ — всегда один хеш), равномерное распределение (разные ключи — разные индексы), скорость (O(1)).

Коллизия — ситуация, когда два разных ключа дают одинаковый индекс. Это неизбежно при достаточном количестве ключей — из-за парадокса дня рождения. Хеш-таблицы умеют обрабатывать коллизии (следующий урок).

В C# метод GetHashCode() есть у любого объекта. Dictionary<K, V> — стандартная хеш-таблица в .NET: запись и поиск по ключу работают за O(1) в среднем случае.

Не путайте криптографические хеш-функции (MD5, SHA) с хеш-функциями для структур данных: для паролей нужны специальные медленные алгоритмы — bcrypt, Argon2, PBKDF2.