.NET HashTable Vs Dictionary - Может ли словарь быть таким же быстрым?

276

Я пытаюсь выяснить, когда и зачем использовать словарь или HashTable. Я провел здесь небольшой поиск и обнаружил, что люди говорят о типичных преимуществах Словаря, с которыми я полностью согласен, что приводит к преимуществам бокса и распаковки для небольшого прироста производительности.

Но я также читал, что Словарь не всегда возвращает объекты в том порядке, в котором они вставлены, вещь, которую он сортирует. Где как HashTable будет. Насколько я понимаю, это приводит к тому, что HashTable в некоторых ситуациях работает намного быстрее.

Мой вопрос действительно, что может быть в таких ситуациях? Я просто ошибаюсь в своих предположениях выше? Какие ситуации вы могли бы использовать, чтобы выбрать одно над другим (да, последнее немного неоднозначно).

Джон
источник
5
Я бы не хотел этого высказывать, но ваша карма составляет 7 777, и я не хочу быть тем парнем, который все испортил.
Капитан Марвел

Ответы:

298

System.Collections.Generic.Dictionary<TKey, TValue>и System.Collections.Hashtableклассы поддерживают структуру данных хеш-таблицы внутри. Ни один из них не гарантирует сохранение порядка товаров.

Если оставить в стороне проблемы с боксом / распаковкой, большую часть времени они должны иметь очень похожую производительность.

Основное структурное различие между ними является то , что Dictionaryзависит от цепочки (сохранения списка элементов для каждого хеша - таблицу ведра) для разрешения коллизий в то время как Hashtableиспользования Rehashing для разрешения конфликтов (когда происходит столкновение, пытается другой хэш - функция для отображения ключа в ведро) ,

Использование Hashtableкласса малоэффективно, если вы ориентируетесь на .NET Framework 2.0+. Это фактически оказано устаревшим Dictionary<TKey, TValue>.

Мехрдад Афшари
источник
21
@ Jon - Цепочка и перефразировка подробно обсуждаются здесь
msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx
Спасибо вам обоим. Просто нашел эту страницу, как ее разместил Ричард ... Я собирался спросить о Цепи, но сайт MSDN действительно полезен!
Джон
6
@Mehrdad - Что мне не понятно в том, как разрешаются коллизии, так это: если несколько ключей могут привести к одному и тому же хешу, то как вы гарантируете, что при поиске вы получаете правильное значение, т.е. как функция узнает, какой элемент возвращение? В msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx говорится: «Вместо того, чтобы делать ребробировку в случае коллизии, как это делается с классом Hashtable, словарь просто связывает любые коллизии в список ведра. " Означает ли это, что при использовании словаря разработчикам не нужно беспокоиться о коллизиях?
Howiecamp
6
@Howiecamp: Это не сильно отличается от Hashtable. В хеш-таблицах хранится 3 элемента информации: хеш-ключ, сам ключ и значение. Для элементов с одинаковым хешем придется пройти по списку, чтобы найти элемент с равным ключом и вернуть его значение. Это в значительной степени верно и для Hashtableтоже. Как разработчик, использующий Dictionaryобычно, вам не нужно беспокоиться об этом.
Мердад Афшари
@ Mehrdad Чтобы было ясно, оба объекта Hashtable и Dictionary хранят сам ключ, и оба также скрывают коллизии от разработчика?
Howiecamp
111

Я думаю, это ничего не значит для вас сейчас. Но только для справки для людей, заходящих

Тест производительности - SortedList и SortedDictionary, словарь и Hashtable.

Выделение памяти:

Тест производительности использования памяти

Время, используемое для вставки:

Время, используемое для вставки

Время поиска предмета:

Время поиска предмета

Абдул Муним
источник
Очень интересно, что отсортированный список имеет более быстрый поиск, чем хеш-таблица. Я думал, что хеш-таблица O (1) против отсортированного списка O (logn). Видимо хэш-таблица отстой. Я никогда не буду использовать это.
Джон Хенкель
@JohnHenckel нет, отсортированный список имеет более медленный поиск. Большой коэффициент производительности означает лучшую производительность и лучшее использование памяти. Таким образом, отсортированный список имеет лучшее использование памяти в соответствии с графиками, но он сосет в других областях, таких как вставка и поиск.
C0DEF52
31

Различия между Hashtable и словарем

Словарь:

  • Словарь возвращает ошибку, если мы пытаемся найти ключ, который не существует.
  • Словарь быстрее, чем Hashtable, потому что нет никакого бокса и распаковки.
  • Словарь - это универсальный тип, который означает, что мы можем использовать его с любым типом данных.

Хеш-таблица:

  • Hashtable возвращает ноль, если мы пытаемся найти ключ, который не существует.
  • Hashtable медленнее, чем словарь, потому что он требует упаковки и распаковки.
  • Hashtable не является универсальным типом,
user2771704
источник
24

Еще одно важное отличие состоит в том, что тип Hashtable поддерживает одновременную работу нескольких читателей и одного писателя, в то время как Dictionary - нет.

Стивен
источник
8
Словарь параллельной поддержки будет поддерживать (.Net 4.0)
Тамилмаран,
1
Я не уверен, что понимаю этот ответ. Посмотрев здесь msdn.microsoft.com/en-us/library/… там сказано: «Для поддержки нескольких писателей все операции над Hashtable должны выполняться через оболочку, возвращаемую методом Synchronized, при условии, что нет потоков, читающих объект Hashtable. " Похоже, это делает функцию «без блокировки нескольких читателей» довольно бесполезной, поэтому мы снова вынуждены блокировать весь доступ к Hashtable, как и в словаре.
Ренни Пет
16

Статья MSDN: « Dictionary<TKey, TValue>Класс имеет те же функциональные возможности, что и Hashtableкласс. A Dictionary<TKey, TValue> определенного типа (отличного от Object) имеет лучшую производительность, чем Hashtableтипы значений, потому что элементы Hashtableимеют тип, Objectи, следовательно, упаковка и распаковка обычно происходят при хранении или извлечение типа значения ".

Ссылка: http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.90).aspx

Хуан Камило Каро Дж.
источник
11

Оба по сути одного класса (вы можете посмотреть на разборку). HashTable был создан первым до того, как в .Net появились дженерики. Словарь, однако, является общим классом и дает вам сильные преимущества при наборе текста. Я бы никогда не использовал HashTable, так как Словарь ничего не стоит.

Адам Лютер
источник
8

Другое важное отличие - это Hashtableпотокобезопасность. Hashtableимеет встроенную безопасность потоков для нескольких считывателей / писателей (MR / SW), что означает, что Hashtableпозволяет ОДНОМ записывать вместе с несколькими считывателями без блокировки В случае Dictionaryотсутствия безопасности потоков, если вам нужна безопасность потоков, вы должны реализовать собственную синхронизацию.

Чтобы уточнить дальше:

Hashtable, обеспечить некоторую поточную безопасность через свойство Synchronized, которое возвращает поточно-ориентированную оболочку вокруг коллекции. Оболочка работает, блокируя всю коллекцию при каждой операции добавления или удаления. Поэтому каждый поток, который пытается получить доступ к коллекции, должен ждать своей очереди, чтобы взять одну блокировку. Это не масштабируется и может привести к значительному снижению производительности для больших коллекций. Кроме того, дизайн не полностью защищен от условий гонки.

Классы коллекций .NET Framework 2.0, такие как List<T>, Dictionary<TKey, TValue>и т. Д., Не обеспечивают никакой синхронизации потоков; Пользовательский код должен обеспечивать всю синхронизацию при одновременном добавлении или удалении элементов в нескольких потоках. Если вам нужна безопасность типов, а также безопасность потоков, используйте классы одновременных коллекций в .NET Framework. Дальнейшее чтение здесь.

NullReference
источник
3

Преимущество словарей состоит в том, что они являются универсальными, что делает их безопасными и немного более быстрыми из-за отсутствия необходимости в боксе. Следующая таблица сравнения (построенная с использованием ответов, найденных в аналогичном посте с вопросом о SO ) иллюстрирует некоторые другие причины, которые поддерживают словари для хеш-таблиц (или наоборот).

janeon
источник
1

Если вы заботитесь о чтении, которое всегда возвращает объекты в том порядке, в котором они вставлены в словарь, вы можете взглянуть на

OrderedDictionary - доступ к значениям осуществляется через целочисленный индекс (по порядку, в котором были добавлены элементы). SortedDictionary - элементы сортируются автоматически

ToXinE
источник
0

Словарь быстрее, чем хеш-таблица, так как словарь является универсальным строгим типом. Hashtable работает медленнее, так как принимает объект как тип данных, что приводит к упаковке и распаковке.

Джитендра Махапатро
источник
2
phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx Пожалуйста, прочитайте комментарии под статьей
Арванд
4
@Arvand Ссылка не работает - домен для продажи.
RenniePet,