1

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

2

1 ответ 1

2

Пишу по памяти.

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.