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

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

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

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

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

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

Источник

Dictionary <<< >>> Различия в Hashtable :

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

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

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

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

  • ConcurrentDictionarystreamобезопасный (может быть безопасно доступен из нескольких streamов одновременно)
  • HybridDictionaryоптимизированная производительность (для нескольких элементов, а также для многих предметов)
  • OrderedDictionary – значения могут быть доступны через индекс int (по порядку, в который были добавлены элементы)
  • SortedDictionary – элементы автоматически сортируются
  • StringDictionary – строго типизированный и оптимизированный для строк

Потому что Dictionary – это общий class ( Dictionary ), так что доступ к его содержимому безопасен по типу (т. Dictionary Вам не нужно бросать из Object , как в случае с Hashtable ).

сравнить

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

в

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

Тем не менее, Dictionary реализован как Hashtable внутри, поэтому технически он работает одинаково.

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

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

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

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

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

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

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

Исходя из разницы между 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 dt = new Dictionary(); dt.Add(1, "One"); dt.Add(2, "Two"); dt.Add(3, "Three"); foreach (KeyValuePair kv in dt) { Console.WriteLine(kv.Key + " " + kv.Value); } } } 

Словарь:

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

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

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

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

    Пример: Dictionary = new Dictionary();

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

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

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

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

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

  • Hashtable не является общим типом,

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

С .NET Framework 3.5 есть также HashSet который предоставляет все преимущества Dictionary если вам нужны только ключи и нет значений.

Поэтому, если вы используете Dictionary и всегда устанавливаете значение null для имитации безопасной хеш-таблицы типа, вы можете подумать о переходе на HashSet .

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

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

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

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

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

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

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

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

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

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

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

Для дальнейшего чтения: типы Hashtable и Dictionary Collection

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

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

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

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

Словарь: общий вариант HashTable.

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

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

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

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

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

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

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

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

Дальнейшее уточнение:

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

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

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

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

Согласно тому, что я вижу с помощью .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.

  • Передача данных не-примитивного типа между действиями в android
  • Как хранить очень большие цифры?
  • Каковы менее известные, но полезные структуры данных?
  • Создание classа LinkedList с нуля
  • Как работает алгоритм HyperLogLog?
  • Вычислить размер объекта в Java
  • Структуры данных, которые могут отображать диапазон ключей в значение
  • Кто-нибудь действительно эффективно реализовал Fibonacci-Heap?
  • Выполнение Trie
  • Поиск C ++ STL-подобного векторного classа, но с использованием хранилища стека
  • Давайте будем гением компьютера.