C# 字典 : faster access but less memory footprint

Question

我需要一些关于以最小内存占用和最大访问性能进行存储和访问的最佳方式的建议。

例如。对于每辆车，我想存储型号和名称。

我有以下几点想法:

选项 1:

Dictionary<string, Dictionary<string, string>> values = new Dictionary<string, Dictionary<string, string>>();
Dictionary<string, string> list = new Dictionary<string, string>();
list.Add("2001", "Jetta S");
list.Add("2002", "Jetta SE");
list.Add("2002", "Jetta LE");
values.Add("VolksWagen", list);

选项 2:

Dictionary<string, List<KeyValuePair<string, string>>> values2 = new Dictionary<string, List<KeyValuePair<string, string>>>();
<pre lang="xml">List<KeyValuePair<string, string>> list2 = new List<KeyValuePair<string, string>>();
list2.Add(new KeyValuePair<string, string>("2001", "Jetta S"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta SE"));
list2.Add(new KeyValuePair<string, string>("2002", "Jetta LE"));
values2.Add("VolksWagen", list2);

选项 3:

Dictionary<string, List<string>> values1 = new Dictionary<string, List<string>>();
List<string> list1 = new List<string>();
list1.Add("2001:Jetta S");
list1.Add("2002:Jetta SE");
list1.Add("2002:Jetta LE");
values1.Add("VolksWagen", list1);

• 选项 1:更快地访问 make 和名称但内存占用最多
• 选项 2:快速访问 make 和名称但更多的内存占用
• 选项 3:缓慢访问 make 和名称(必须解析它)但是更少的内存占用

像上面那样会有1500多个词典。

有任何关于最快访问但内存占用更少的建议吗？

谢谢。

Answer 1

SortedList<TKey,TValue>是一个平面列表(因此内存占用量没有大幅增加)，它使用二进制搜索进行访问 - 所以 O(log(n)) - 所以不如Dictionary<TKey,TValue>快在 O(1) - 但比 List<T> 好多了(或其他线性搜索)在 O(n) .

如果您想要最快 访问，您需要为哈希表使用额外的内存。

作为旁注，SortedList<TKey,TValue>还允许通过 int index 进行高效访问，这对于 SortedDictionary<TKey,TValue> 来说很难, 对于 Dictionary<TKey,TValue> 几乎没有意义.

显然，在您的场景中，您可能需要合并 SortedList<,>使用嵌套或复合键 - 但 IMO 这将是您获得内存和访问器性能平衡的最佳途径。您可以使用专用的复合键，即 iummutable struct使用复合键成员，覆盖 GetHashCode()和 Equals , 实现 IEquatable<T> , 以及排序:实现 IComparable和 IComparable<T> .