Как мы знаем, существует 2 классических стратегии разрешения конфликтов: отдельная цепочка и открытая адресация.
Мне интересно, какой из них был выбран для HashTable / Dictionary в .net.
Или была использована какая-то другая стратегия?
Все это описано в этой статье на MSDN: Обширный анализ структур данных с использованием C # 2.0
... метод разрешения коллизий, называемый рефазингом, который является техникойиспользуется классом Hashtable .NET Framework.В последнем разделе мы рассмотрим класс Dictionary, в котором используется метод разрешения коллизий, называемый цепочкой..... ... Реазинг работает следующим образом: существует набор хеш-функций, H1 ... Hn, и при вставке или извлечении элемента из хеш-таблицы изначально хеш-функция H1используется.Если это приводит к столкновению, вместо этого пробуется H2, и далее до Hn, если необходимо.В предыдущем разделе была показана только одна хеш-функция, которая является начальной хеш-функцией (H1).Другие хеш-функции очень похожи на эту функцию, дифференцируются только по мультипликативному коэффициенту.В общем, хеш-функция Hk определяется как:
... метод разрешения коллизий, называемый рефазингом, который является техникойиспользуется классом Hashtable .NET Framework.В последнем разделе мы рассмотрим класс Dictionary, в котором используется метод разрешения коллизий, называемый цепочкой.....
... Реазинг работает следующим образом: существует набор хеш-функций, H1 ... Hn, и при вставке или извлечении элемента из хеш-таблицы изначально хеш-функция H1используется.Если это приводит к столкновению, вместо этого пробуется H2, и далее до Hn, если необходимо.В предыдущем разделе была показана только одна хеш-функция, которая является начальной хеш-функцией (H1).Другие хеш-функции очень похожи на эту функцию, дифференцируются только по мультипликативному коэффициенту.В общем, хеш-функция Hk определяется как:
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
Класс Dictionary отличается от класса Hashtable во многих отношениях, чем один.Помимо строгой типизации, Словарь также использует другую стратегию разрешения коллизий, чем класс Hashtable, используя технику, называемую сцеплением.Напомним, что при зондировании в случае коллизии пробуется другой слот в списке сегментов.(При перефразировании хэш пересчитывается и пробуется этот новый слот.) Однако при связывании вторичная структура данных используется для хранения любых коллизий.В частности, каждый слот в Словаре имеет массив элементов, которые отображаются на этот сегмент.В случае коллизии, элемент коллизии добавляется к списку сегмента.
Помните, что только первое предложение - мое собственное: -)
Это действительно очень интересный вопрос; Я только что написал сообщение в блоге о том, как Dictionary реализовано за кадром. Я могу покрыть Hashtable позже.
Dictionary
Hashtable