Подтвердить что ты не робот

Список <T> увеличение емкости против увеличения словаря <K, V>?

Почему List<T> увеличивает свою емкость в 2 раза?

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

Почему Dictionary<K,V> использует простые числа как емкость?

private void Resize()
{
    int prime = HashHelpers.GetPrime(this.count * 2);
    int[] numArray = new int[prime];
    for (int i = 0; i < numArray.Length; i++)
    {
        numArray[i] = -1;
    }
    Entry<TKey, TValue>[] destinationArray = new Entry<TKey, TValue>[prime];
    Array.Copy(this.entries, 0, destinationArray, 0, this.count);
    for (int j = 0; j < this.count; j++)
    {
        int index = destinationArray[j].hashCode % prime;
        destinationArray[j].next = numArray[index];
        numArray[index] = j;
    }
    this.buckets = numArray;
    this.entries = destinationArray;
}

Почему он не просто умножается на 2? Оба имеют дело с поиском места для хранения памяти... правильно?

4b9b3361

ОТВЕТЫ

Ответ 1

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

Таблицы хэш обычно используют операцию modulo, чтобы найти ведро, в которое входит запись, как вы можете видеть в своем коде:

int index = destinationArray[j].hashCode % prime;

Предположим, что ваша функция hashCode приводит к следующим хэш-кодам среди других {x, 2x, 3x, 4x, 5x, 6x...}, тогда все они собираются в виде всего m кол-во кодов, где m = table_length/GreatestCommonFactor (table_length, x). (Тривиально проверить/вывести это). Теперь вы можете сделать одно из следующих действий, чтобы избежать кластеризации:

  • Убедитесь, что вы не генерируете слишком много хэш-кодов, которые являются кратными другому хэш-коду, например, в {x, 2x, 3x, 4x, 5x, 6x...}. Но это может быть довольно сложно, если ваш hashTable должен иметь миллионы записей.

  • Или просто сделайте m равным table_length, сделав GreatestCommonFactor (table_length, x) равным 1, т.е. сделав table_length взаимно просты с x. И если x может быть почти любым числом, тогда убедитесь, что table_length является простым числом.

(из http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html)

HashHelpers.GetPrime(this.count * 2)

должно возвращать простое число. Посмотрите на определение HashHelpers.GetPrime().

Ответ 2

Словарь

помещает все его объекты в ведра в зависимости от их значения GetHashCode, т.е. Bucket[object.GetHashCode() % DictionarySize] = object;
Он использует простое число для размера, чтобы избежать вероятности столкновений. Предположительно, размер с большим количеством делителей будет плохой для плохо разработанных хеш-кодов.

Ответ 3

От question в SO;

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

List<T> используется array для хранения данных; и увеличение емкости массива требует копирования массива в новое место памяти; что требует много времени. Думаю, для того, чтобы снизить количество копирующих массивов, список удваивает его емкость.

Ответ 4

Я не компьютерный ученый, но...

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

loadFactor = FreeCells/AllCells

это мы можем написать как

loadFactor = (AllBuckets - UsedBuckets)/AllBuckets

loadFactor определяет непродолжительность столкновения в хэш-карте. Таким образом, используя Prime Number, число, которое

.. - натуральное число, большее 1, что не имеет положительных делителей, отличных от 1 и самого себя.

мы уменьшаем (но не стираем) риск столкновения в нашем хэшмапе.

Если loadFactor стремится к 0, у нас есть более безопасный hashmap, поэтому мы всегда должны поддерживать его как можно ниже. В MS блог выяснилось, что значение этого loadFactor (оптимального) должно быть arround 0.72, поэтому, если оно становится мы увеличиваем мощность, следуя ближайшему простому числу.

EDIT

Чтобы быть более ясным в этом: имея простое число, обеспечивает, насколько это возможно, равномерное распределение хэшей в этой конкретной реализации хеша, которую мы имеем в .NET-словаре. Это не о эффективности поиска значений, а эффективности используемой памяти и уменьшении риска столкновения.

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

Ответ 5

Dictionary нуждается в некоторой эвристике, чтобы распределение хеш-кода среди ведер было более равномерным.

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

int num = this.comparer.GetHashCode(key) & 2147483647; // make hash code positive
// get the remainder from division - that our bucket index
int num2 = this.buckets[num % ((int)this.buckets.Length)];

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

Это не единственная эвристика. Java HashMap, например, использует другой подход. Количество ведер там всегда имеет мощность 2, а при выращивании оно удваивает количество ведер:

resize(2 * table.length);

Но при вычислении индекса ковша он изменяет хеш:

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
    return h & (length-1);
}

// from put() method
int hash = hash(key.hashCode()); // get modified hash
int i = indexFor(hash, table.length); // trim the hash to the bucket count

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

Дополнение. Рост поведения не влияет на сложность Add. Dictionary, HashMap и List каждый из них амортизировал сложность O (1) Add.

Вырастить операцию занимает O (N), но происходит только в течение N-го раза, поэтому, чтобы вызвать операцию роста, нам нужно вызвать Add N раз. Для N = 8 время, необходимое для выполнения N Add, имеет значение

O (1) + O (1) + O (1) + O (1) + O (1) + O (1) + O (1) + O (N) = O (N) + O ( N) = O (2N) = O (N)

Итак, N Add возьмем O (N), то один Add принимает O (1).

Ответ 6

Увеличение емкости с помощью постоянного коэффициента (вместо увеличения емкости с помощью константы аддитивности), когда требуется изменение размера, чтобы гарантировать некоторое время амортизации. Например, добавление или удаление из конца списка на основе массива требует времени O(1), за исключением случаев, когда вам необходимо увеличить или уменьшить емкость, требующую копирования содержимого списка, и, следовательно, требуя времени O(n). Изменение емкости на постоянный коэффициент гарантирует, что амортизированное время выполнения еще O(1). Оптимальное значение коэффициента зависит от ожидаемого использования. Дополнительная информация о Wikipedia.

Выбор возможности хэш-таблицы, чтобы быть простым, используется для улучшения распределения элементов. bucket[hash % capacity] даст более равномерное распределение, если hash неравномерно распределено, если capacity является простым. (Я не могу дать математику позади этого, но я ищу хорошую ссылку.) Сочетание этого с первым пунктом - именно то, что делает реализация - увеличение емкости как минимум (как минимум) 2, а также обеспечение того, чтобы емкость проста.