Вопрос по hashtable, c#, .net – .NET HashTable Vs Dictionary - Может ли словарь быть таким же быстрым?

259

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

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

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

Я бы хотел это подтвердить, но ваша карма составляет 7 777, и я не хочу быть тем парнем, который все испортил для вас. CaptainMarvel

Ваш Ответ

10   ответов
1

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

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

15

MSDN Article: "The Dictionary<TKey, TValue> class has the same functionality as the Hashtable class. A Dictionary<TKey, TValue> of a specific type (other than Object) has better performance than a Hashtable for value types because the elements of Hashtable are of type Object and, therefore, boxing and unboxing typically occur ,if storing or retrieving a value type".

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

105

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

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

2

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

285

System.Collections.Generic.Dictionary<TKey, TValue> а такжеSystem.Collections.Hashtable оба класса поддерживают структуру данных хеш-таблицы внутри.None of them guarantee preserving the order of items.

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

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

Там мало пользы для использованияHashtable класс, если вы ориентируетесь на .NET Framework 2.0+. Он фактически устарелDictionary<TKey, TValue>.

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

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

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

Hashtable, provide some thread-safety through the Synchronized property, which returns a thread-safe wrapper around the collection. The wrapper works by locking the entire collection on every add or remove operation. Therefore, each thread that is attempting to access the collection must wait for its turn to take the one lock. This is not scalable and can cause significant performance degradation for large collections. Also, the design is not completely protected from race conditions.

The .NET Framework 2.0 collection classes like List<T>, Dictionary<TKey, TValue>, etc do not provide any thread synchronization; user code must provide all synchronization when items are added or removed on multiple threads concurrently If you need type safety as well thread safety, use concurrent collections classes in the .NET Framework. Further reading here.

-1

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

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

Differences between Hashtable and Dictionary

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

  • Dictionary returns error if we try to find a key which does not exist.
  • Dictionary faster than a Hashtable because there is no boxing and unboxing.
  • Dictionary is a generic type which means we can use it with any data type.

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

  • Hashtable returns null if we try to find a key which does not exist.
  • Hashtable slower than dictionary because it requires boxing and unboxing.
  • Hashtable is not a generic type,
23

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

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

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

Похожие вопросы