哈希表数据结构替代方案，使用较少的内存

Question

我有很多对象。每个对象都有一个唯一的 GUID。我需要此 GUID 的映射对象。我现在使用System.Collections.Hashtable。问题是添加对象哈希集会更改其大小并导致大型对象堆碎片。此外，它需要的内存是我拥有对象的两倍。我需要减少内存使用量。

我需要的数据结构的功能：

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

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

Answer 1

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

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

Answer 2

哈希表中的 500,000 个条目真的不多。只需告诉哈希表，当您创建它时它会很大：

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

这将创建一个字典，其中包含近 1,000,000 个元素的空间。当您接近 1,000,000 时，它将调整大小。旧的非通用Hashtable为您提供了更多的控制，允许您指定负载系数来控制重新分配。看这里。