Какова лучшая структура данных в .NET для поиска по строковому ключу или числовому индексу?

Question

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

Answer 1

Требуется класс OrderedDictionary . Вам нужно будет включить пространство имен System.Collections.Specialized:

    OrderedDictionary od = new OrderedDictionary(); 
    od.Add("abc", 1); 
    od.Add("def", 2); 
    od.Add("ghi", 3); 
    od.Add("jkl", 4); 

    // Can access via index or key value:      
    Console.WriteLine(od[1]);       
    Console.WriteLine(od["def"]);

Answer 2

Одно слово предупреждения. OrderedDictionary имеет действительно плохие характеристики производительности для большинства операций, кроме вставки и поиска: для удаления и изменения значения может потребоваться линейный поиск по всему списку, что приводит к времени выполнения O ( N ). (Для модификации это зависит от того, был ли доступ по индексу или по ключу.)

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

Если поиск по индексу происходит не слишком часто, SortedList или SortedDictionary будут иметь гораздо лучшие характеристики производительности (доступ по индексу может быть достигнут с помощью ElementAt метод расширения).

Если, с другой стороны, доступ по индексу является нормой, тогда полностью прекратите использование структур данных словаря и просто сохраните свои значения в List<KeyValuePair<TKey, TValue>>. Хотя это означает линейный поиск доступа по ключу, все остальные операции очень дешевы, и на практике трудно добиться общей производительности.

/ РЕДАКТИРОВАТЬ: Конечно, последний также является структурой данных словаря в теоретическом смысле. Вы даже можете инкапсулировать его в класс, реализующий соответствующий интерфейс.

Answer 3

Есть System.Collections.ObjectModel. KeyedCollection , которая является производной от Collection . Извлечение O (1) .

class IndexableDictionary<TItem> : KeyedCollection<string, TItem>
 { Dictionary<TItem, string> keys = new Dictionary<TItem, string>();

   protected override string GetKeyForItem(TItem item) { return keys[item];}

   public void Add(string key, TItem item) 
    { keys[item] = key;
      this.Add(item);
    }
 }

Answer 4

Я рекомендую использовать SortedDictionary или SortedList . Оба имеют O (log n) производительность поиска.

Различия, как указано в библиотека MSDN :

SortedList <(Of <(TKey, TValue>)>) использует меньше памяти чем SortedDictionary <(Of <(TKey, TValue>)>).

SortedDictionary <(Of <(TKey, TValue>)>) имеет более быструю вставку и Операции удаления несортированных данных: O (log n) в отличие от O (n) для SortedList <(Of <(TKey, TValue>)>).

Если список заполнен сразу из отсортированных данных, SortedList <(Of <(TKey, TValue>)>) быстрее, чем SortedDictionary <(Of <(TKey, TValue>)>).

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

Answer 5

Словарь может работать с linq. Хотя я не знаю о возможных проблемах производительности. Dictionary.ElementAt (индекс);

Answer 6

Вы ищете что-то вроде SortedList класса (вот также универсальная версия ).

Answer 7

Коллекции на основе хеша (Dictionary, Hashtable, HashSet) отсутствуют, потому что у вас не будет индекса, так как вам нужен индекс, я бы использовал вложенный универсальный тип:

List<KeyValuePair<K,V>>

Конечно, вы теряете поиск O (1) ключа, который вы получаете с хешами.