C# - Поиск ключей словаря и значений поиска в списке

Question

С точки зрения скорости в поиске, лучше ли искать ключи словаря или значения списка?

Иными словами, какой из них был бы наиболее предпочтительным?

Dictionary<tring,string> dic = new Dictionary<string,string>(); 
if(dic.ContainsKey("needle")){ ... } 

Или

List<string> list = new List<string>(); 
if(list.Contains("needle")){ ... } 

Answer 1

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

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

Если у вас есть только, у вас есть ключевые пункты (не сопоставляя ключи со значениями), вы также можете попробовать HashSet. Он имеет преимущество O (1) поиска без накладных расходов на стороне словаря Value.

(Предоставленный накладные расходы, вероятно, минимальный, но зачем, если вам это не нужно?)

Answer 2

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

Смотрите также: http://www.dotnetperls.com/dictionary-time

Answer 3

Я предлагаю использовать Dictionary, когда число выборок значительно превышает количество вставок. Хорошо использовать List, когда у вас всегда будет меньше четырех предметов.

Для поиска Словарь обычно является лучшим выбором. Требуемое время является плоским, O (1) постоянной временной сложностью. Список имеет линейную временную сложность O (N). Три элемента можно зацикливать быстрее, чем искать в словаре.