Добавляет ли Dictionary <TKey, TValue> пустые элементы в резервное хранилище?

Question

Я смотрю в код позади Dictionary<TKey, TValue>. Интересно то, что в методе private Insert есть bucket, который, кажется, содержит пустые слоты в массиве предварительно заданного размера. Внутри метода Insert код проверяет, остались ли в корзине какие-либо элементы, и при необходимости изменит размер. Количество добавленных элементов является фактором простого числа. Кроме того, свойства словарной записи хранятся в структуре с хэш-кодом, ключом и значением.

Мой вопрос: какова цель? Это сделано для предотвращения попыток добавить элементы в объект словаря, когда может быть недостаточно памяти?

ПРИМЕЧАНИЕ. Я не хотел вставлять сюда какой-либо код, поскольку для чтения требуется разборка.

Answer 1

Объект Dictionary<TKey,TValue> не добавляет новые пустые значения с этим подходом. Что он делает, так это предварительно выделяет резервное хранилище для данных, которые позже будет предложено добавить. Конечной целью является то, что для среднего случая вставки не требуется выделение для завершения. Вместо этого он находит слот в существующем массиве сегментов для размещения самого себя.

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

• http://en.wikipedia.org/wiki/Hash_table

Answer 2

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

Существуют конструкторы для большинства коллекций, которые позволяют указать начальные размеры, начальные «потенциальные» размеры и факторы роста.Указание точного размера, если вы знаете, что это лучше всего делать в этом отношении.