6

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

4

7 回答 7

7

你想要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"]);
于 2008-09-26T05:15:02.573 回答
2

有 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);
    }
 }
于 2008-09-26T04:25:23.877 回答
2

一句话警告。除了插入和查找之外，大多数操作的性能OrderedDictionary都非常差：删除和修改值都可能需要对整个列表进行线性搜索，从而导致运行时O ( n )。（对于修改，这取决于是按索引还是按键进行访问。）

对于大多数具有合理数据量的操作，这是完全不能接受的。此外，数据结构将元素存储在线性向量和哈希表中，导致一些内存开销。

如果按索引检索不经常发生，a SortedListorSortedDictionary将具有更好的性能特征（可以通过ElementAt扩展方法实现按索引访问）。

另一方面，如果按索引访问是常态，那么请停止使用字典数据结构，只需将值存储在List<KeyValuePair<TKey, TValue>>. 尽管这意味着通过密钥进行线性搜索，但所有其他操作都非常便宜，并且在实践中整体性能难以超越。

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

于 2008-09-26T08:15:52.497 回答
0

基于哈希的集合（字典、哈希表、哈希集）已经过时了，因为你没有索引，因为你想要一个索引，我会使用嵌套的泛型：

List<KeyValuePair<K,V>>

当然，您会丢失使用散列获得的 O(1) 密钥查找。

于 2008-09-26T04:20:13.423 回答
0

字典可以与 linq 一起使用。虽然我不知道可能的性能问题。Dictionary.ElementAt(index);

于 2008-09-26T08:17:13.337 回答
0

我建议使用 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) 相对于 SortedList<(Of <(TKey, TValue>)>) 的 O(n)。

如果列表是从排序数据中一次性填充的，SortedList<(Of <(TKey, TValue>)>) 比 SortedDictionary<(Of <(TKey, TValue>)>) 快。

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

于 2008-09-26T13:23:18.677 回答
-1

您正在寻找类似SortedList 类的东西（这里也是通用版本）。

于 2008-09-26T05:04:42.130 回答