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

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

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

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

6.07.2009 20:46:22
Я бы не хотел этого высказывать, но ваша карма составляет 7 777, и я не хочу быть тем парнем, который все испортил.
CaptainMarvel 29.05.2018 14:51:01
10 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

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

295
7.07.2009 20:33:52
@ Jon - Цепочка и перефразировка подробно обсуждаются здесь
RichardOD 6.07.2009 20:52:17
Спасибо вам обоим. Только что нашел эту страницу, как ее разместил Ричард ... Я собирался спросить о Цепи, но сайт MSDN действительно полезен!
Jon 6.07.2009 20:56:52
@Mehrdad - Что мне не ясно в том, как разрешаются коллизии, так это: если несколько ключей могут привести к одному и тому же хешу, то как вы гарантируете, что получаете правильные значения при поиске, т.е. как функция узнает, какой элемент возвращение? В msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx говорится: «Вместо того, чтобы делать ребробировку в случае коллизии, как это делается с классом Hashtable, словарь просто связывает любые коллизии в список ведра. " Означает ли это, что при использовании словаря разработчикам не нужно беспокоиться о коллизиях?
Howiecamp 2.02.2010 03:26:31
@Howiecamp: Это не сильно отличается от Hashtable. В хеш-таблицах хранится 3 элемента информации: хеш-ключ, сам ключ и значение. Для элементов с одинаковым хешем придется пройти по списку, чтобы найти элемент с равным ключом и вернуть его значение. Это в значительной степени верно и для Hashtableтоже. Как разработчик, использующий Dictionaryобычно, вам не нужно беспокоиться об этом.
Mehrdad Afshari 2.02.2010 11:32:52
@ Mehrdad Просто чтобы прояснить: оба объекта Hashtable и Dictionary хранят сам ключ, и оба также скрывают коллизии от разработчика?
Howiecamp 5.02.2010 05:33:51

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

11
6.07.2009 20:50:43

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

24
14.03.2010 16:45:53
Словарь параллельной поддержки будет поддерживать (.Net 4.0)
Tamilmaran 6.02.2012 04:35:18
Я не уверен, что понимаю этот ответ. Посмотрите здесь msdn.microsoft.com/en-us/library/… там написано: «Для поддержки нескольких писателей все операции над Hashtable должны выполняться через оболочку, возвращаемую методом Synchronized, при условии, что нет потоков, читающих объект Hashtable. " Похоже, это делает функцию «без блокировки нескольких читателей» довольно бесполезной, поэтому мы снова вынуждены блокировать весь доступ к Hashtable, как и в словаре.
RenniePet 16.09.2015 22:37:02

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

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

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

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

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

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

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

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

110
22.10.2019 13:14:06
Очень интересно, что отсортированный список имеет более быстрый поиск, чем хеш-таблица. Я думал, что хеш-таблица O (1) против отсортированного списка O (logn). Видимо хэш-таблица отстой. Я никогда не буду использовать это.
John Henckel 10.01.2020 14:32:42
@JohnHenckel нет, отсортированный список имеет более медленный поиск. Большой коэффициент производительности означает лучшую производительность и лучшее использование памяти. Таким образом, отсортированный список имеет лучшее использование памяти в соответствии с графиками, но он сосет в других областях, таких как вставка и поиск.
C0DEF52 5.02.2020 08:58:41

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

0
15.03.2012 06:24:40
phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx Пожалуйста, прочитайте комментарии под статьей
Arvand 1.05.2012 07:00:47
@Arvand Ссылка не работает - домен для продажи.
RenniePet 16.09.2015 22:21:49

Статья 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

16
3.09.2015 12:56:16

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

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

1
23.10.2013 08:01:42

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

Толковый словарь:

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

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

  • Hashtable возвращает ноль, если мы пытаемся найти ключ, который не существует.
  • Hashtable медленнее, чем словарь, потому что он требует упаковки и распаковки.
  • Hashtable не является универсальным типом,
30
6.01.2015 12:21:43

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

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

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

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

8
12.11.2015 15:11:32

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

3
13.11.2018 03:51:17