Словарь против списка

30

Поэтому я столкнулся с Dictionary<int, int>сегодня на работе. Это просто показалось мне странным, потому что я бы просто использовал List<int>вместо этого. Есть ли разница, и будет ли вариант использования, когда одна структура будет предпочтительнее другой?

ZeroDivide
источник
1
Должна ли быть связь между двумя (или более) данными целыми числами? Тогда карта (словарь на этом языке) имеет смысл.
Рог
3
Название словаря делает это очевидным для меня. Когда вам нужно что-то быстро найти, вы используете словарь.
ChaosPandion
2
@ChaosPandion: a List<T>.NET Framework представляет собой массив произвольного доступа, где операция поиска обычно выполняется быстрее, чем для Dictionary<int,T>.
Док Браун
2
@DocBrown - только в довольно странном случае использования числового индекса в качестве ключа. Другой мудрый взгляд будет быстрее при использовании Dictionary<TKey, TValue>.
ChaosPandion
2
@chaos этот вопрос о странном случае.
MarkJ

Ответы:

32

Вы должны использовать, Dictionary<int, int>если ваши индексы имеют особое значение помимо просто позиционного размещения.

Непосредственный пример, который приходит на ум, - это сохранение столбца id и столбца int в базе данных. Например, если у вас есть [person-id]столбец и [personal-pin]столбец, вы можете перенести их в Dictionary<int, int>. Этот способ pinDict[person-id]дает вам ПИН-код, но индекс имеет смысл, а не просто позицию в List<int>.

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

Крис Харпер
источник
Если мой персональный идентификатор находится в диапазоне 0, ..., 999, и мне нужно было бы загрузить значения личных контактов в память для всех 1000 человек, я обычно выбирал бы List<int>, а не словарь. Смотрите мой ответ ниже.
Док Браун
3
да, но словарь может быть разреженным
JK.
@jk: это именно то, что я пытался уточнить в своем ответе.
Док Браун
7
Персональный ПИН? Звучит как-то излишне.
Джек,
Хм, когда индекс имеет «особое значение», в сценариях реального мира может быть вероятность, что они не образуют непрерывный диапазон [0, ..., n] (хотя это не обязательно), поэтому этот ответ не совсем неправильно, но неточно. Тем не менее, ИМХО, решение не должно быть основано на этой «особой смысловой вещи», а только на «строит ли ключи примерно интервал [0, ..., n]». Судя по количеству голосов, большинство читателей упустили этот момент.
Док Браун
28

Думайте о Listкак о массиве, а Dictionaryкак о хеш-таблице . Вы должны использовать только, Dictionaryесли вам нужно, чтобы сопоставить (или связать) значимые ключи со значениями, тогда как Listтолько сопоставить (или связать) позиции (или индексы) со значениями.

Например, скажем, вы хотели сохранить связь между возрастом человека и его ростом. Вы можете использовать, Dictionary<int, int>чтобы сопоставить возраст человека (и int) с его ростом ( int):

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

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

Бернард
источник
7
+1 за упоминание, что имеет Listдело с заказом , где имеет Dictionaryдело с ассоциацией . Если вам нужно каждый раз получать данные в определенном порядке или их порядок относительно друг друга важен, то Listэто путь. Dictionariesимеют тенденцию быть неупорядоченными и иметь дело с отношениями ключ -> значение.
KChaloux
2
Не в последнюю очередь, когда вы знаете, что вы ищете, хеш-таблица составляет около O (1) времени, в то время как массив в лучшем случае O (logN) (отсортировано и без дубликатов) и O (N) в худший случай.
JensG
1
+1. Никто другой, кажется, не обращал внимания на то, что списки семантически упорядочены, а диктанты - это семантически поиски, что , на мой взгляд , является абсолютно фундаментальным .
Бенджамин Ходжсон
15

Семантически, a Dictionary<int, T>и List<T>очень похожи, оба являются контейнерами произвольного доступа .NET Framework. Чтобы использовать список в качестве замены словаря, вам нужно специальное значение в вашем типе T(например null), чтобы представить пустые слоты в вашем списке. Если Tтип не является обнуляемым, например int, вы можете использовать int?вместо него, или если вы просто ожидаете хранить положительные значения, вы также можете использовать специальное значение, например -1, для представления пустых слотов.

Какой из них вы выберете, зависит от диапазона значений ключа. Если ваши ключи в Dictionary<int, T>пределах находятся в целочисленном интервале, без большого количества пробелов между ними (например, 80 значений из [0, ... 100]), тогда a List<T>будет более подходящим, так как доступ по индексу быстрее, и в этом случае меньше памяти и времени по сравнению со словарем.

Если ваши ключевые значения равны 100 intзначениям из диапазона, подобного [0, ..., 1000000], то List<T>требуется память для хранения 1000000 значений T, тогда как вашему словарю просто потребуется память порядка порядка 100 значений T, 100 значений типа int (плюс некоторые накладные расходы, в реальности ожидайте примерно в 2 раза больше памяти для хранения этих 100 ключей и значений). Так что в последнем случае словарь будет более подходящим.

Док Браун
источник
6
это важное отличие imho, Dictionary <int, int> может быть разреженным
jk.
В таком случае, мы не можем использовать List <KeyValuePair <int, int >>? Какой из них будет лучше для линейного обхода?
Дипак Мишра
@DeepakMishra: главное отличие здесь в том, List<KeyValuePair<int,T>>что O (1) не доступна. Во-вторых, элементы List<KeyValuePair<int,T>>могут иметь определенный порядок, не зависящий от их ключевых значений. Если вам нужно последнее, но не первое, List<KeyValuePair<int,T>>или List<Tuple<int,T>>может быть лучшим выбором. Если вам нужно и то, и другое OrderedDictionary.
Док Браун
@DocBrown Какой из них будет лучше для линейного обхода (например, foreach) и операции вставки, нет необходимости прямого поиска?
Дипак Мишра
@DeepakMishra: в разработке программного обеспечения не существует такой вещи, как «вообще лучше». Лучшее здесь может означать быстрее, лучше читать, меньше кода для ввода, легче расширять для будущих требований. Но в целом, перестаньте задумываться над этим, реализуйте ту, которая правильно решает вашу проблему и является самой простой на ваш взгляд , проверяйте, достаточно ли это быстро для вашей цели , и вкладывайте в нее только больше мыслей, когда наблюдаете недостатки.
Док Браун
6

Как можно считать их эквивалентными?

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

Было бы очень мало ситуаций, когда одно не было бы значительно выше другого.

Лорен Печтель
источник
2

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

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

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

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

Саймон Б
источник
1

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

Подробнее о .... Словарь против списка с примером.

Walshregal
источник
-1

Если в рассматриваемом коде хранятся два набора коррелированных значений, класс Dictionary обеспечивает индексированный способ поиска значений по ключу. Если существует только один набор значений, но к этому набору нужно обращаться случайным образом (возможно, для проверки существования ключа в наборе), а значения уникальны, HashSet может быть лучшим классом набора для использования.

JoshL
источник
-3

Это отличные ответы, которые, кажется, охватывают основы.

Еще одно соображение, которое я предлагаю, состоит в том, что словари (в C #) являются более сложными с точки зрения кодирования. Наличие как списков, так и словарей в одной и той же кодовой базе усложняет поддержку вашего кода, поскольку оба метода имеют тонкие различия в том, как выполнять базовые операции, такие как поиск и сортировка данных объекта. Я считаю, что если вам не нужен словарь по какой-либо оправданной причине, используйте список.

StephenR
источник
8
Я не согласен. Словарь / карта - это фундаментальная структура данных, с которой каждый инженер-программист должен быть хорошо знаком. В любом случае: вам потребуется обоснованная причина для использования любой структуры данных; в том числе список.
Стивен Эверс