从Dictionary中获取任何元素的最快方法

Question

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

Answer 1

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

在Java中,我可能会推荐LinkedHashMap,它有自定义的C#等价物(不是内置的)(参见参考资料).

但是,以合理的方式自己实现它是相当容易的.例如,您可以使用带有元组的常规字典,这些元组指向下一个元素以及实际数据.或者你可以保留一个二级堆栈,它只是按添加顺序存储所有密钥.只是一些想法.我自己从来没有实施或描述过,但我相信你会找到一个好方法.

哦,如果你还没有,你可能还想检查哈希码分布,以确保那里没有问题.