Как процесс хэширования работает в словаре? Я читал, что использование словаря обеспечивает быстрый поиск. Но не понял, как? Как происходит хеширование и отображение индекса? Не удалось найти хорошую ссылку.
EDIT: Как фактическое место памяти, в котором объект хранится, полученным из результата хеширования?
Процесс хеширования в словаре использует технику, называемую цепочкой. При цепочке используется вторичная структура данных для проведения любых столкновений. В частности, каждый слот в словаре содержит массив элементов, которые сопоставляются с ведром. В случае столкновения встречный элемент добавляется к списку ведер.
Подробнее см. эту статью в MSDN.
Хеш-таблица или словарь - это структура данных, в которой хранятся пары ключ-значение. Преимущество хеш-таблицы в том, что при заданном ключе найти соответствующее значение довольно быстро. Упрощенно, время нахождения пары ключ-значение в хеш-таблице не зависит от размера таблицы. Сравните это с хранением пар ключ-значение в списке или массиве. Чтобы найти пару ключ-значение, вам придется искать в списке с самого начала, пока не будет найден соответствующий ключ. Чем длиннее список, тем больше времени потребуется для поиска пары ключ-значение. Используя нотацию big-O, вы можете сказать, что поиск ключа в хеш-таблице имеет порядок O (1), а поиск ключа в списке с помощью линейного поиска имеет порядок O (N) (упрощенно).
Чтобы вставить пару ключ-значение в хеш-таблицу, вам сначала нужно будет вычислить хеш-код ключа. В .NET все объекты имеют метод с именем GetHashCode который возвращает хеш-код (32-разрядное целое число) для этого конкретного объекта. Важно, чтобы равные объекты возвращали один и тот же хэш-код, но также очень полезны, если разные объекты возвращают разные хэш-коды. Остерегайтесь неправильного представления о том, что разные объекты не могут возвращать один и тот же хеш-код - они могут, но это приведет к коллизии (см. Ниже).
В качестве примера рассмотрим хеш-коды двух строк:
"Boo" 0x598FD95A "Foo" 0x598FD8DE
Несмотря на то, что строки очень похожи, они имеют разные хэш-коды.
Здесь я немного упростил ситуацию, чтобы сосредоточиться на важных аспектах хеш-таблицы, поэтому сейчас допустим, что Internally Dictionary<TKey, TValue> хранит пары ключ-значение в массиве. Чтобы найти индекс в этом массиве, где будет храниться пара ключ-значение, вы должны вычислить хеш-код ключа по модулю размера массива. Предположим, что размер массива равен 5:
Index("Boo") = 0x598FD95A % 5 = 4
Index("Foo") = 0x598FD8DE % 5 = 0
Это приводит к этому внутреннему массиву хеш-таблиц:
+---+---------+ | 0 | "Foo" | +---+---------+ | 1 | (empty) | +---+---------+ | 2 | (empty) | +---+---------+ | 3 | (empty) | +---+---------+ | 4 | "Boo" | +---+---------+
Поиск записи в хеш-таблице выполняется очень быстро. Вам просто нужно вычислить хеш-код ключа по модулю размера внутреннего массива и извлечь строку с этим индексом.
Теперь рассмотрим ключ "Зоопарк":
Index("Zoo") = 0x598FDC62 % 5 = 0
Он имеет тот же индекс, что и ключ "Foo". Это приводит к тому, что называется коллизиям. Надлежащая реализация хеш-таблицы должна обрабатывать коллизии, и для этого существуют разные стратегии. Кроме того, по мере заполнения внутреннего массива в массиве будет все меньше и меньше пустых элементов, что приведет к увеличению числа коллизий. Коэффициент загрузки - это соотношение между используемыми элементами и общим количеством элементов во внутреннем массиве. В приведенном выше примере коэффициент загрузки равен 2/5 = 0,4. В большинстве реализаций хеш-таблиц размер внутреннего массива увеличивается, когда коэффициент загрузки превышает определенный порог.
Если вы хотите узнать больше о некоторых из этих концепций, вам придется изучить некоторые из более полных ресурсов, связанных в других ответах.
Используя концепцию Computer Science, называемую Hash Map. Это работает быстрее, чем поиск в списке. Это работает, сохраняя поиск от необходимости перебирать список до тех пор, пока не найдет совпадение. Вместо этого ключ " hashed" и используется как индекс в списке. Эта функция хэширования почти всегда быстрее, чем поиск в списке (повторение нескольких сравнений).
Обычно, принимая значение хэш-значения% array size, которое может вызвать столкновение.
Словарь использует хешированные ключи для поиска, как я пытался объяснить в своем ответе на другой ваш вопрос. Таким образом, если у вас есть пользовательский тип объекта в качестве ключа, все зависит от реализации GetHashCode() вашего пользовательского объекта.