Метод GrowTable в параллельном словаре в .Net

Question

Можете ли вы объяснить магию в методе GrowTable?

Код:

// Compute the new table size. We find the smallest integer larger than twice the previous table size, and not divisible by
// 2,3,5 or 7. We can consider a different table-sizing policy in the future. 
int newLength;
try
{
    checked
    {
        // Double the size of the buckets table and add one, so that we have an odd integer.
        newLength = buckets.Length * 2 + 1;

        // Now, we only need to check odd integers, and find the first that is not divisible 
        // by 3, 5 or 7.
        while (newLength % 3 == 0 || newLength % 5 == 0 || newLength % 7 == 0)
        {
            newLength += 2;
        }

        Assert(newLength % 2 != 0);
    }
}

В других коллекциях .net (List, Dictionary) метод изменения размера поддерживает двойной размер.

См. Код, 1478 строка

Answer 1

Когда вы храните данные в растущем массиве, решение о том, насколько их вырастить, в основном является пространственно-временным компромиссом. Если вы выделяете (и, таким образом, тратите) много памяти всякий раз, когда вам нужно увеличить массив, вы получаете более быстрое выполнение, потому что вам не нужно часто изменять размер массива. (Что касается амортизированной сложности времени, то рост на x% одинаков для любого x. Но фактическая скорость отличается.)

Сколько обычно растет массив, не задокументировано (только временная сложность сложения). Например, текущая реализация MS .Net List<T> увеличивается в два раза, но текущая реализация MS C ++ vector<T> растет только на 50%.

Все это может применяться к коллекции записей в словаре на основе хеш-таблицы, если вы реализуете его в одном массиве (что, конечно, не единственная возможность). Но вы должны учитывать и ведра. У них тоже есть пространственно-временной компромисс, но другой: если вы выбираете любой размер, словарь работает. Но чем больше коллекция, тем меньше у вас коллизий. И с меньшим количеством столкновений вы получите более быстрое время поиска. Если вы хотите иметь поиск в постоянном времени, количество сегментов должно быть линейно пропорционально количеству элементов в словаре. Поэтому имеет смысл сделать размер массива buckets таким же, как и для массива entry.

Но есть еще одна вещь. Если хэш-коды имеют некоторую структуру, вы не хотите, чтобы эта структура отражалась в вашем словаре, потому что это вызывает больше коллизий. Допустим, вы использовали идентификаторы учетных записей в качестве ключей хеша. И вы назначаете идентификаторы пользователям в ИТ-отделе, начиная с 0, пользователям в маркетинге от 200 и т. Д. Теперь, если размер массива сегментов равен 100, вы получите много коллизий и, следовательно, ужасную производительность. Если бы размер массива делился на 2 или 5, число коллизий также увеличилось бы.

Из-за этого лучшим размером для массива buckets является простое число. Следующий лучший размер - почти простое число (число, у которого не много делителей). И, как и прежде, существует компромисс: вычисление простых чисел происходит относительно медленно. Чтобы сделать это быстрее, можно сказать, что почти простые числа достаточно хороши. Или вы можете предварительно вычислить некоторые простые числа, что стоит немного памяти.

Со всеми этими компромиссами, нет единого лучшего решения. Для вашего использования вы можете попробовать отрегулировать все эти параметры и выбрать наиболее подходящий для вас. Но авторы библиотек должны сделать их достаточно хорошими для всех или, по крайней мере, для большинства. И авторы Dictionary<T> выбрали почему-то несколько иначе, чем авторы ConcurrentDictionary<T>.

Конкретный алгоритм, который использует текущая реализация MS Dictionary<T>, состоит в том, чтобы иметь таблицу с некоторыми простыми числами до 7 199 369. Он всегда использует простое число, которое больше двойного текущего размера. Для небольших чисел он выбирает наименьшее такое простое число из таблицы. Для больших чисел вычисляется наименьшее такое простое число.