Как решается коллизия в Dictionary?

Общий принцип разрешения коллизий в Dictionary

В Unity/C# под Dictionary<TKey, TValue> подразумевается реализация из пространства имен System.Collections.Generic, которая использует хэш-таблицу для хранения данных. Коллизия возникает, когда два разных ключа возвращают одинаковый хэш-код или когда разные хэш-коды отображаются в одну и ту же ячейку (бакет) хэш-таблицы.

Основной метод: Метод цепочек (Separate Chaining)

Dictionary в C# использует метод цепочек для разрешения коллизий. Каждый бакет (ячейка) хэш-таблицы содержит связный список элементов (запись Entry), чьи ключи имеют коллизию.

Структура данных внутри Dictionary:

// Упрощенное представление внутренней структуры (реальный код сложнее)
private struct Entry
{
    public int hashCode; // Кэшированный хэш-код ключа
    public int next;     // Индекс следующего элемента в цепочке (-1 если конец)
    public TKey key;
    public TValue value;
}

private int[] buckets;  // Массив индексов, указывающих на первую запись в цепочке
private Entry[] entries; // Массив записей (хранит данные и связи цепочек)

Процесс работы при коллизии

1. Вычисление индекса бакета: При добавлении или поиске элемента сначала вычисляется хэш-код ключа (через key.GetHashCode()), который затем приводится к диапазону индексов массива buckets (обычно через операцию % или побитовую маску).

2. Обработка коллизии:

   • Если бакет пуст (buckets[bucketIndex] == -1), элемент добавляется в массив entries, а в buckets[bucketIndex] записывается его индекс.
   • Если бакет уже содержит элемент (или цепочку), происходит итерация по цепочке через поле next в записях entries. Для каждого элемента проверяется:

     - Совпадение хэш-кодов (`entry.hashCode == key.GetHashCode()`)
     - Фактическое равенство ключей (`entry.key.Equals(key)`)

• При добавлении: если ключ найден, его значение обновляется; если не найден, новый элемент добавляется в конец цепочки (или в первую свободную ячейку entries).
• При поиске: если ключ найден, возвращается его значение; если не найден — выбрасывается исключение (при dict[key]) или возвращается default (при TryGetValue).

Пример добавления с коллизией:

var dict = new Dictionary<int, string>();
dict.Add(1, "One");
dict.Add(17, "Seventeen"); // Предположим, что 1 и 17 дали коллизию хэш-кодов

// Внутреннее представление (упрощенно):
// buckets[коллизионный_индекс] -> индекс записи для ключа 1
// entries[индекс_для_1].next    -> индекс записи для ключа 17
// entries[индекс_для_17].next   -> -1 (конец цепочки)

Критические аспекты для Unity-разработчика

• Производительность: В худшем случае (много коллизий) поиск может деградировать до O(n). Качество метода GetHashCode() ключей напрямую влияет на распределение.
• Кастомизация: Для пользовательских типов в качестве ключа обязательно переопределять GetHashCode() и Equals() для минимизации коллизий и корректной работы.
• Размер таблицы: Dictionary автоматически увеличивает размер (рехеширование) при достижении порога заполнения, что может вызвать задержку. В производительно-критичном коде можно задать начальную емкость через конструктор.
• Потокобезопасность: Dictionary не является потокобезопасным. В многопоточных сценариях в Unity используйте ConcurrentDictionary или механизмы синхронизации.

Пример правильного ключа:

public class CharacterId
{
    public readonly int Id;
    public readonly string Region;

    public override int GetHashCode()
    {
        // Комбинирование хэшей для уменьшения коллизий
        unchecked
        {
            int hash = 17;
            hash = hash * 31 + Id.GetHashCode();
            hash = hash * 31 + (Region?.GetHashCode() ?? 0);
            return hash;
        }
    }

    public override bool Equals(object obj)
    {
        return obj is CharacterId other && 
               Id == other.Id && 
               Region == other.Region;
    }
}

Таким образом, Dictionary в C# эффективно разрешает коллизии через метод цепочек, но требует внимания к реализации хэш-функций и равенства ключей для поддержания производительности, что особенно важно в ресурсоограниченной среде Unity.