Почему словарь предпочтительнее, чем Hashtable в C #? - PullRequest
1303 голосов
/ 19 ноября 2008

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

Ответы [ 19 ]

1497 голосов
/ 19 ноября 2008

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

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

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

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

Источник

597 голосов
/ 21 апреля 2011

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 index (по порядку, в котором элементы были добавлены)
  • SortedDictionary - элементы автоматически отсортированы
  • StringDictionary - строго типизированный и оптимизированный для строк
173 голосов
/ 19 ноября 2008

Поскольку 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 реализован как хеш-таблица внутри, поэтому технически он работает так же.

84 голосов
/ 19 ноября 2008

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

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

67 голосов
/ 19 ноября 2008

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

32 голосов
/ 19 ноября 2008

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

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

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

22 голосов
/ 17 сентября 2012

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 при объявлении самого себя мы можем указать тип ключа и значение, поэтому нет необходимости приводить при получении.

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

HashTable

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);
        }
    }
}
16 голосов
/ 28 мая 2014

Словарь:

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

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

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

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

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

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

Hashtable:

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

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

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

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

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

15 голосов
/ 29 октября 2014

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

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

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

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

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

14 голосов
/ 15 января 2013

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...