Проблема, которую нельзя обойти

В прошлом уроке мы разобрались, как ключ превращается в хеш-код, а затем в индекс корзины. Но там же выяснилось: два разных ключа могут дать одинаковый хеш, а два разных хеша могут дать одинаковый остаток от деления и попасть в одну корзину. Это не изъян конкретной хеш-функции, а неизбежное следствие того, что ключей больше, чем возможных адресов. Коллизии могут возникнуть, и хеш-таблица должна их как-то разрешать. Без этого она не сможет хранить больше одного элемента на корзину.

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

Идея цепочек очень проста. Массив buckets — это массив списков. Каждый список — это корзина, в которой могут находиться несколько элементов с одинаковым индексом. Когда мы добавляем элемент, вычисляем индекс и добавляем в список по этому индексу. Когда ищем — вычисляем индекс, идём в список и просматриваем его, сравнивая ключи через Equals. Когда удаляем — находим в списке и убираем.

Насколько велики списки? Это зависит от коэффициента заполнения alpha = n / m, где n — число элементов, m — число корзин. Если alpha близка к 1, в среднем на корзину приходится один элемент, и списки короткие. Если alpha больше 1, списки становятся длиннее, и поиск замедляется. Но здесь есть важное отличие от открытой адресации: в методе цепочек alpha может быть больше 1. Мы можем хранить в десять раз больше элементов, чем корзин, — просто списки будут в среднем по десять элементов. Поиск по ним станет дольше, но таблица продолжит работать. Разумеется, для хорошей производительности alpha стараются держать в разумных пределах, и когда она превышает порог, массив корзин расширяют.

Реализация IntSet с цепочками

Соберём учебную структуру для множества целых чисел с разрешением коллизий через цепочки. Начальная ёмкость — четыре корзины. Порог для расширения — alpha больше 0,75. При превышении порога удваиваем массив и перераспределяем все элементы по новым корзинам.

Индекс корзины вычисляем так: (int)((uint)value % (uint)buckets.Length). Приведение к uint здесь нужно, чтобы отрицательные ключи получали корректный неотрицательный остаток. Иначе -1 % 4 в C# даст -1, и мы выйдем за границы массива. Приведение к uint превращает -1 в очень большое положительное число, и остаток получается корректным.

using System;
using System.Collections.Generic;

var set = new IntSet();
set.Add(1);
set.Add(5);
set.Add(9);
Console.WriteLine(set.Contains(5));
Console.WriteLine(set.Contains(2));
Console.WriteLine(set.Count);

set.Add(13);
Console.WriteLine(set.Count);

Console.WriteLine(set.Remove(5));
Console.WriteLine(set.Remove(5));

set.Add(-1);
Console.WriteLine(set.Contains(-1));

class IntSet
{
    private List<int>[] _buckets;
    private int _count;

    public IntSet(int capacity = 4)
    {
        if (capacity <= 0) throw new ArgumentOutOfRangeException(nameof(capacity));
        _buckets = new List<int>[capacity];
        for (int i = 0; i < capacity; i++) _buckets[i] = new List<int>();
    }

    public int Count => _count;

    public bool Contains(int value)
    {
        int index = Index(value);
        return _buckets[index].Contains(value);
    }

    public bool Add(int value)
    {
        int index = Index(value);
        if (_buckets[index].Contains(value)) return false;
        if (_count + 1 > _buckets.Length * 0.75)
        {
            Resize(checked(_buckets.Length * 2));
            index = Index(value);
        }
        _buckets[index].Add(value);
        _count++;
        return true;
    }

    public bool Remove(int value)
    {
        int index = Index(value);
        if (_buckets[index].Remove(value))
        {
            _count--;
            return true;
        }
        return false;
    }

    private int Index(int value)
    {
        return (int)(unchecked((uint)value) % (uint)_buckets.Length);
    }

    private void Resize(int newCapacity)
    {
        var old = _buckets;
        _buckets = new List<int>[newCapacity];
        for (int i = 0; i < newCapacity; i++) _buckets[i] = new List<int>();
        _count = 0;
        foreach (var bucket in old)
        {
            foreach (int value in bucket)
            {
                int index = Index(value);
                _buckets[index].Add(value);
                _count++;
            }
        }
    }
}

Вывод:

True
False
3
4
True
False
True

Разберём. Начинаем с четырёх корзин. Add(1): индекс 1 % 4 = 1, корзина 1, добавляем. Add(5): 5 % 4 = 1, попадает в ту же корзину 1, где уже лежит 1. Список корзины 1 становится [1, 5]. Add(9): 9 % 4 = 1, снова корзина 1, список [1, 5, 9]. Все три числа попали в одну корзину, но структура работает: Contains(5) находит 5 в списке, Contains(2) не находит. Count равен 3.

Add(13): 13 % 4 = 1, но перед добавлением проверяем порог. _count + 1 = 4, порог 4 · 0,75 = 3. Условие 4 > 3 истинно — расширяемся до восьми корзин. Все элементы перераспределяются: 1 % 8 = 1, 5 % 8 = 5, 9 % 8 = 1, теперь они распределены по разным корзинам. После расширения добавляем 13: 13 % 8 = 5, корзина 5, где уже лежит 5. Список корзины 5 становится [5, 13]. Count равен 4.

Remove(5): индекс 5 % 8 = 5, в списке корзины 5 находим 5 и удаляем. Список становится [13]. Count уменьшается до 3. Повторный Remove(5) возвращает false: 5 больше нет.

Add(-1): приведение к uint даёт 4 294 967 295. 4 294 967 295 % 8 = 7. Корзина 7, добавляем. Contains(-1) находит. Всё работает корректно.

Разберём оценки. При достаточно равномерном распределении ключей Contains и Remove в среднем работают за O(1 + alpha): вычисление индекса O(1), потом просмотр списка длиной, пропорциональной alpha. При alpha порядка 1 это ожидаемо O(1). Но в худшем случае все элементы могут попасть в одну корзину, и поиск станет O(n). Это не теоретическая случайность: если хеш-функция плохая или ключи подобраны специально, все они соберутся в одном списке. Хорошая хеш-функция делает такое маловероятным, но не невозможным.

При таком распределении Add ожидаемо амортизированно O(1). Наша простая функция для целых чисел сама по себе равномерность на произвольном входе не обеспечивает. Расширение Resize занимает O(n + m): нужно перебрать все n элементов и создать m новых списков. Это дорого, но происходит редко: при удвоении ёмкости каждое расширение случается после примерно n добавлений, и суммарная работа по всем расширениям за серию из n добавлений линейна. Значит, амортизированная стоимость одного Add остаётся O(1).

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

Второй подход устроен совсем иначе. Здесь нет списков: массив содержит сами элементы, и каждая корзина — это один слот. Когда мы добавляем элемент и его индекс занят, мы начинаем искать другой свободный слот — «пробировать» массив. Простейший способ — линейное пробирование: пробуем индекс, потом индекс + 1, потом + 2, и так далее, по кругу, пока не найдём пустое место.

Пример. Пусть таблица имеет восемь слотов. Добавляем 1: 1 % 8 = 1, слот 1 свободен, кладём туда. Добавляем 9: 9 % 8 = 1, слот 1 занят, пробуем слот 2 — свободен, кладём. Добавляем 17: 17 % 8 = 1, слоты 1 и 2 заняты, пробуем 3 — свободен, кладём. Три элемента, которые в цепочном методе попали бы в один список, здесь распределились по трём соседним слотам. Это называется кластеризацией: занятые слоты собираются в непрерывные группы, и чем больше группа, тем чаще новые элементы попадают в неё.

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

Но здесь есть тонкость с удалением. Если мы просто очистим слот при удалении, мы разорвём цепочку пробирования. Пример: слоты 1, 2, 3 заняты соответственно 1, 9, 17. Удаляем 9, ставим в слот 2 пусто. Теперь ищем 17: индекс 1, слот 1 содержит 1 — не то, слот 2 пуст — и мы останавливаемся, не дойдя до 17 в слоте 3. Ответ «не найдено» будет неверным. Чтобы этого избежать, удалённые слоты помечают специальным маркером — tombstone, «надгробие». Такой слот уже не содержит элемента, но он не «никогда не был занят»: поиск через него проходит дальше, а вставка может его переиспользовать.

Различие между tombstone и пустым слотом принципиально. Пустой слот означает «здесь ничего не было, можно прекращать поиск». Tombstone означает «здесь что-то было и было удалено; поиск нужно продолжать». При вставке нужно проверить дубликаты по всему пути пробирования, не останавливаясь на первой могиле: возможно, искомый ключ лежит дальше. Проход по таблице ограничен её размером m, иначе при полностью заполненной таблице мы бы зациклились.

Для удобной и быстрой работы открытой адресации alpha = n / m поддерживают меньше 1: в таблице должно оставаться хотя бы несколько свободных слотов. Если alpha приближается к 1, кластеризация становится настолько плотной, что поиск вырождается в линейный. Поэтому при alpha выше определённого порога (обычно 0,5–0,7) таблицу расширяют и перепробируют все элементы в новую, большую таблицу.

У каждого метода свои сильные и слабые стороны. Цепочки проще в реализации: вставка и удаление работают со списком, а удаление не требует никаких могил — просто убираем элемент из списка. Коэффициент alpha может превышать 1, что позволяет работать с плотно заполненной таблицей. Но корзины требуют дополнительной памяти: в нашем List это отдельные динамические массивы, а при связных цепочках — узлы, и при большом числе элементов эти накладные расходы становятся заметными.

Открытая адресация компактнее: всё хранится в одном массиве, без списков и дополнительных ссылок. Но она требует alpha < 1 и аккуратной работы с удалением через могилы. Кластеризация может сильно замедлить поиск, если таблица заполнена плотно. При расширении нужно заново найти место каждому элементу; стоимость зависит от длины пробирования и распределения ключей.

Что именно используется в конкретных реализациях словарей и множеств — вопрос отдельный, и мы его здесь не разбираем: в C# внутреннее устройство Dictionary и HashSet — не наша тема, и смешивать наш учебный цепочный подход с их реализацией не стоит. Важно понимать сами принципы: коллизии нужно разрешать, и для этого есть два фундаментальных подхода, у каждого своя механика и свои компромиссы.

И ещё одно уточнение, которое часто путают. Техника разрешения коллизий — это про размещение элементов: где именно хранится элемент, если его корзина занята. А проверка Equals — это отдельный этап: после того как мы нашли корзину или слот, мы сравниваем ключи, чтобы убедиться, что это именно тот элемент, который мы ищем. Одна и та же проверка Equals нужна и в цепочках, и в открытой адресации, но механика размещения у них совершенно разная. Не стоит смешивать эти два уровня.

В следующих уроках мы перейдём к более высокоуровневым структурам — словарям и множествам как абстракциям, — и там уже не нужно будет думать о каждой корзине. Но понимание того, что под капотом, полезно: оно помогает предвидеть, когда структура будет работать быстро, а когда начнёт тормозить.