Всем привет, есть вопрос касательно внутреннего устройства Dictionary в С#. При инициализации Dictionary в нём создаются 2 внутренних массива buckets и entries. Как я понимаю их размер равен между собой(если что поправьте) и является ближайшим простым числом(3 например), при добавлении элемента мы высчитываем с него хэш-код специальной хэш-функцией которая является реализацией GetHashCode() объекта-ключа. И далее этот хэш-код с помощью модуля от размера словаря. Но я немного не понимаю что именно за индекс мы получаем - индекс в buckets или в entries? Если в buckets, то откуда берется индекс в entries? И правильно ли я понимаю что структура Entry - это по сути узел односвязного списка?
1 ответ
Пишу по памяти.
- Да, размер buckets и entries совпадает.
- Размер buckets является ближайшим простым числом, которое вдвое больше предыдущей ёмкости словаря (перед последним увеличением словаря).
- Да, хэш-функцией является реализацией GetHashCode() объекта-ключа, в тех случаях, когда в словарь не передан специальный класс для сравнения объектов. Если такой объект передан, то используется его функции GetHashCode и Equals.
- После взятия остатка от деления хэша на ёмкость, мы получаем индекс в buckets - собственно хэш-карте.
- Индекс элемента в entries, хранится в ячейке buckets - на то она и хэш-карта.
- Да, в entries хранятся узлы односвязного списка коллизий по сути дела. Ещё это может быть узел списка дырок, появившихся при удалении ключей. И наконец просто свободная ячейка в незанятой части массива.