相对于字典<T,T> 或列表<T> 的内存使用decrease/Increase

Question

我有一个项目需要处理海量数据。我们使用的主要存储是字典。事实上，数以千计的词典被创建出来。将其更改为 List for keys 和 List for values（我们自己实现了 IDictionary）后，内存使用量减少了大约 30-40%。

为什么？

Answer 1

如果你把它们排序并放在一个数组中，你大概可以再节省 30% 的内存。

功能会消耗内存，你知道吗？

Dictionary<,> 给你一个价格 O(1) Add() 和 TryGetValue()

List<> 以较低的价格为您提供 O(1) Add()，如果排序，则为 O (logn) BinarySearch()，但是注意保持排序不能用Add()，必须用Insert()，也就是O (n)

T[] 以更低的价格为您提供 O(logn) BinarySearch()。从技术上讲，您可以插入 O(n)，但您必须手动执行（并且 "real" 成本会比 List<>的一个)

现在...如果你想知道Dictionary<,>如何使用你宝贵的记忆，你可以看看reference source

有这个struct:

private struct Entry {
    public int hashCode;    // Lower 31 bits of hash code, -1 if unused
    public int next;        // Index of next entry, -1 if last
    public TKey key;           // Key of entry
    public TValue value;         // Value of entry
}

并且有两个数组，其中一个使用了这个结构：

private int[] buckets;
private Entry[] entries;

所以一个List<TKey> +一个List<TValue>可能比一个Dictionary<TKey, TValue>小，因为一个Dictionary<,>有一个额外的int[] buckets加上一个int hashCode 和每个元素的 int next。

注意Dictionary<,>和List<>的增长算法是不一样的。 List<> 通过将其元素数量加倍来增长，而 Dictionary<,> 通过将其元素数量加倍然后找到大于此的质数来增长。所以 Dictionary<,> 增长得更快一些。

Answer 2

几年前，我分析了 Dictionary 内存使用情况。简而言之，Dictionary<TKey, TValue> 的开销是每个项目 24 个字节。那是 64 位运行时。有关详细信息，请参阅 More on .NET Collection Sizes。

List<T> 存储引用类型时的开销为每个项目 8 个字节：保存对列表中项目的引用所需的数据量。您将每个项目开销为 24 字节的单个字典换成了两个每个项目开销为 8 字节的列表。所以你的总开销是每项 16 个字节。

16 是 24 的 2/3。因此您节省了大约 33%。

您遇到的可能是传统的 size/speed 权衡。该字典为您提供 O(1) 查找但使用更多内存。使用两个列表，您可以节省内存但查找是 O(log n)。

相对于字典<T,T> 或列表<T> 的内存使用decrease/Increase

Memory usage decrease/Increase with respect to Dictionary<T,T> OR List<T>

dictionary

memory-management

list

c#-4.0