С# Hashtable Внутренняя структура данных
Все -
Запрашивая конкретный вопрос, который я кулак недавно и на удивление не нашел убедительного ответа.
Какова структура данных внутренней поддержки, которую С# Hashtable (и словарь - который использует Hashtable внутри) использует
Итак, в сущности, какие ведра представляют собой пары ключевых значений, хранящихся в - ArrayList, LinkedList (который, как я знаю, не является ответом здесь), древовидная структура и т.д.
Не искать стратегии столкновения и т.д. - просто после вычисления хэш-кода - какая структура данных использует Hashtable для внутреннего использования для хранения этого значения?
Любые объяснения или указатели на статьи действительно помогут.
Ответы
Ответ 1
Существует хорошее объяснение внутренней структуры данных словаря:
https://www.simple-talk.com/blogs/2011/09/16/the-net-dictionary/, то же самое происходит для HashTable
В двух словах
hashtable состоит из двух массивов: ведра и записи
При добавлении элемента хеш-код генерируется по модулю текущего размера массива и определяет интервал, в котором хранится элемент.
Однако этот слот не тот, который находится в записях, это фактически тот, который находится в ведрах.
Значение в ведрах хэшированного индекса - это индекс слота в записях, которые фактически хранятся в памяти, и который просто присваивается следующему свободному слоту в массиве.
Ответ 2
System.Collections.Hashtable определяет настраиваемую структуру (ведро) для хранения информации о ключе, значении и коллизии и хранит простой массив экземпляров этой структуры.
System.Collections.Generic.Dictionary использует одну и ту же стратегию, хотя с типичными типами вместо object. Общий Dictionary не использует не-общий Hashtable, хотя они работают аналогично.
