Поэтому я столкнулся с Dictionary<int, int>
сегодня на работе. Это просто показалось мне странным, потому что я бы просто использовал List<int>
вместо этого. Есть ли разница, и будет ли вариант использования, когда одна структура будет предпочтительнее другой?
c#
.net
data-structures
ZeroDivide
источник
источник
List<T>
.NET Framework представляет собой массив произвольного доступа, где операция поиска обычно выполняется быстрее, чем дляDictionary<int,T>
.Dictionary<TKey, TValue>
.Ответы:
Вы должны использовать,
Dictionary<int, int>
если ваши индексы имеют особое значение помимо просто позиционного размещения.Непосредственный пример, который приходит на ум, - это сохранение столбца id и столбца int в базе данных. Например, если у вас есть
[person-id]
столбец и[personal-pin]
столбец, вы можете перенести их вDictionary<int, int>
. Этот способpinDict[person-id]
дает вам ПИН-код, но индекс имеет смысл, а не просто позицию вList<int>
.Но на самом деле, каждый раз, когда у вас есть два связанных списка целых чисел, это может быть подходящей структурой данных.
источник
List<int>
, а не словарь. Смотрите мой ответ ниже.Думайте о
List
как о массиве, аDictionary
как о хеш-таблице . Вы должны использовать только,Dictionary
если вам нужно, чтобы сопоставить (или связать) значимые ключи со значениями, тогда какList
только сопоставить (или связать) позиции (или индексы) со значениями.Например, скажем, вы хотели сохранить связь между возрастом человека и его ростом. Вы можете использовать,
Dictionary<int, int>
чтобы сопоставить возраст человека (иint
) с его ростом (int
):Не очень полезный пример, но суть в том, что вы не сможете сделать это так элегантно с помощью a,
List
поскольку для этого нужно будет хранить эти значения позиционно.источник
List
дело с заказом , где имеетDictionary
дело с ассоциацией . Если вам нужно каждый раз получать данные в определенном порядке или их порядок относительно друг друга важен, тоList
это путь.Dictionaries
имеют тенденцию быть неупорядоченными и иметь дело с отношениями ключ -> значение.Семантически, a
Dictionary<int, T>
иList<T>
очень похожи, оба являются контейнерами произвольного доступа .NET Framework. Чтобы использовать список в качестве замены словаря, вам нужно специальное значение в вашем типеT
(напримерnull
), чтобы представить пустые слоты в вашем списке. ЕслиT
тип не является обнуляемым, напримерint
, вы можете использоватьint?
вместо него, или если вы просто ожидаете хранить положительные значения, вы также можете использовать специальное значение, например -1, для представления пустых слотов.Какой из них вы выберете, зависит от диапазона значений ключа. Если ваши ключи в
Dictionary<int, T>
пределах находятся в целочисленном интервале, без большого количества пробелов между ними (например, 80 значений из [0, ... 100]), тогда aList<T>
будет более подходящим, так как доступ по индексу быстрее, и в этом случае меньше памяти и времени по сравнению со словарем.Если ваши ключевые значения равны 100
int
значениям из диапазона, подобного [0, ..., 1000000], тоList<T>
требуется память для хранения 1000000 значений T, тогда как вашему словарю просто потребуется память порядка порядка 100 значений T, 100 значений типа int (плюс некоторые накладные расходы, в реальности ожидайте примерно в 2 раза больше памяти для хранения этих 100 ключей и значений). Так что в последнем случае словарь будет более подходящим.источник
List<KeyValuePair<int,T>>
что O (1) не доступна. Во-вторых, элементыList<KeyValuePair<int,T>>
могут иметь определенный порядок, не зависящий от их ключевых значений. Если вам нужно последнее, но не первое,List<KeyValuePair<int,T>>
илиList<Tuple<int,T>>
может быть лучшим выбором. Если вам нужно и то, и другоеOrderedDictionary
.Как можно считать их эквивалентными?
Словарь является разреженным и допускает случайные вставки, но создает проблему обхода по порядку, List не редок и вставка не по порядку обходится дорого, по своей природе обеспечивает обход по порядку.
Было бы очень мало ситуаций, когда одно не было бы значительно выше другого.
источник
В сторону: Другие языки программирования называют этот тип структуры данных как Карта, а не Словарь.
Если ваши данные могут быть определенно определены как пары ключ / значение, то Словарь обеспечит гораздо более быстрый доступ, если вам нужно найти значение, используя его ключ.
Например, предположим, у вас есть список клиентов. Каждый клиент содержит такие данные, как имя и адрес, а также уникальный номер клиента. Предположим, у вас также есть список обрабатываемых заказов. Каждый Заказ будет содержать подробную информацию о том, что делается, и должен будет включать номер клиента человека, который заказал его.
Когда заказ будет готов к отправке, вам нужно найти адрес для отправки. Если клиенты хранятся в виде простого списка, то вам нужно выполнить поиск по всему списку, чтобы найти клиента с нужным номером клиента. Вместо этого вы можете хранить клиентов в словаре с номером клиента в качестве ключа. Словарь теперь позволит вам вывести нужного клиента за один шаг без поиска.
источник
Словарь использует хеширование для поиска данных. Словарь сначала вычисляет хеш-значение для ключа, и это хеш-значение приводит к целевому сегменту данных. После этого каждый элемент в корзине должен быть проверен на равенство. Но на самом деле список будет быстрее, чем словарь при поиске первого элемента, потому что ничего не нужно искать на первом шаге. Но на втором этапе список должен просмотреть первый элемент, а затем второй элемент. Таким образом, каждый шаг поиска занимает все больше и больше времени. Чем больше список, тем больше времени.
Подробнее о .... Словарь против списка с примером.
источник
Если в рассматриваемом коде хранятся два набора коррелированных значений, класс Dictionary обеспечивает индексированный способ поиска значений по ключу. Если существует только один набор значений, но к этому набору нужно обращаться случайным образом (возможно, для проверки существования ключа в наборе), а значения уникальны, HashSet может быть лучшим классом набора для использования.
источник
Это отличные ответы, которые, кажется, охватывают основы.
Еще одно соображение, которое я предлагаю, состоит в том, что словари (в C #) являются более сложными с точки зрения кодирования. Наличие как списков, так и словарей в одной и той же кодовой базе усложняет поддержку вашего кода, поскольку оба метода имеют тонкие различия в том, как выполнять базовые операции, такие как поиск и сортировка данных объекта. Я считаю, что если вам не нужен словарь по какой-либо оправданной причине, используйте список.
источник