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

Question

Если у меня есть, скажем, 100 элементов, которые будут сохранены в словаре, я должен инициализировать его таким образом?

var myDictionary = new Dictionary<Key, Value>(100);

Насколько я понимаю, словарь .NET внутренне изменяет размеры, когда достигает заданной нагрузки, и что порог загрузки определяется как отношение емкости.

Это предполагает, что если 100 слов были добавлены в вышеупомянутый словарь, то при изменении одного из элементов он изменил бы свой размер. Изменение размера словаря - это то, чего я бы хотел избежать, так как он снижает производительность и тратит память.

Вероятность хэширования коллизий пропорциональна загрузке в словаре. Следовательно, даже если словарь не изменяет свой размер (и использует все свои слоты), производительность должна ухудшаться из-за этих коллизий.

Как лучше всего решить, к какой способности инициализировать словарь, если вы знаете, сколько элементов будет в словаре?

Answer 1

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

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

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

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

Answer 2

Я провел быструю проверку, возможно, не научную, но если я установил размер, для добавления одного миллиона элементов потребовалось 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();
        }

Answer 3

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

Answer 4

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

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

<Ол>

Dictionary зарезервирует объем памяти, необходимый для хранения k элементов;

На производительность QUERY для словаря это не влияет, и она не будет быстрее или медленнее;

Операции ADD не потребуют большего выделения памяти (возможно, дорого) и, следовательно, будут быстрее.

От MSDN :

  

Емкость словаря (TKey,   TValue) это количество элементов, которые   можно добавить в словарь (TKey,   TValue) перед изменением размера необходимо.   Как элементы добавляются в   Словарь (TKey, TValue), емкость   автоматически увеличивается по мере необходимости   перераспределением внутреннего массива.

     

Если размер коллекции может быть   оценочный, с указанием начального   емкость устраняет необходимость   выполнить ряд изменения размера   операции при добавлении элементов в   Словарь (TKey, TValue).

Answer 5

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

Answer 6

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