Почему словарь предпочтительнее Hashtable в C #?

В большинстве языков программирования словари предпочтительнее хеш-таблиц. Каковы причины этого?

19.11.2008 09:24:24
> Это не обязательно правда. Хеш-таблица - это реализация словаря. Типичный для этого, и он может быть по умолчанию в .NET, но по определению он не единственный. Я не уверен, что это требуется стандартом ECMA, но документация MSDN очень четко указывает на то, что он реализован как хеш-таблица. Они даже предоставляют класс SortedList для случаев, когда альтернатива более разумна.
Promit 17.04.2009 04:57:34
@ Я всегда думал, что Dictionaryэто реализация Hashtable.
b1nary.atr0phy 21.03.2015 09:30:33
Я думаю, причина в том, что в словаре вы можете определить тип ключа и значение для себя. Hashtable может принимать только объекты и сохранять пары на основе хеша (из object.GetHashCode ()).
Radinator 4.08.2016 09:17:20
@Dan Ваша заявка совершенно ошибочна ... хеш-таблица содержит только один экземпляр каждого ключа, и поиск никогда не дает нескольких записей; если вы хотите связать несколько значений с каждым ключом, сделайте значение хеш-таблицы списком значений. Нет такой структуры данных, как «словарь» ... Словарь - это просто имя, которое некоторые библиотеки используют для своей хэш-таблицы. например, вызывается неуниверсальная хеш-таблица C # HashTable. Когда они добавили дженерики в язык, они назвали дженериковую версию Dictionary. Оба хеш-таблицы.
Jim Balter 3.11.2018 16:58:42
@Dan Ваше утверждение ошибочно ... хеш-таблица ( en.wikipedia.org/wiki/Hash_table ) представляет собой конкретную реализацию словаря, также называемого ассоциативным массивом ( en.wikipedia.org/wiki/Associative_array ), и, будучи словарь, содержит только один экземпляр каждого ключа, и поиск никогда не дает нескольких записей; если вы хотите связать несколько значений с каждым ключом, сделайте значение хеш-таблицы списком значений. И классы .NET Dictionary, и классы Hashtable являются хеш-таблицами.
Jim Balter 3.11.2018 17:32:30
19 ОТВЕТОВ
РЕШЕНИЕ

Для чего это стоит, словарь , является (концептуально) хэш - таблицу.

Если вы имели в виду «почему мы используем Dictionary<TKey, TValue>класс вместо Hashtableкласса?», То это простой ответ: Dictionary<TKey, TValue>это универсальный тип, а Hashtableне. Это означает, что вы получаете безопасность типов Dictionary<TKey, TValue>, потому что вы не можете вставить в нее какой-либо случайный объект и вам не нужно приводить значения, которые вы вынимаете.

Интересно, что Dictionary<TKey, TValue>реализация в .NET Framework основана на Hashtable, как вы можете сказать из этого комментария в его исходном коде:

Общий словарь был скопирован из источника Hashtable

Источник

1560
15.12.2017 12:52:41
А также общие коллекции намного быстрее, так как здесь нет бокса / распаковки
Chris S 26.01.2009 12:45:40
Не уверен насчет Hashtable с вышеуказанным оператором, но для ArrayList vs List <t> это правда
Chris S 26.01.2009 12:46:52
Hashtable использует Object для внутреннего хранения вещей (только не универсальный способ сделать это), поэтому он также должен был бы включать / отключать.
Guvante 17.04.2009 05:29:54
@BrianJ: «хэш-таблица» (два слова) - это термин в области компьютерных наук для такой структуры; Словарь - это конкретная реализация. HashTable примерно соответствует Dictionary <объект, объект> (хотя и с немного отличающимися интерфейсами), но оба являются реализациями концепции хеш-таблицы. И, конечно, просто чтобы еще больше сбить с толку, некоторые языки называют свои хеш-таблицы «словарями» (например, Python), но правильным термином CS по-прежнему является хеш-таблица.
Michael Madsen 20.06.2013 17:57:22
@BrianJ: И HashTable(класс), и Dictionary(класс) являются хеш-таблицами (концепция), но a HashTableне является Dictionaryи не является Dictionarya HashTable. Они используются очень похожими способами и Dictionary<Object,Object>могут действовать таким же нетипизированным способом, что и a HashTable, но они напрямую не делятся каким-либо кодом (хотя части, вероятно, будут реализованы очень похожим образом).
Michael Madsen 20.06.2013 21:00:16

Потому Dictionaryчто это обобщенный класс ( Dictionary<TKey, TValue>), поэтому доступ к его содержимому безопасен для типов (т. Е. Вам не нужно Objectприводить из , как в случае с Hashtable).

сравнить

var customers = new Dictionary<string, Customer>();
...
Customer customer = customers["Ali G"];

в

var customers = new Hashtable();
...
Customer customer = customers["Ali G"] as Customer;

Тем не менее, Dictionaryвнутренне реализовано как хеш-таблица, поэтому технически она работает так же.

178
19.02.2019 20:58:45

В .NET разница между Dictionary<,>и HashTableв первую очередь заключается в том, что первый тип является универсальным типом, так что вы получаете все преимущества универсальных типов с точки зрения статической проверки типов (и сокращения объема упаковки, но это не так велико, как люди думают в Условия исполнения - для бокса есть определенная стоимость памяти).

68
19.11.2008 09:54:50

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

14
14.09.2015 05:19:47

К сведению: В .NET Hashtableявляется поточно-ориентированным для использования несколькими потоками считывателей и одним потоком записи, в то время как в Dictionaryобщедоступных статических членах они являются поточно-ориентированными, но не гарантируется, что все члены экземпляра будут поточно-ориентированными

Из-за этого нам пришлось изменить все наши словари Hashtable.

88
23.10.2017 08:00:20
Весело. Исходный код Dictionary <T> выглядит намного чище и быстрее. Возможно, лучше использовать словарь и реализовать собственную синхронизацию. Если чтение словаря должно быть актуальным, вам просто нужно синхронизировать доступ к методам чтения / записи словаря. Было бы много блокировок, но это было бы правильно.
Triynko 14.05.2010 18:09:20
В качестве альтернативы, если ваши чтения не должны быть абсолютно актуальными, вы можете рассматривать словарь как неизменяемый. Затем вы можете получить ссылку на словарь и повысить производительность, вообще не синхронизируя чтение (поскольку оно является неизменным и по своей сути поточно-ориентированным). Чтобы обновить его, вы создаете полную обновленную копию словаря в фоновом режиме, а затем просто меняете ссылку на Interlocked.CompareExchange (при условии, что один поток записи; несколько потоков записи потребуют синхронизации обновлений).
Triynko 14.05.2010 18:15:40
В .Net 4.0 добавлен ConcurrentDictionaryкласс, в котором все открытые / защищенные методы реализованы как поточно-ориентированные. Если вам не нужно поддерживать устаревшие платформы, это позволит вам заменить Hashtableмногопоточный код: msdn.microsoft.com/en-us/library/dd287191.aspx
Dan Is Fiddling By Firelight 27.01.2012 20:49:56
Аноним на помощь. Классный ответ.
unkulunkulu 11.03.2012 21:34:17
Я вспоминаю, что читал, что HashTable является поточно-ориентированным для чтения и записи только в сценарии, где информация никогда не удаляется из таблицы. Если читатель запрашивает элемент, который находится в таблице, в то время как другой элемент удаляется, и читатель будет искать этот элемент более чем в одном месте, возможно, что во время поиска читателем писатель может переместить элемент из места, которое не было исследовано, в место, которое, таким образом, привело к ложному сообщению о том, что предмет не существует.
supercat 13.11.2013 23:03:03

Люди говорят, что словарь такой же, как хеш-таблица.

Это не обязательно правда. Хеш-таблица является одним из способов реализации словаря. Типичный для этого, и он может быть по умолчанию в .NET в Dictionaryклассе, но по определению он не единственный.

С таким же успехом вы могли бы реализовать словарь, используя связанный список или дерево поиска, это было бы не так эффективно (по некоторым показателям эффективности).

34
19.02.2019 21:04:46
Документы MS гласят: «Получение значения с использованием его ключа выполняется очень быстро, близко к O (1), потому что класс Dictionary <(Of <(TKey, TValue>)>) реализован в виде хеш-таблицы». - так что вам нужно гарантировать хеш-таблицу при работе с Dictionary<K,V>. IDictionary<K,V>может быть все что угодно :)
snemarch 23.09.2010 13:52:44
@ rix0rrr - я думаю, что вы поняли это, словарь использует HashTable, а не HashTable использует словарь.
Joseph Hamilton 9.08.2011 17:22:25
@JosephHamilton - rix0rrr правильно понял: «Хеш-таблица - это реализация словаря ». Он имеет в виду понятие «словарь», а не класс (обратите внимание на нижний регистр). Концептуально хеш-таблица реализует интерфейс словаря. В .NET словарь использует хеш-таблицу для реализации IDictionary. Это грязно;)
Robert Hensing 8.03.2013 09:38:58
Я говорил об этом в .NET, поскольку именно на это он ссылался в своем ответе.
Joseph Hamilton 14.10.2014 19:56:03
@JosephHamilton: реализация (или реализация ) даже отдаленно не означает то же самое, что и использование . Наоборот. Возможно, было бы яснее, если бы он сказал это немного по-другому (но с тем же значением): «хеш-таблица - это один из способов реализации словаря». То есть, если вам нужна функциональность словаря, один из способов сделать это ( реализовать словарь) - это использовать хеш-таблицу.
ToolmakerSteve 23.03.2015 04:41:18

Еще одно отличие, которое я могу понять:

Мы не можем использовать словарь <KT, VT> (generics) с веб-сервисами. Причина в том, что стандарт веб-службы не поддерживает стандарт дженериков.

5
23.10.2017 08:05:50
Мы можем использовать общие списки (List <string>) в веб-сервисе на основе мыла. Но мы не можем использовать словарь (или хеш-таблицу) в веб-сервисе. Я думаю, что причина этого в том, что .net xmlserializer не может обработать объект словаря.
Siddharth 30.11.2015 11:04:21

Обратите внимание, что MSDN говорит: «Словарь <(Of <(TKey, TValue>)>) реализован как хеш-таблица », а не «Словарь <(Of <(TKey, TValue>)>) класс реализован как HashTable »

Словарь НЕ реализован как HashTable, но он реализован в соответствии с концепцией хеш-таблицы. Реализация не связана с классом HashTable из-за использования Generics, хотя внутри Microsoft могла бы использовать тот же код и заменить символы типа Object на TKey и TValue.

В .NET 1.0 Generics не существовало; именно здесь изначально начинались HashTable и ArrayList.

11
23.10.2017 08:10:15
Можете ли вы исправить эту цитату MSDN? Что-то отсутствует или не так; это не грамматически и несколько непонятно.
Peter Mortensen 23.10.2017 08:11:09

Согласно тому, что я вижу с помощью .NET Reflector :

[Serializable, ComVisible(true)]
public abstract class DictionaryBase : IDictionary, ICollection, IEnumerable
{
    // Fields
    private Hashtable hashtable;

    // Methods
    protected DictionaryBase();
    public void Clear();
.
.
.
}
Take note of these lines
// Fields
private Hashtable hashtable;

Таким образом, мы можем быть уверены, что DictionaryBase использует HashTable внутри.

-3
23.10.2017 08:12:07
System.Collections.Generic.Dictionary <TKey, TValue> не является производным от DictionaryBase.
snemarch 23.09.2010 13:48:10
«Таким образом, мы можем быть уверены, что DictionaryBase использует HashTable внутри». - Это хорошо, но это не имеет никакого отношения к вопросу.
Jim Balter 3.11.2018 17:11:02

Dictionary<<< >>> Hashtableразличия:

  • Универсальный <<< >>> Неуниверсальный
  • Требуется собственная синхронизация потоков <<< >>> Предлагает потокобезопасную версию через Synchronized()метод
  • Пронумерованный предмет: KeyValuePair<<< >>> Пронумерованный предмет:DictionaryEntry
  • Более новые (> .NET 2.0 ) <<< >>> Старые (начиная с .NET 1.0 )
  • находится в System.Collections.Generic <<< >>> находится в System.Collections
  • Запрос на несуществующий ключ выдает исключение <<< >>> Запрос на несуществующий ключ возвращает ноль
  • потенциально немного быстрее для типов значений <<< >>> немного медленнее (требуется упаковка / распаковка) для типов значений

Dictionary/ Hashtableсходства:

  • Оба являются внутренними хеш-таблицами == быстрый доступ к данным из многих элементов в соответствии с ключом
  • Оба требуют неизменных и уникальных ключей
  • Ключи обоих требуют собственного GetHashCode()метода

Аналогичные коллекции .NET (кандидаты на использование вместо словаря и Hashtable):

  • ConcurrentDictionary- потокобезопасен (может быть безопасно доступен из нескольких потоков одновременно)
  • HybridDictionary- оптимизированная производительность (для нескольких предметов, а также для многих предметов)
  • OrderedDictionary- значения могут быть доступны через индекс int (по порядку, в котором элементы были добавлены)
  • SortedDictionary- элементы автоматически сортируются
  • StringDictionary- строго типизирован и оптимизирован для строк
625
15.01.2013 09:59:08
@ Guillaume86, вот почему вы используете TryGetValue вместо msdn.microsoft.com/en-us/library/bb347013.aspx
Trident D'Gao 29.06.2013 22:18:31
+1 для StringDictionary... кстати, StringDictionaryэто не то же самое, что Dictionary<string, string>при использовании конструктора по умолчанию.
Cheng Chen 25.06.2014 06:24:45
ParallelExtensionsExtras @ code.msdn.microsoft.com/windowsdesktop/… содержит ObservableConcurrentDictionary, который является отличной привязкой к ели, а также параллелизмом.
VoteCoffee 31.10.2014 14:28:01
классное объяснение, очень приятно, что вы также перечислили сходства, чтобы уменьшить количество вопросов, которые могут прийти вам в голову
mkb 25.03.2016 12:23:36

Dictionary<> является универсальным типом, и поэтому он безопасен.

Вы можете вставить любой тип значения в HashTable, и это может иногда вызывать исключение. Но Dictionary<int>будет принимать только целочисленные значения и аналогично Dictionary<string>будет принимать только строки.

Так что лучше использовать Dictionary<>вместо HashTable.

5
23.10.2017 08:12:51

Collections& Genericsполезны для обработки группы объектов. В .NET все объекты коллекций подчиняются интерфейсу IEnumerable, который в свою очередь имеет ArrayList(Index-Value))& HashTable(Key-Value). После .NET Framework 2.0, ArrayList& HashTableбыли заменены на List& Dictionary. Теперь Arraylist& HashTableбольше не используются в современных проектах.

Разница между HashTable& Dictionary, Dictionaryявляется общей, где Hastableне является общей . Мы можем добавить любой тип объекта HashTable, но при получении нам нужно привести его к требуемому типу. Таким образом, это не безопасно типа. Но для того dictionary, чтобы объявить себя, мы можем указать тип ключа и значение, поэтому нет необходимости приводить при получении.

Давайте посмотрим на пример:

Хеш-таблица

class HashTableProgram
{
    static void Main(string[] args)
    {
        Hashtable ht = new Hashtable();
        ht.Add(1, "One");
        ht.Add(2, "Two");
        ht.Add(3, "Three");
        foreach (DictionaryEntry de in ht)
        {
            int Key = (int)de.Key; //Casting
            string value = de.Value.ToString(); //Casting
            Console.WriteLine(Key + " " + value);
        }

    }
}

Словарь,

class DictionaryProgram
{
    static void Main(string[] args)
    {
        Dictionary<int, string> dt = new Dictionary<int, string>();
        dt.Add(1, "One");
        dt.Add(2, "Two");
        dt.Add(3, "Three");
        foreach (KeyValuePair<int, String> kv in dt)
        {
            Console.WriteLine(kv.Key + " " + kv.Value);
        }
    }
}
21
23.10.2017 08:14:45
вместо явного назначения типа данных для KeyValuePair, мы могли бы использовать var. Таким образом, это уменьшит набор текста - foreach (var kv in dt) ... просто предложение.
Ron 13.07.2016 13:43:11

Начиная с .NET Framework 3.5 есть еще и тот, HashSet<T>который предоставляет все плюсы, Dictionary<TKey, TValue>если вам нужны только ключи и никаких значений.

Так что, если вы используете a Dictionary<MyType, object>и всегда устанавливаете значение для nullимитации типовой безопасной хеш-таблицы, вам, возможно, стоит подумать о переключении на HashSet<T>.

16
23.10.2017 08:15:58

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

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

Для дальнейшего чтения: Типы Hashtable и Коллекция словарей

8
12.11.2015 10:51:13

Словарь:

  • Возвращает / выдает Exception, если мы пытаемся найти ключ, который не существует.

  • Это быстрее, чем Hashtable, потому что там нет упаковки и распаковки.

  • Только открытые статические члены являются потокобезопасными.

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

    Пример: Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

  • Dictionay - это безопасная от типов реализация Hashtable, Keysи она Valuesстрого типизирована.

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

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

  • Это медленнее, чем словарь, потому что он требует упаковки и распаковки.

  • Все члены Hashtable являются потокобезопасными,

  • Hashtable не является универсальным типом,

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

16
25.06.2014 05:23:40
«Возвращает / выдает исключение, если мы пытаемся найти ключ, который не существует». Нет, если вы используетеDictionary.TryGetValue
Jim Balter 3.11.2018 17:21:59

В статье « Обширный анализ структур данных с использованием C #» на MSDN говорится, что в стратегии разрешения конфликтов также есть различия :

Класс Hashtable использует технику, называемую перефразировкой .

Перефразировка работает следующим образом: существует набор хеш-функций, H 1 ... H n , и при вставке или извлечении элемента из хеш-таблицы первоначально используется хеш-функция H 1 . Если это приводит к столкновению, вместо этого пробуют H 2 и далее до H n, если необходимо.

Словарь использует технику, называемую цепочкой .

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

16
18.11.2014 11:35:50

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

В случае словаря нет безопасности потока; если вам нужна безопасность потоков, вы должны реализовать собственную синхронизацию.

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

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

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

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

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

7
23.10.2017 08:18:33
Из того, что я понимаю, Hashsetгарантии безопасности потоков MR / SW в сценариях использования, которые не включают удаления . Я думаю, что он должен был быть полностью безопасным для MR / SW, но безопасная обработка удалений значительно увеличивает затраты на безопасность MR / SW. Хотя разработка Dictionaryсценариев могла бы обеспечить безопасность MR / SW при минимальных затратах в сценариях без удаления, я думаю, что MS хотела бы не рассматривать сценарии без удаления как «особые».
supercat 14.02.2020 16:21:35

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

Ключ / значение будет преобразован в тип объекта (бокс) при сохранении в куче.

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

Эти операции очень дороги. Нам нужно как можно больше избегать коробок / распаковок.

Словарь: универсальный вариант HashTable.

Нет бокса / распаковки. Никаких преобразований не требуется.

10
23.10.2017 08:19:25

В большинстве языков программирования словари предпочтительнее хеш-таблиц

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

Однако в C # очевидная причина (для меня) состоит в том, что C # HashTables и другие члены пространства имен System.Collections в значительной степени устарели. Они присутствовали в c # V1.1. Они были заменены из C # 2.0 классами Generic в пространстве имен System.Collections.Generic.

0
6.03.2019 01:58:11
Одним из преимуществ хеш-таблицы над словарем является то, что если в словаре не существует ключа, он выдаст ошибку. Если ключ не существует в хеш-таблице, он просто возвращает ноль.
Bill Norman 20.03.2019 19:22:20
В C # я бы по-прежнему избегал использования System.Collections.Hashtable, так как они не имеют преимущества обобщений. Вы можете использовать словарь TryGetValue или HasKey, если вы не знаете, существует ли ключ.
kristianp 21.03.2019 00:49:35
Ой, а не HasKey, это должен быть ContainsKey.
kristianp 21.03.2019 01:02:09