Предыдущий пост тут.

FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 2. Строки.

Продолжаем изучать, что у FrozenDictionary под капотом. Сегодня начнём говорить о словарях с ключом типа string. Для таких словарей предусмотрены аж 12 реализаций FrozenDictionary. Естественно, рассмотрим только принципиальные отличия.

LengthBucketsFrozenDictionary

При создании «замороженных» словарей с ключом типа string, FrozenDictionary в первую очередь попытается создать класс LengthBucketsFrozenDictionary, поэтому начнём именно с него. LengthBucketsFrozenDictionary оптимизирован для ситуаций, когда ключи имеют разную длину. Достигается это распределением ключей по бакетам (корзинам). Алгоритм напоминает блочную сортировку. Для каждой уникальной длины ключа создаётся бакет вместимостью MaxPerLength = 5 элементов.

💡 Чтобы стало понятнее, разберём пример словаря с 6 элементами (рис. 1). В словаре есть ключи длиной 3, 4 и 5 символов. Следовательно, их можно распределить в 3 бакета:

- бакет для ключей длиной 3: fig;
- бакет для ключей длиной 4: lime и kiwi;
- бакет для ключей длиной 5: apple, grape и lemon.

Поскольку известна минимальная (3) и максимальная (5) длина ключей, нет смысла создавать 3 отдельных бакета. Можно всё хранить в одном массиве _lengthBuckets. В таком случае индекс рассчитывается так: (key.Length - minLength) * MaxPerLength.

🔍 Поиск осуществляется в 3 шага (рис. 2):

1. Определяется бакет в массиве _lengthBuckets.
2. Линейным поиском в бакете определяется индекс искомого ключа в _keys.
3. Возвращается значение.

🚫 У LengthBucketsFrozenDictionary есть 2 ограничения:

1. Количество ключей с одинаковой длиной не должно превышать MaxPerLength (принцип Дирихле).
2. Количество пустых бакетов должно быть < 20%. Иначе реализация становится неэффективна с точки зрения использования памяти.

Если одно из этих условий не выполняется, то будет выбрана другая реализация FrozenDictionary. О ней я расскажу в следующей части.

📊 Результаты бенчмарка показывают, что чтение из LengthBucketsFrozenDictionary может быть до 99% быстрее обычного Dictionary. Но если в словаре количество ключей с одинаковой длиной достигает 5, то производительность небольших словарей (до 100 элементов) может быть хуже (рис. 3).