使用循环引用深度复制Java对象 [英] Deep copying Java objects with circular references

问题描述

我如何为 Foo 实施深层复制？它包含一个 Bar 的实例，然后引用该 Foo 。

How would I go about implementing a deep copy for Foo? It contains an instance of Bar, which then has a reference to that Foo.

public class Foo {

    Bar bar;

    Foo () {
        bar = new Bar(this);
    }

    Foo (Foo oldFoo) {
        bar = new Bar(oldFoo.bar);
    }

    public static void main(String[] args) {
        Foo foo = new Foo();
        Foo newFoo = new Foo(foo);
    }

    class Bar {
        Foo foo;

        Bar (Foo foo) {
            this.foo = foo;
        }

        Bar (Bar oldBar) {
            foo = newFoo(oldbar.Foo);
        }
    }
}

目前，此代码由于无限递归会导致堆栈溢出。

As it stands, this code would cause a stack overflow due to infinite recursion.

此外，这是我可以构造的最简单的例子。实际上，对象图会更大，有多个实例变量本身就是集合。想多个 Bar s，例如多个 Foo 。

Also, this is the most simplistic example I could construct. In practice, the object graph would be larger, with multiple instance variables which could themselves be collections. Think multiple Bars, with multiple Foos, for instance.

编辑：我目前正在实施@ chiastic-security的方法。我为Foo正确地做了吗？我正在使用单独的HashMap来包含对象图的所有部分，以便我可以尽可能地编写深层复制功能。

EDIT: I'm currently in the process of implementing @chiastic-security's method. Am I doing it correctly for Foo? I'm using a separate HashMap to contain all parts of the object graph so that I can write the deep copy functionality as generally as possible.

Foo (Foo oldFoo) throws Exception {
    this(oldFoo, new IdentityHashMap<Object, Object>(), new IdentityHashSet<Object>());
}

Foo (Foo oldFoo, IdentityHashMap<Object, Object> clonedObjects, IdentityHashSet<Object> cloning) throws Exception {
    System.out.println("Copying a Foo");

    HashMap<Object, Object> newToOldObjectGraph = new HashMap<Object, Object>();
    newToOldObjectGraph.put(bar, oldFoo.bar);
    deepCopy(newToOldObjectGraph, clonedObjects, cloning);
}

void deepCopy(HashMap<Object, Object> newToOldObjectGraph, IdentityHashMap<Object, Object> clonedObjects, IdentityHashSet<Object> cloning) throws Exception {
    for (Entry<Object, Object> entry : newToOldObjectGraph.entrySet()) {
        Object newObj = entry.getKey();
        Object oldObj = entry.getValue();

        if (clonedObjects.containsKey(oldObj)) {
            newObj = clonedObjects.get(oldObj);
        }
        else if (cloning.contains(oldObj)){
            newObj = null;
        }
        else {
            cloning.add(oldObj);
            // Recursively deep clone
            newObj = newObj.getClass().getConstructor(oldObj.getClass(), clonedObjects.getClass(), cloning.getClass()).
                newInstance(oldObj, clonedObjects, cloning);

            clonedObjects.put(oldObj, newObj);
            cloning.remove(oldObj);
        }
        if (newObj == null && clonedObjects.containsKey(oldObj)) {
            newObj = clonedObjects.get(oldObj);
        }
    }
}

推荐答案

实现可能涉及循环引用的深层副本的最简单方法是，如果您希望以后能够容忍对结构的更改，那么将使用 IdentityHashMap 和 IdentityHashSet （来自这里）。如果要复制：

The easiest way to implement a deep copy that might involve circular references, if you want it to be tolerant of changes to the structure later, would be to use an IdentityHashMap and an IdentityHashSet (from here). When you want to copy:

1. 创建一个空的 IdentityHashMap< Object，Object> ，将源对象映射到它们的克隆。


2. 创建一个空的 IdentityHashSet< Object> 来跟踪当前所有的对象克隆的过程，但还没有完成。


3. 开始复制过程。在每个阶段，当您要复制对象时，请在 IdentityHashMap 中查找它，看看您是否已克隆该位。如果有，请返回您在 IdentityHashMap 中找到的副本。


4. 签入 IdentityHashSet 查看您是否正在克隆您现在已达到的对象（因为循环引用）。如果你有，现在就把它设置为 null ，然后继续。


5. 如果你之前没有克隆过它（即，源对象不在地图中），你不是在克隆它（即，它不在集合中），将它添加到 IdentityHashSet ，递归深度克隆它，然后当你完成递归调用时，将源/克隆对添加到 IdentityHashMap ，并将其从<$ c $中删除c> IdentityHashSet 。


6. 现在在递归克隆结束时，你需要处理 null 因为您遇到了循环引用而导致您挂起的引用。您可以同时浏览源和目标图。每当您在源图中找到一个对象时，请在 IdentityHashMap 中查找它，并找出它应映射到的内容。如果它存在于 IdentityHashMap 中，并且如果目标图形中当前 null ，则可以设置目标引用到你在 IdentityHashMap 中找到的克隆。

1. Create an empty IdentityHashMap<Object,Object>, to map source objects to their clones.
2. Create an empty IdentityHashSet<Object> to track all the objects that are currently in the process of being cloned, but haven't yet finished.
3. Start the copy process going. At each stage, when you want to copy an object, look it up in your IdentityHashMap to see if you've already cloned that bit. If you have, return the copy that you find in the IdentityHashMap.
4. Check in the IdentityHashSet to see if you're in the middle of cloning the object you've now reached (because of a circular reference). If you have, just set it to null for now, and move on.
5. If you haven't previously cloned this (i.e., the source object isn't in the map), and you're not in the middle of cloning it (i.e., it's not in the set), add it to the IdentityHashSet, recursively deep clone it, and then when you've finished the recursive call, add the source/clone pair to the IdentityHashMap, and remove it from the IdentityHashSet.
6. Now at the end of your recursive cloning, you need to deal with the null references you left hanging because you encountered a circular reference. You can walk the graph of source and destination simultaneously. Whenever you find an object in the source graph, look it up in your IdentityHashMap, and find out what it should map to. If it exists in the IdentityHashMap, and if it's currently null in the destination graph, then you can set the destination reference to the clone you find in the IdentityHashMap.

这将确保你不要将图形的相同部分克隆两次，但只要在图形中出现两次的对象，它总是以相同的参考结尾。这也意味着循环引用不会导致无限递归。

This will make sure you don't clone the same part of the graph twice, but always end up with the same reference whenever there's an object that appears twice in your graph. It will also mean that circular references don't cause infinite recursion.

使用 Identity 版本的要点是如果图中的两个对象与 .equals（）确定的相同，但由 == ，然后一个 HashSet 和 HashMap 会识别这两个，你最终会把所有东西加在一起不加入。只有在 == 。

The point of using the Identity versions is that if two objects in your graph are the same as determined by .equals(), but different instances as determined by ==, then a HashSet and HashMap would identify the two, and you'd end up joining things together that shouldn't be joined. The Identity versions will treat two instances as the same only if they're identical, i.e., the same as determined by ==.

如果您想要完成所有这些但无需自己实现，您可以查看 Java深度克隆库。

If you want to do all this but without having to implement it yourself, you could have a look at the Java Deep Cloning Library.

这篇关于使用循环引用深度复制Java对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！