.NET Dictionary, впечатляюще быстро, но как это работает?

Ответ 1

dictionary<T,T> в .Net - это структура данных, называемая хеш-таблицей:

В таблице Hash и в словаре .Net:

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

http://msdn.microsoft.com/en-us/library/4yh14awz.aspx

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html

В двоичном поиске:

http://en.wikipedia.org/wiki/Binary_search

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

Ответ 2

Основной принцип:

• Установить пустой массив.
• Получить хэш-код.
• Re-hash hash соответствует размеру массива (например, если массив имеет 31 элемент в размере, мы можем сделать hash % 31) и использовать его как индекс.

Извлечение - это то же самое, что и поиск индекса, получение ключа, если он есть, и вызов Equals в этом элементе.

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

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

Очевидно, что очень плохой алгоритм хэширования может уничтожить это, вы можете продемонстрировать это себе, создав словарь объектов, где метод hashcode следующий:

public override int GetHashCode()
{
  return 0;
}

Это допустимо, но ужасно, и превращает ваше поведение близкого к O (1) в O (n) (и плохое, даже когда O (n) идет.

Существует множество других деталей и оптимизаций, но приведенный выше является основным принципом.

Edit:

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

Ответ 3

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

Как работает словарь .NET в длину (или вид).

Начнем с концепции, как указывалось во многих других ответах: Dictionary<TKey, TValue> - это обобщенная (в смысле функции языка С#) реализация хеш-таблицы.

Хеш-таблица - это просто ассоциативный массив, то есть когда вы передаете пару (ключ, значение), тогда ключ используется для вычисления хеш-кода, который поможет вычислить местоположение (называемое сегментом) в базовом массиве хранения. (называемые сегментами), в которых будет сохраняться пара и некоторая другая дополнительная информация. Обычно это достигается путем вычисления по модулю % хеш-кода от размера массива/сегментов: hashCode % buckets.Length.

Этот вид ассоциативного массива имеет среднюю сложность O (1) (т.е. Постоянное время) для поиска, вставки и удаления... за исключением определенных обстоятельств, которые мы рассмотрим позже. Так что, вообще говоря, поиск слов в словаре гораздо быстрее, чем, скажем, в списке или массиве, поскольку вам не нужно ~ обычно ~ перебирать все значения.

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

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

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

Хорошо, теперь давайте посмотрим, как вещи вставляются в .NET Dictionary<TKey, TValue> который сводится к просмотру кода метода ниже:

private void Insert(TKey key, TValue value, bool add)

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

Шаг 1: Дайте мне хэш-код

Существует два способа вычисления хеш-кода клавиши TKey:

• Один из них основан на стандартном IEqualityComparer<TKey> реализации IEqualityComparer<TKey> если вы не передаете его как параметр Dictionary<TKey, TValue> который в основном генерируется EqualityComparer<TKey>.Default (реализация доступна здесь), в случае, если TKey является тип, отличный от всех обычных вещей (таких как примитивы и строки), например пользовательский тип, IEqualityComparer<in TKey> будет использовать реализацию (включая override):

  • bool Equals(object obj)
  • int GetHashCode()

• Другой, ну, опирается на реализацию IEqualityComparer<in TKey> вы можете передать конструктору Dictionary<TKey, TValue>.

Интерфейс IEqualityComparer<in T> выглядит так:

// The generic IEqualityComparer interface implements methods to if check two objects are equal
// and generate Hashcode for an object.
// It is use in Dictionary class.  
public interface IEqualityComparer<in T>
{
    bool Equals(T x, T y);
    int GetHashCode(T obj);
}

В любом случае, словарь заканчивает тем, что имеет первый хеш-код с использованием метода сравнения: comparer.GetHashCode()

Шаг 2: Получить целевое ведро

Хеш-код, который мы получили из нашего ключа TKey через IEqualityComparer<in T> иногда может быть отрицательным, что не очень полезно, если мы хотим получить положительный индекс для массива...

Что происходит, чтобы избавиться от отрицательных значений, Int32 код Int32 полученный с помощью comparer.GetHashCode() имеет значение "ANDed" с Int32.MaxValue (т. 0x7FFFFFFF 2147483647 или 0x7FFFFFFF) (в смысле логической логики: биты):

var hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;

Целевое ведро (индекс) получается следующим образом:

var targetBucket = hashCode % buckets.Length

Будет также видеть в данный момент, как buckets изменяется массив.

buckets (int[]) - это private поле Dictionary<TKey, TValue> содержащее индексы первого связанного слота в поле entries которое является Entry[], причем Entry определяется следующим образом:

private struct Entry
{
    public int hashCode;
    public int next;
    public TKey key;
    public TValue value;
}

key, value и hashcode являются самоочевидными полями, что касается next поля, оно в основном указывает индекс, если есть другой элемент в этой цепочке (т.е. несколько ключей с одинаковым хэш-кодом), если эта запись является последним элементом цепочка затем next поле устанавливается на -1.

Примечание: поле hashCode в struct Entry - это поле после корректировки отрицательного значения.

Шаг 3: проверьте, есть ли уже запись

На этом этапе важно отметить, что поведение отличается в зависимости от того, обновляете ли вы (add = false) или строго вставляете (add = true) новое значение.

Теперь мы проверим записи, относящиеся к targetBucket начиная с первой записи, которая может быть задана как:

var entryIndex = buckets[targetBucket];
var firstEntry = entries[entryIndex];

Фактический (упрощенный) исходный код с комментариями:

// Iterating through all the entries related to the targetBucket
for (var i = buckets[targetBucket]; i >= 0; i = entries[i].next)
{
    // Checked if all 
    if (entries[i].hashCode == hashCode && 
        comparer.Equals(entries[i].key, key)) 
    {
        // If update is not allowed
        if (add) 
        { 
            // Argument Exception:  
            // "Item with Same Key has already been added" thrown =]
            ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
        }

        // We update the entry value
        entries[i].value = value;

        // Modification while iterating check field
        version++;

        return;
    } 
}

Примечание: поле version является полем, также используемым в других распространенных структурах данных .NET (например, List<T>), которые помогают обнаруживать при итерации (в MoveNext()) (и генерировать связанное исключение).

Шаг 4: проверьте, нужно ли изменять размеры массивов

// The entries location in which the data will be inserted
var index = 0;

// The freeCount field indicates the number of holes / empty slotes available for insertions.
// Those available slots are the results of prior removal operations
if (freeCount > 0) 
{
    // The freeList field points to the first hole (ie. available slot) in the entries
    index = freeList;
    freeList = entries[index].next;
    // The hole is no longer available
    freeCount--;
}
else 
{
    // The entries array is full 
    // Need to resize it to make it bigger
    if (count == entries.Length)
    {
        Resize();
        targetBucket = hashCode % buckets.Length;
    }
    index = count;
    count++;
}

Примечание: вызов about Resize():

• Он Double- представляет собой размер базовых массивов (buckets и entries), как и многие другие коллекции, чтобы избежать слишком большого количества операций изменения размера, предоставляя достаточно места при изменении размера коллекции.
• Double- >> ish <<, поскольку размер может быть только простым числом из предварительно вычисленного набора Int32 например. 3, 7, 11, 17 ,..., 7199369 так как использование простого может уменьшить количество столкновений (см. 7199369 ответ на SO)

На самом деле в начале метода Resize() новый размер вычисляется следующим образом:

public static int ExpandPrime(int oldSize)
{
    var min = 2 * oldSize;

    if ((uint) min > 2146435069U && 2146435069 > oldSize)
    {
        return 2146435069;
    }

    return HashHelpers.GetPrime(min);
}

Шаг 5: Добавьте запись

Поскольку словарь завершает проверку отверстий и размера, он может, наконец, добавить запись, используя вычисленный hashCode, key, value и правильный index, который только что был вычислен, и соответствующим образом скорректировать целевой блок:

entries[index].hashCode = hashCode;

// If the bucket already contained an item, it will be the next in the collision resolution chain.
entries[index].next = buckets[targetBucket];
entries[index].key = key;
entries[index].value = value;
// The bucket will point to this entry from now on.
buckets[targetBucket] = index;

// Again, modification while iterating check field
version++;

Бонус: специальная обработка струн

Цитируется из источника CodeProject, указанного ниже:

Чтобы убедиться, что каждая операция "получить" и "добавить" не будет превышать более 100 элементов для каждого сегмента, используется счетчик столкновений.

Если при обходе массива для поиска или добавления элемента счетчик столкновений превышает 100 (предел жестко IEqualityComparer) и IEqualityComparer имеет тип EqualityComparer<string>.Default, для альтернативной строки создается новый IEqualityComparer<string> алгоритм хеширования.

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

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

использование

Всякий раз, когда вы используете пользовательский тип в качестве ключа, не забывайте иметь собственный IEqualityComparer или переопределять два метода Object (hashcode + equal), чтобы впоследствии избежать неожиданностей при вставках.

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

Дополнительное примечание для интервьюируемых

Я хотел бы подчеркнуть тот факт, что знание деталей реализации для интервью, как правило, не имеет большого значения (фактическая реализация отличается от некоторых версий .NET("Обычная" или Core...), плюс все же могут быть подвержены изменениям )).

Если бы кто-то задал мне вопрос, я бы сказал:

• Ответ, который вы ищете, находится на StackOverflow :)
• Ответ, который вы ищете, также на
  • .NET Reference
  • Github -.NET Core
• Ответ, который вы ищете, не требует подробностей реализации и официальной документации здесь или там будет достаточно для большинства случаев использования.

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

Источники:

• .NET Reference - Исходный код
• Github -.NET Core - Исходный код
• Reddit - Eli5: как работает двойное хеширование в словарях .NET?
• ТАК - Как работает двойное хеширование в случае словаря .NET?
• Code Project - Понимание общего словаря в глубине
• Блог по программированию Марка Винча - Назад к основам: словарь, часть 1, хеш-таблицы
• Блог по программированию Марка Винча - Назад к основам: словарь, часть 2, реализация .NET

Ответ 4

Он использует hash, как практически каждая другая реализация словаря.

Ответ 5

Этот вопрос мне любопытно, поэтому я написал сверхбыструю оптимизированную версию словаря словаря, который 5x (пять раз) быстрее чем стандартная реализация .NET dictionary.

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

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

/// <summary>
/// Ultra fast dictionary, optimized for retrieval of keys consisting of 3-letter uppercase strings, where each string is 'A' to 'Z'.
/// This is 5 times faster than the default Dictionary<> implementation, but not as flexible.
/// ----start output from tester---
/// Ultra Fast Dictionary.
///   Total time for 2,000,000,000 key retrievals: 19,892 milliseconds. 0.00994600 nanoseconds per retrieval. Sum -1958822656.
/// Normal Dictionary.
///   Total time for 2,000,000,000 key retrievals: 98,397 milliseconds. 0.04919850 nanoseconds per retrieval. Sum -1958822656.
/// ----end output from tester---
/// </summary>
public class DictionaryUltraFast
{
    string[][][] dictionary;

    /// <summary>
    /// Add a string to the dictionary.
    /// </summary>
    public void Add(string key, string value)
    {
        key = key.ToUpper();
        if (dictionary == null)
        {
            dictionary = new string['Z' - 'A' + 1][][];
        }
        if (dictionary[key[0] - 'A'] == null)
        {
            dictionary[key[0] - 'A'] = new string['Z' - 'A' + 1][];
        }
        if (dictionary[key[0] - 'A'][key[1] - 'A'] == null)
        {
            dictionary[key[0] - 'A'][key[1] - 'A'] = new string['Z' - 'A' + 1];
        }
        dictionary[key[0] - 'A'][key[1] - 'A'][key[2] - 'A'] = value;
    }

    public string Get(string key)
    {
        return dictionary[key[0] - 'A'][key[1] - 'A'][key[2] - 'A'];
    }
}