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

Вам нужен класс 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"]);

Существует System.Collections.ObjectModel.KeyedCollection‹ string,TItem>, производная от Collection‹ TItem>. Получение — 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);
    }
 }

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

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

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

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

/EDIT: Конечно, последний также является структурой данных словаря в теоретическом смысле. Вы даже можете инкапсулировать его в класс, реализующий соответствующий интерфейс.

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

List<KeyValuePair<K,V>>

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

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

Я рекомендую использовать SortedDictionary‹string, TValue› или SortedList‹string, TValue›. Оба имеют производительность поиска 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 редко бывают критическими. Но если для вас важна производительность, я предлагаю вам реализовать оба варианта и провести измерения.

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