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

Итак, что пошло не так в нашей SimpleHashTable? Два разных ключа — скажем, "username" и "city" — могут дать один и тот же индекс. Это называется коллизией.

Вы можете подумать: «Ну ладно, просто сделаем таблицу побольше». Но даже с таблицей на миллион слотов вы получите коллизию раньше, чем ожидаете. Это хорошо объясняет парадокс дней рождения: в группе всего из 23 человек вероятность совпадения дней рождения превышает 50%. Аналогично — если заполнить хеш-таблицу хотя бы на 1–2%, коллизии уже практически гарантированы. Хеш-функции сжимают бесконечное пространство ключей в конечный массив, и столкновения просто неизбежны математически.

Значит, вопрос не «как избежать коллизий», а «как с ними справляться». Для этого придумали два принципиально разных подхода.

Метод цепочек

Первый подход — метод цепочек (separate chaining). Идея простая: каждый слот массива хранит не одно значение, а связный список. Если два ключа попали на один индекс — они оба живут в этом списке, друг за другом.

Представьте гардероб в театре. У каждого крючка (индекс) есть номерок. Если два человека сдали пальто на один крючок — вешаешь второе поверх первого и запоминаешь порядок. Ищешь — просто перебираешь цепочку на этом крючке.

На индексе 2 живут два элемента — они образуют цепочку. Поиск по ключу "city" пойдёт на индекс 2, а там пробежится по списку и найдёт нужный узел.

Напишем полноценную реализацию. Сначала узел связного списка:

class HashNode
{
    public string Key;
    public string Value;
    public HashNode Next; // следующий узел в цепочке

    public HashNode(string key, string value)
    {
        Key = key;
        Value = value;
    }
}

Теперь сама таблица:

class ChainingHashTable
{
    private HashNode[] buckets;
    private int capacity;
    private int count;

    public ChainingHashTable(int capacity = 16)
    {
        this.capacity = capacity;
        buckets = new HashNode[capacity];
    }

    private int GetIndex(string key) =>
        Math.Abs(key.GetHashCode()) % capacity;

    public void Put(string key, string value)
    {
        int index = GetIndex(key);
        HashNode current = buckets[index];

        // Ищем — вдруг ключ уже есть, тогда просто обновляем
        while (current != null)
        {
            if (current.Key == key)
            {
                current.Value = value;
                return;
            }
            current = current.Next;
        }

        // Ключа нет — добавляем в голову цепочки (O(1))
        var newNode = new HashNode(key, value) { Next = buckets[index] };
        buckets[index] = newNode;
        count++;
    }

    public string Get(string key)
    {
        int index = GetIndex(key);
        HashNode current = buckets[index];

        while (current != null)
        {
            if (current.Key == key)
                return current.Value;
            current = current.Next;
        }

        return null; // ключ не найден
    }
}

Разберём по шагам. При добавлении мы сначала идём по цепочке на нужном индексе — если ключ уже есть, просто обновляем значение. Если нет — вставляем новый узел в начало цепочки: это O(1), не нужно доходить до конца. При поиске — та же цепочка, перебираем до нужного ключа.

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

Как только коэффициент загрузки превышает пороговое значение, таблица проводит рехеширование (rehashing): создаётся новый массив вдвое большего размера, все элементы перераспределяются по новым индексам. Это дорогая операция — O(n), но происходит редко, поэтому амортизированно вставка всё равно остаётся O(1).

Открытая адресация

Второй подход принципиально другой: никаких связных списков. Если слот занят — ищем другой слот прямо в том же массиве. Это называется открытой адресацией (open addressing).

Самая простая стратегия — линейное зондирование (linear probing): если индекс i занят, пробуем i+1, i+2, i+3 и так далее по кругу.

Индекс 2 занят — пробуем 3. Свободно — вставляем. Кажется просто. Но у линейного зондирования есть неприятный эффект: кластеризация. Занятые слоты начинают слипаться в длинные «пробки», и при каждом новом поиске приходится пробегать весь кластер.

Более умная стратегия — квадратичное зондирование (quadratic probing): шаги не 1, 2, 3, а 1², 2², 3² — то есть 1, 4, 9, 16. Элементы разлетаются по таблице равномернее, кластеры не образуются так быстро.

Ещё лучше — двойное хеширование (double hashing): шаг вычисляется второй хеш-функцией. Формула: index = (hash1(key) + i * hash2(key)) % capacity. Каждый ключ имеет свой уникальный шаг зондирования — вероятность кластеров минимальна.

Посмотрим на простую реализацию с линейным зондированием, чтобы понять идею:

class OpenAddressHashTable
{
    private string[] keys;
    private string[] values;
    private bool[] deleted; // "надгробная плита" — об этом ниже
    private int capacity;

    public OpenAddressHashTable(int capacity = 16)
    {
        this.capacity = capacity;
        keys = new string[capacity];
        values = new string[capacity];
        deleted = new bool[capacity];
    }

    private int GetIndex(string key) =>
        Math.Abs(key.GetHashCode()) % capacity;

    public void Put(string key, string value)
    {
        int index = GetIndex(key);

        // Линейное зондирование: ищем свободный или совпадающий слот
        for (int i = 0; i < capacity; i++)
        {
            int probe = (index + i) % capacity;

            if (keys[probe] == null || deleted[probe] || keys[probe] == key)
            {
                keys[probe] = key;
                values[probe] = value;
                deleted[probe] = false;
                return;
            }
        }
        // Таблица заполнена — в реальном коде здесь рехеширование
        throw new InvalidOperationException("Таблица заполнена");
    }

    public string Get(string key)
    {
        int index = GetIndex(key);

        for (int i = 0; i < capacity; i++)
        {
            int probe = (index + i) % capacity;

            if (keys[probe] == null) return null; // пустой слот — ключа нет
            if (!deleted[probe] && keys[probe] == key) return values[probe];
        }

        return null;
    }

    public void Delete(string key)
    {
        int index = GetIndex(key);

        for (int i = 0; i < capacity; i++)
        {
            int probe = (index + i) % capacity;
            if (keys[probe] == null) return;
            if (!deleted[probe] && keys[probe] == key)
            {
                deleted[probe] = true; // не удаляем, а помечаем!
                return;
            }
        }
    }
}

Обратите внимание на массив deleted — это и есть надгробная плита (tombstone). Почему нельзя просто обнулить слот при удалении?

Представьте: вы добавили ключи A и B, оба попали на индекс 5. A занял слот 5, B — слот 6 (следующий). Потом вы удалили A и обнулили слот 5. Теперь при поиске B программа приходит на индекс 5, видит пустой слот и решает, что ключа B вообще нет — хотя он лежит на 6. Надгробная плита говорит: «Здесь что-то было удалено — ищи дальше».

Что выбрать и как это устроено в C#

Оба метода работают, но у каждого свои сильные стороны.

Метод цепочек проще в реализации и хорошо переносит высокий load factor — даже при заполнении таблицы на 90% он деградирует плавно. Зато каждый узел — отдельный объект в куче, это дополнительное давление на сборщик мусора. Хорошо подходит, когда нужны частые вставки и заранее неизвестен объём данных.

Открытая адресация хранит всё в одном массиве — данные лежат компактно в памяти, и процессор может использовать кэш эффективнее. Но она чувствительна к load factor: при заполнении выше 70–80% производительность резко падает из-за кластеров. Хорошо подходит, когда размер данных известен заранее и операций удаления немного.

А что делает Dictionary<K, V> в C#? Внутри используется схема, близкая к методу цепочек, но с оптимизацией: вместо настоящих указателей хранятся индексы в отдельных массивах entries и buckets. Это позволяет избежать накладных расходов на создание объектов узлов и держать данные компактнее. Рехеширование происходит автоматически, когда load factor превышает пороговое значение — вы об этом даже не узнаете.

var userRoles = new Dictionary<string, string>();

// Добавляем — коллизии обрабатываются внутри
userRoles["alice"] = "admin";
userRoles["bob"] = "editor";
userRoles["carol"] = "viewer";

// Поиск за O(1) в среднем, даже если внутри были коллизии
Console.WriteLine(userRoles["bob"]); // editor

// Безопасный поиск — если ключа нет, не бросает исключение
if (userRoles.TryGetValue("dave", out string role))
    Console.WriteLine(role);
else
    Console.WriteLine("Пользователь не найден");

Весь механизм обработки коллизий — детали реализации. Вы работаете с Dictionary как с таблицей «ключ → значение» и получаете O(1) в среднем, не думая о цепочках и зондировании.

Коллизия — это когда два разных ключа дают одинаковый индекс в хеш-таблице. Избежать этого нельзя математически: хеш-функция отображает бесконечное пространство ключей в конечный массив.

Метод цепочек хранит в каждом слоте связный список. При коллизии новый элемент добавляется в список — ничего не теряется. Поиск идёт по цепочке на нужном индексе. Прост в реализации, терпим к высокому load factor.

Открытая адресация ищет следующий свободный слот в том же массиве. Стратегии зондирования: линейное (i+1, i+2...), квадратичное (i+1², i+2²...), двойное хеширование. Хранит данные компактно, но чувствительна к заполненности таблицы. При удалении обязателен маркер tombstone — иначе разрывается цепочка зондирования.

Коэффициент загрузки (load factor) = count / capacity. Когда он превышает порог (обычно 0.75), таблица проводит рехеширование — создаёт новый массив вдвое больше и перераспределяет все элементы.

Dictionary<K, V> в C# использует вариант метода цепочек с оптимизированной памятью. Рехеширование, обработка коллизий — всё автоматически. Вы просто добавляете пары «ключ → значение» и получаете O(1) в среднем.

Понимание коллизий важно не для того, чтобы писать свои хеш-таблицы, а чтобы не удивляться, когда Dictionary вдруг занимает больше памяти, чем ожидалось, или почему выбор хорошей хеш-функции влияет на производительность.