java - Java HashMaps 和 putAll() 方法的问题

Question

大家好，我正在编写一个程序来比较各种 Dijkstra 实现的运行时间。我从一个文本文件中解析相关信息并将其输入到哈希表中。在我当前的实现中，我有一个包含节点信息的“主”哈希表，该信息被复制到一个临时哈希表中，然后传递给不同的 Dijkstra 类。

public class Router
{
    public static Map <Integer, Node> nodes = new HashMap<Integer, Node>();
    public static Map <Integer, Node> temp = new HashMap<Integer, Node>();
    public static int target = 2;
    public static int start = 0;

    public static void main(String[] args) throws IOException
    {
        Parser p3 = new Parser(args[0], nodes, p);
        temp.putAll(nodes);

        // Test 1
        DijkstraFib fb = new DijkstraFib(temp, start, target, p);
        temp.clear();
        temp.putAll(nodes);

        //Test 2
        DijkstraBinary d = new DijkstraBinary(temp, start, target, p);
        temp.clear();
        temp.putAll(nodes);

        // Test 3
        Dijkstra b = new Dijkstra(temp, start, target, p);
    }

因此，不必为每个 Dijkstra 类调用解析器三次，我只想将所有值从 nodes 表复制到 temp，因为 temp 在方法执行期间被修改。前两个测试运行良好，但第三个测试失败。如果我交换测试 2 和测试 3，那么测试 2 会失败；基本上，无论最后运行哪个测试，都会失败。这是我的 Dijkstra 方法:

void route(Map <Integer, Node> nodes, int source)
{
    Node start = nodes.get(source);
    start.distance = 0;
    unsettledNodes.add(start);

    while(!unsettledNodes.isEmpty())
    {
        Node n = extractMin();
        visited.put(n.name, n);
        relax_neighbours(n, nodes);
    }
}

void relax_neighbours(Node n, Map <Integer, Node> nodes)
{
    for (int i = 0; i < n.outgoing.size(); i++)
    {
        Edge edge = n.outgoing.get(i);
        Node v = nodes.get(edge.node);

        if (isSettled(v))
        {
            continue;
        }

        double shortDist = n.distance + edge.length;
        if (shortDist < v.distance)
        {
            unsettledNodes.remove(v);
            v.distance = shortDist;
            v.previous = n;
            unsettledNodes.add(v);
        }
    }
}

这是我打印从目标节点开始的路径的方法:

 void print_path(Map <Integer, Node> visited, int i)
{
    ArrayList<Node> path = new ArrayList<Node>();

    for (Node target = visited.get(i); target != null; target = target.previous)
    {
        path.add(target);
    }
    System.out.println("Simple Dijkstra took " + this.time_taken + " ms");
    System.out.print("Min dist from " + this.source + " to " + this.target + " = " + path.get(0).distance + " : ");

    Collections.reverse(path);

    System.out.print(path.get(0).name);
    p.append(Integer.toString(path.get(0).name));
    for (int k = 1; k < path.size(); k++)
    {
        System.out.print(" -> " + path.get(k).name);
    }
    System.out.println();
}

这是控制台输出:

Edges: 948464
Fibonacci Dijkstra took 340 ms
Min dist from 0 to 2 = 89.0 : 0 -> 195 -> 5523 -> 5504 -> 5870 -> 5835 -> 3076 -> 15319 -> 5588 -> 5911 -> 2

Binary Dijkstra took 302292 ms
Min dist from 0 to 2 = 89.0 : 0 -> 195 -> 5523 -> 5504 -> 5870 -> 5835 -> 3076 -> 15319 -> 5588 -> 5911 -> 2

Simple Dijkstra took 0 ms
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
   at java.util.ArrayList.rangeCheck(ArrayList.java:571)
   at java.util.ArrayList.get(ArrayList.java:349)
   at Dijkstra.print_path(Dijkstra.java:115)
   at Dijkstra.<init>(Dijkstra.java:25)
   at Router.main(Router.java:33)

Answer 1

在没有看到更多代码的情况下，我无法确定，但是当您将 putAll 放入新 map 时，您似乎正在传递相同的对象。也就是说，在调用中引用相同的节点，而 temp 不是节点中值的副本。不是。如果您的方法正在修改最短路径算法的路径权重(即，如果 Node 是可变的)，您将遇到问题。

一个选项是通过创建一个新节点并填充所有相关信息来为您的节点编写一个深度复制方法。然后，对于算法的每次新运行，您都将拥有该节点的“全新”副本