c# - 从字典中获取任何元素的最快方法

Question

我在 C# 中实现 A*(不是用于寻路)，我需要字典来保存打开的节点，因为我需要快速插入和快速查找。我想从字典中获取第一个开放节点(它可以是任何随机节点)。使用 Dictionary.First() 非常慢。如果我使用迭代器，MoveNext() 仍然使用我程序整个 CPU 时间的 15%。从字典中获取任意随机元素的最快方法是什么？

Answer 1

我建议您为此目的使用专门的数据结构，因为常规词典不是为此而制作的。

在 Java 中，我可能会推荐 LinkedHashMap，它有自定义的 C# 等价物(遗憾的是不是内置的)(see)。

然而，以合理的方式自己实现这一点相当容易。例如，您可以使用带有指向下一个元素和实际数据的元组的常规字典。或者您可以保留一个辅助堆栈，它只按添加顺序存储所有键。只是一些想法。我自己从来没有实现过也没有分析过，但我相信你会找到一个好方法。

哦，如果你还没有，你可能还想检查散列码分布，以确保那里没有问题。