Как в FrozenDictionary подсчитываются коллизии хэша

Второй короткий пост о деталях реализации FrozenDictionary, которые остались за кадром. Сегодня об алгоритме подсчёта количества коллизий хэша.

В FrozenDictionary хэш-коды всех ключей известны заранее. Это позволяет выбрать такое количество бакетов, при котором число коллизий не превышает допустимый порог — на данный момент это 5%. Делается это следующим образом:

1. Выбирается количество бакетов n из определённого диапазона. Этот диапазон подобран разработчиками .NET эвристическим способом.
2. Для каждого хэш-кода рассчитывается остаток от деления на n и считается количество одинаковых результатов.
3. Если количество коллизий слишком велико, то n увеличивается.

Вот пример с bool[]:

int[] hashCodes = [/*some hash codes*/];  
var seenBuckets = new bool[bucketsNumber];  
var collisionsCount = 0;

foreach (var hash in hashCodes) {  
    var bucketIndex = hash % bucketsCount;  
    if (seenBuckets[bucketIndex]) {  
        collisionsCount++;  
    }  
    else {  
        seenBuckets[bucketIndex] = true;  
    }  
}

Но в .NET сделали иначе и вместо bool[] используют int[] с битовыми сдвигами.

int[] hashCodes = [/*some hash codes*/];  
var seenBuckets = new int[bucketsNumber];  
var collisionsCount = 0;

foreach (var hash in hashCodes) {  
    var bucketIndex = hash % bucketsCount;  
    var i = bucketIndex / 32;  
    var bit = 1 << bucketIndex;  
    if ((seenBuckets[i] & bit) != 0) {  
        collisionsCount++;  
    }  
    else {  
        seenBuckets[i] |= bit;  
    }  
}

Такой подход позволяет значительно уменьшить размер массива (20% – 80%) и время его создания уменьшается в среднем на 70%. В то же время, скорость чтения и записи снижается в среднем на 50% и 198% соответственно (см. графики).

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