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

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

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

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

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

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

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

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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

От MSDN:

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

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

Ответ 5

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

Ответ 6

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