Следует ли инициализировать общий словарь .NET с емкостью, равной количеству элементов, которые он будет содержать?

Я думаю, вы слишком усложняете дело. Если вы знаете, сколько элементов будет в вашем словаре, то обязательно укажите это при построении. Это поможет словарю выделить необходимое пространство во внутренних структурах данных, чтобы избежать перераспределения и перетасовки данных.

Да, в отличие от HashTable, который использует повторное хеширование как метод разрешения коллизий, Dictionary будет использовать цепочку. Так что да, использовать счетчик - это хорошо. Для HashTable вы, вероятно, захотите использовать count * (1/fillfactor)

Указание начальной емкости для конструктора Dictionary увеличивает производительность, поскольку будет меньше изменений размеров внутренних структур, которые хранят значения словаря во время операций ADD.

Учитывая, что вы указываете конструктору Dictionary начальную емкость k, тогда:

1. Dictionary зарезервирует объем памяти, необходимый для хранения k элементов;
2. На производительность QUERY по словарю не влияет, и он не будет ни быстрее, ни медленнее;
3. Операции ADD не потребуют большего выделения памяти (возможно, дорого) и, следовательно, будут быстрее.

От MSDN:

The capacity of a Dictionary(TKey, TValue) is the number of elements that can be added to the Dictionary(TKey, TValue) before resizing is necessary. As elements are added to a Dictionary(TKey, TValue), the capacity is automatically increased as required by reallocating the internal array.

If the size of the collection can be estimated, specifying the initial capacity eliminates the need to perform a number of resizing operations while adding elements to the Dictionary(TKey, TValue).

Я провел быстрый тест, вероятно, не научный, но если я установил размер, потребовалось 1,2207780 секунд, чтобы добавить один миллион элементов, и 1,5024960 секунд, чтобы добавить, если я не указал размер словаря ... мне это кажется незначительным .

Вот мой тестовый код, может быть, кто-то сможет провести более строгий тест, но я сомневаюсь, что это имеет значение.

static void Main(string[] args)
        {
            DateTime start1 = DateTime.Now;
            var dict1 = new Dictionary<string, string>(1000000);

            for (int i = 0; i < 1000000; i++)
                dict1.Add(i.ToString(), i.ToString());

            DateTime stop1 = DateTime.Now;

            DateTime start2 = DateTime.Now;
            var dict2 = new Dictionary<string, string>();

            for (int i = 0; i < 1000000; i++)
                dict2.Add(i.ToString(), i.ToString());

            DateTime stop2 = DateTime.Now;

            Console.WriteLine("Time with size initialized: " + (stop1.Subtract(start1)) + "\nTime without size initialized: " + (stop2.Subtract(start2)));
            Console.ReadLine();
        }

Первоначальный размер - это всего лишь предположение. Например, большинство хеш-таблиц предпочитают, чтобы размеры были простыми числами или степенью двойки.

То, чем вы должны инициализировать емкость словаря, зависит от двух факторов: (1) Распределение функции gethashcode и (2) Сколько элементов нужно вставить.

Ваша хеш-функция должна быть либо случайным образом распределена, либо она должна быть специально сформулирована для вашего набора входных данных. Допустим, первое, но если вас интересует второе, поищите идеальные хеш-функции.

Если у вас есть 100 элементов для вставки в словарь, случайным образом распределенная хеш-функция, и вы устанавливаете емкость равной 100, то, когда вы вставляете i-й элемент в хеш-таблицу, у вас будет (i-1) / 100 вероятность того, что i-й элемент элемент будет сталкиваться с другим элементом при вставке. Если вы хотите снизить вероятность столкновения, увеличьте пропускную способность. Увеличение ожидаемой вместимости вдвое снижает вероятность столкновения вдвое.

Кроме того, если вы знаете, как часто вы собираетесь обращаться к каждому элементу в словаре, вы можете вставлять элементы в порядке убывания частоты, поскольку элементы, которые вы вставляете первыми, в среднем будут доступны быстрее.