Hashtable удвоение?

Question

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

Это похоже на List<T>, где оно удваивается по размеру при достижении предела? Если да, то воссоздает ли это дублирование коллекцию с нуля (на этот вопрос можно ответить и для List<T>, поскольку я не уверен, что это именно так)?

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

Answer 1

Я считаю, что и Hashtable, и Dictionary<TKey, TValue> расширяются до следующего простого числа после удвоения текущего счетчика, например, От 31 до 67.

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

Вы спрашивали о List<T> - там это действительно просто. Список поддерживается массивом, и вам просто нужно создать новый массив с нужным размером и скопировать содержимое текущего массива. Что-то вроде:

private void Resize(int newCapacity)
{
    T[] tmp = new T[newCapacity];
    Array.Copy(backingArray, tmp, backingArray.Length);
    backingArray = tmp;
}

Answer 2

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

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

Для хеш-таблицы .NET вы можете указать «коэффициент загрузки» в некоторых конструкторах . Из MSDN:

Коэффициент загрузки - максимальное соотношение элементов в ведра. Меньшая нагрузка фактор означает более быстрый поиск по стоимости увеличенного потребления памяти. коэффициент нагрузки 1,0 - лучший баланс между скоростью и размером.

Answer 3

Конечно, все зависит от вашей хэш-реализации.

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

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

Answer 4

почему бы не покопаться в отражателе , чтобы провести некоторое исследование, если интересно:

private void Insert(object key, object nvalue, bool add)
{
    uint num;
    uint num2;
    if (key == null)
    {
        throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
    }
    if (this.count >= this.loadsize)
    {
        this.expand();
    }
    else if ((this.occupancy > this.loadsize) && (this.count > 100))
    {
        this.rehash();
    }
    uint num3 = this.InitHash(key, this.buckets.Length, out num, out num2);
    int num4 = 0;
    int index = -1;
    int num6 = (int) (num % this.buckets.Length);
Label_0071:
    if (((index == -1) && (this.buckets[num6].key == this.buckets)) && (this.buckets[num6].hash_coll < 0))
    {
        index = num6;
    }
    if ((this.buckets[num6].key == null) || ((this.buckets[num6].key == this.buckets) && ((this.buckets[num6].hash_coll & 0x80000000L) == 0L)))
    {
        if (index != -1)
        {
            num6 = index;
        }
        Thread.BeginCriticalRegion();
        this.isWriterInProgress = true;
        this.buckets[num6].val = nvalue;
        this.buckets[num6].key = key;
        this.buckets[num6].hash_coll |= (int) num3;
        this.count++;
        this.UpdateVersion();
        this.isWriterInProgress = false;
        Thread.EndCriticalRegion();
    }
    else if (((this.buckets[num6].hash_coll & 0x7fffffff) == num3) && this.KeyEquals(this.buckets[num6].key, key))
    {
        if (add)
        {
            throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", new object[] { this.buckets[num6].key, key }));
        }
        Thread.BeginCriticalRegion();
        this.isWriterInProgress = true;
        this.buckets[num6].val = nvalue;
        this.UpdateVersion();
        this.isWriterInProgress = false;
        Thread.EndCriticalRegion();
    }
    else
    {
        if ((index == -1) && (this.buckets[num6].hash_coll >= 0))
        {
            this.buckets[num6].hash_coll |= -2147483648;
            this.occupancy++;
        }
        num6 = (int) ((num6 + num2) % ((ulong) this.buckets.Length));
        if (++num4 < this.buckets.Length)
        {
            goto Label_0071;
        }
        if (index == -1)
        {
            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed"));
        }
        Thread.BeginCriticalRegion();
        this.isWriterInProgress = true;
        this.buckets[index].val = nvalue;
        this.buckets[index].key = key;
        this.buckets[index].hash_coll |= (int) num3;
        this.count++;
        this.UpdateVersion();
        this.isWriterInProgress = false;
        Thread.EndCriticalRegion();
    }
}

Answer 5

Со страницы MSDN на Hashtable.Add () :

Если количество меньше емкости Hashtable, этот метод является O (1) операция. Если емкость должна быть увеличено для размещения нового элемент, этот метод становится O (n) операция, где n это число.

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

Answer 6

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

Для списка это не так дорого, как, например, воссоздание строки или массива, так как из одного списка в другой нужно копировать только указатели, и это можно сделать очень эффективно.

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