.NET中用于查找字符串键或数字索引的最佳数据结构是什么？

StackOverflow https://stackoverflow.com/questions/137753

题

我正在寻找最理想的数据结构（性能和易用性），可以通过字符串键或索引从中检索值。字典不起作用，因为您无法通过索引真正检索。有什么想法吗？

有帮助吗？

解决方案

您想要 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 <！> lt; string，TItem <！> gt; ，派生自Collection <！> lt; TItem <！> GT ;. 检索是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>> 中。虽然这意味着通过密钥进行线性搜索访问，但所有其他操作都非常便宜，并且在实践中整体性能难以击败。

/编辑：当然，后者也是理论意义上的字典数据结构。您甚至可以将其封装在实现适当接口的类中。

基于哈希的集合（Dictionary，Hashtable，HashSet）已经用完，因为你没有索引，因为你想要一个索引，我会使用一个嵌套的泛型：

List<KeyValuePair<K,V>>

当然，你丢失了哈希带来的O（1）Key查找。

字典可以与linq一起使用。虽然我不知道可能的性能问题。 Dictionary.ElementAt（索引）;

我建议使用SortedDictionary <！> lt; string，TValue <！> gt;或SortedList <！> lt; string，TValue <！> gt;。两者都具有O（log n）搜索性能。

差异如引用 MSDN库：

  <！>

排序列表≤（中   <！> lt;（TKey，TValue <！> gt;）<！> gt;）使用更少的内存   比SortedDictionary <！> lt;（Of <！> lt;（TKey，   TValue GT <！>）GT <！>;）

     

SortedDictionary <！> lt;（Of <！> lt;（TKey，   TValue <！> gt;）<！> gt;）具有更快的插入和   未排序数据的删除操作：   O（log n）而不是O（n）   SortedList <！> lt;（Of <！> lt;（TKey，TValue <！> gt;）<！> gt;）。

     

如果列表一次全部填充   来自排序数据，SortedList <！> lt;（Of   <！> lt;（TKey，TValue <！> gt;）<！> gt;）比快   SortedDictionary <！> lt;（Of <！> lt;（TKey，   TValue GT <！>）GT <！>;）

根据我的经验，SortedDictionary对于大多数典型的业务场景更为适用，因为在使用这样的结构时，数据通常最初未排序，并且SortedDictionary的内存开销很少是关键。但如果性能对您来说很重要，我建议您实施两者并进行测量。

您正在寻找类似 SortedList类（这里是通用版本以及）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top