C# словарь внутренний массив размера

Question

Я не уверен, если это правильный вопрос, чтобы спросить здесь, но пожалуйста, не убивайте меня :)

У меня есть спор с другом о словаре С # ... Она говорит мне, что если я скажу словарь с 1 элементом. И хэш-код для ключа - 100000, тогда внутренний массив словаря будет иметь размер 100000!

Это правда? Я попытался найти ответы на Google, но по какой-то причине я не нашел для этого вопроса.

Answer 1

По умолчанию конструктор словаря «имеет начальную емкость по умолчанию», according to MSDN.

Он также заявляет:

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

Один такой конструктор просто берет Int32, который инициализирует внутреннюю память следующим образом:

Начальное количество элементов, что словарь может содержать.

Что такое «начальная емкость по умолчанию» на самом деле является внутренней детализацией реализации этого класса и как таковой не отображается в документации или общедоступном API.

Дизассемблирование mscorlib с ilspy и рассматривая конструктор по умолчанию показывает, что она реализуется следующим образом:

public Dictionary() : this(0, null) 
{ 
} 

скованный конструктор реализован следующим образом:

public Dictionary(int capacity, IEqualityComparer<TKey> comparer) 
{ 
    if (capacity < 0) 
    { 
     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); 
    } 

    if (capacity > 0) 
    { 
     this.Initialize(capacity); 
    } 

    this.comparer = (comparer ?? EqualityComparer<TKey>.Default); 
} 

т.е. Initialize() не вызывается вообще по конструктору по умолчанию, прямо или косвенно.

Initialize() - это метод, который устанавливает внутреннее хранилище.

Так что, если вы вызываете конструктор по умолчанию, размер внутренней памяти даже не инициализируется, пока вы не добавите элемент. Таким образом, он имеет практически нулевой размер.

Initialize() созывается со значением нуля при первом вызове .Add(), , который устанавливает вещи вверх.

private void Initialize(int capacity) 
{ 
    int prime = HashHelpers.GetPrime(capacity); 
    this.buckets = new int[prime]; 
    for (int i = 0; i < this.buckets.Length; i++) 
    { 
     this.buckets[i] = -1; 
    } 
    this.entries = new Dictionary<TKey, TValue>.Entry[prime]; 
    this.freeList = -1; 
} 

GetPrime(0) возвращается 3, поэтому this.buckets устанавливается на массив, содержащий три целых числа.

Линия, которая присваивает значение this.entries, выглядит немного странно, но я не вижу, где в нее входит 100000.

Короткий ответ
Я думаю, что ваш коллега ошибается.

Answer 2

Нет, это не так. Источники класса Dictionary<,> доказывают это.

Answer 3

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

Answer 4

Нет, в этом примере словарь будет иметь один элемент с ключом 100000.

Так ключевые dosn't влияют на размер словаря.

Answer 5

Нет, это неправда. Если у меня есть

Dictionary<int, object[]> dict = new Dictionary<int, object[]>() 
{ 
    {10000, new object[] { 1, 2, 3, 4 }} 
}; 

Этот словарь будет содержать один массив объектов с индексом 10000, а не 9999 пустых объектов слотами массива с последующим объектом мы вошли выше. Ответ - нет, вы друг ошибаетесь.

Надеюсь, это поможет.

Answer 6

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

Теперь давайте разберем хранилище словаря.

До тех пор, пока объект используется в качестве словаря Словаря, он не должен каким-либо образом изменять его значение хеша. Каждый ключ в словаре должен быть уникальным в соответствии с сравнением словаря. Ключ не может быть нулевой ссылкой (Nothing в Visual Basic), но может быть значение, если тип значения TValue является ссылочным типом.

Словарь требует реализации равенства, чтобы определить, являются ли ключи равными. Вы можете указать реализацию универсального интерфейса IEqualityComparer с помощью конструктора, который принимает параметр сравнения; если вы не указали реализацию, используется общий разделитель равенства по умолчанию EqualityComparer.Default. Если тип TKey реализует общий интерфейс System.IEquatable, по умолчанию используется сопоставление по умолчанию.

Хотя вероятно, что хэш-код будет использоваться, поскольку EqualityComparer.Default определяется как таковую:

Значение по умолчанию проверяет собственности, реализует ли тип T в System.IEquatable общий интерфейс, и если да возвратов EqualityComparer, который использует эту реализацию. В противном случае она возвращает EqualityComparer, который использует переопределения Object.equals и Object.GetHashCode предоставленные Т.

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

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

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

Ваш друг должен сделать свое исследование, прежде чем спорить. Уф!

Answer 7

Хэш-код (то есть GetHashCode) используется для размещения элементов в ковши, используемых в словаре.

Фактическая потребляемая мощность основана на количестве элементов в словаре.

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

List<List<KeyValuePair<T,J>>> buckets; // let's assume this get's allocated somewhere (the dictionary allocates this internally) 
... 
public J GetValueFromDictionary(T key) 
{ 
    int bucketIndex = key.GetHashCode() % buckets.Length; 
    return buckets[bucketIndex].Find(x => x.Key == key).Single().Value; 
}