c# - HashTable 数据结构替代方案，它使用更少的内存

Question

我有大量的对象。每个对象都有一个唯一的 GUID。我需要这个 GUID 的地图对象。我现在使用 System.Collections.Hashtable。问题是添加对象 hashset 会改变其大小并导致大对象堆的碎片。它也需要两倍于我拥有的对象的内存。我需要减少内存使用量。

我需要的数据结构的特点：

• 添加对象
• 按 ID 移除对象
• 按 ID 查找对象
• 运行数据结构中的所有对象（foreach）

为此目的最好的数据结构是什么？我知道有红黑树和 AVL 树，但我不知道哪种树更好用。也许还有另一种适合通过唯一标识符或字符串映射的树数据结构？哪种数据结构工作得更快？

Answer 1

哈希表中的 500,000 个条目实际上并不多。只需告诉哈希表在您创建它时它会很大：

var myDict = new Dictionary<key,val>(1000000);

这将创建一个可容纳近 1,000,000 个元素的字典。当您接近 1,000,000 时，它将调整大小。旧的非泛型Hashtable为您提供更多控制，允许您指定负载因子来控制重新分配。看这里。

Answer 2

数据结构是静态的还是动态的？如果它是静态的，请考虑使用完美散列。您将获得哈希表的好处，而无需太多内存开销。

不要指望树来解决您的问题……它们也具有相当高的内存开销，并且查询和更新的速度往往较慢。