Небольшая резюмирующая заметка про различия между Dictionary и Hashtable в .NET.
Во-первых, словари быстрее для типов значений (т. е. структур: int, float и пр.). В блоге некоего Криса Ньюмана нашел простой и наглядный тест сравнения скорости. HashTable рассчитана на работу с объектами, а не типами значений. Поэтому такие типы будут постоянно упаковываться и распаковываться при работе с таблицей. Если в качестве ключей нужны простые значения, надо использовать словарь.
Ещё одно преимущество словаря — строгая типизация хранимых пар ключ-значение. Это намного удобнее в работе в большинстве случаев.
В случае с объектами всё несколько ровнее. Для эффективной работы хэш-таблицы, необходима полноценная реализация метода GetHashCode, которая для каждого объекта будет создавать уникальный хэш. Уникальность не обязательна, но ускоряет работу. Согласно статье MSDN хэш-таблица сегментирует объекты-значения, ассоциируя их с некоторыми группами кодов. Это может сильно ускорить поиск объекта: будет получен код образца, дальше определён сегмент, а уже в нём будет произведён поиск, а не по всей таблице.
С точки зрения организации внутренних структур словари работают примерно так же, как и хеш-таблицы. Но за счёт использования последовательностей для разрешения конфликтов (короче, когда признак ключа уже есть в таблице) вместо рехеширования, словари обеспечивают поиск с постоянной скоростью — O(1). Хэш-таблица в случае обнаружения существующего хэша, идёт к следующей ячейке до тех пор, пока не найдёт ближайшую свободную. Словарь же просто прикрепляет дубликат в конец цепочки с элементами, попавшими на этот сегмент. При этом в словаре число элементов никогда не превышает число выделенных сегментов. В случае устранения узких мест, это хороший намёк на оценку возможности перейти от словаря к хеш-таблице, но это задача промышленных проектов, где хорошая архитектура чаще решает такую проблему. Зато, что намного актуальнее: если используются объекты и хэш-метод может возвращать неуникальные коды, то использование словарей тем предпочтительнее, чем выше шанс дубликатов. Фактически, если явно функция хеширования не определена, то хэш зависит исключительно от типа объекта (поведение метода в реализации класса Object), и таблица в данном случае будет очень неэффективна.
Последнее замечание, на счет словарей и перечислений. Когда в словарь добавляется очень много записей с Enum в качестве ключа, словарь работает очень медленно. Для ускорения нужно добавить немного кода, который сгладил бы различие с обычным типом-значением, либо подставлять соответствующее int-значение вместо оригинального значения. В развёрнутой статье — “Accelerating Enum-Based Dictionaries with Generic EnumComparer” — всё это подробно объясняется и есть код под. NET 2.0 и 3.5. Если вкратце: по умолчанию для добавления 1 млн. записей требуется 533 мс, что в 10 раз дольше использования int-значения. Если вариант с int по каким-то причинам неудобен, надо реализовать свой Comparer. Правда, у такой ситуации особенность: она очень редкая.
Подробнее вопрос организации внутренних структур коллекций в. NET разобран в отличной статье — “An Extensive Examination of Data Structures Using C# 2.0”.