java - 通过 HashSet 与链接哈希集进行迭代

Question

我正在考虑如何在内存中表示图形？

我正在考虑使用 HashMap 的 HashMap ，以便它的行为类似到邻接矩阵，但我们可以使用可比较的边缘标签而不仅仅是整数。

在广度优先搜索和 Dijkstra 算法中，我们必须迭代邻接表并将节点添加到队列中。这引出了我的问题:

在 Java 中通过链接哈希集进行迭代是否比通过常规 HashSet 进行迭代更有效？

这似乎是因为每个节点之间按照添加顺序存在链接，因此我们不必遍历空容器(如果存在)(取决于 HashMap 的重新哈希率，这可以或多或少)。这将使我们能够将邻接矩阵的随机访问行为与邻接列表的搜索算法效率结合起来。

Answer 1

是的，你说得对。

Java HashMap/Set 在稀疏图中性能较差，因为它必须从空 bin 进行迭代。当大多数节点只连接一个其他节点时。 HashMap/Set 可能需要 8 次迭代才能得到准确的结果。相关分析可见 Codeforces: Performance of hash set iterators in different programming languages .

为了表示图形，Java 泛型机制可以让您为原始类型创建对象类型，例如 Integer。当转换为原始类型并构建图形时，它们会降低性能。在最佳实践中，您需要使用Trove或其他图书馆。也许，你自己实现。