Java內部類this$0字段產生的一個小bug

首先查看下面一段代碼，我指出了問題代碼的所在，讀者先自己思考一下這段代碼會有什麼問題。

這是用clone方法完整拷貝一個二項堆（BinomialHeap）結構的代碼。二項堆中包含一個內部類BinomialHeapEntry，這個內部類的對象即二項堆中的每一個結點，除了包含結點對應的關鍵字外，還記錄父節點parent，下一個兄弟結點sibling和第一個孩子結點child三個指針。二項堆的根表通過每棵二項樹根節點的sibling指針鏈接。

cloneBinomialTree(BinomialHeapEntry root)方法遞歸拷貝一個根節點（含根節點）下的整個二項樹，clone方法中遍歷根表中每個樹根結點，拷貝對應的二項樹，然後將新的head指針賦給拷貝後的新堆。

public class BinomialHeap<E> implements Cloneable {
        transient BinomialHeapEntry head; // 根表中的第一個元素
        int size;                         // 整個二項堆的大小（結點數）
      
        private class BinomialHeapEntry {
        E element;
        transient BinomialHeapEntry parent = null, child = null,
                sibling = null;
        transient int degree = 0;
     
                private BinomialHeapEntry(E element) {
            this.element = element;
        }
     
                // 獲得孩子結點的迭代器
                private Iterable<BinomialHeapEntry> children {...}
        }
     
        @Override
    public BinomialHeap<E> clone() {
        // TODO Auto-generated method stub
        BinomialHeap<E> clone;
        try {
            clone = (BinomialHeap<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
            throw new InternalError();
        }
             
        BinomialHeapEntry newHead = null, curRoot = null;
                // 遍歷根表
        Iterator<HeapEntry<E>> rootIt = this.roots().iterator();
        while(rootIt.hasNext()){
            BinomialHeapEntry root = (BinomialHeapEntry) rootIt.next();
                        // 拷貝根節點下的整棵二項樹<br>                        <span style="color: #ff0000;">// BUG引入的地方</span>
            BinomialHeapEntry newRoot = cloneBinomialTree(root);
            if(curRoot == null){
                newHead = newRoot;
            } else {
                curRoot.sibling = newRoot;
            }
            curRoot = newRoot;
        }
             
        clone.head = newHead;
        return clone;
    }
         
        // 拷貝根節點（含根節點）下的整棵子樹
    private BinomialHeapEntry cloneBinomialTree(BinomialHeapEntry root){
        BinomialHeapEntry newRoot = new BinomialHeapEntry(root.element());
        BinomialHeapEntry curChild = null;
                // 遍歷根節點的所有孩子結點
        Iterator<HeapEntry<E>> childIt = root.children().iterator();
        while(childIt.hasNext()){
            BinomialHeapEntry child = (BinomialHeapEntry) childIt.next();
            // 遞歸拷貝孩子節點下的子樹
                        BinomialHeapEntry newChild = cloneBinomialTree(child);
            newChild.parent = newRoot;
            if(curChild == null){
                newRoot.child = newChild;
            } else {
                curChild.sibling = newChild;
            }
            curChild = newChild;
        }
        newRoot.degree = root.degree;
        return newRoot;
    }
     
}

先回顧一下Java內部類的一些知識，非靜態的Java內部類作為外部類的一個成員，只能通過外部類的對象來訪問，要創建一個內部類對象，也需要通過外部類對象來創建，即：outerObject.new InnerClass()。這時，所創建的內部類對象會產生名稱為this$0的一個字段，該字段保存的是創建這個內部類對象的外部類對象引用，即剛才的outerObject。這個引用使得一個內部類對象可以自由的訪問外部類的成員變量。

在回顧上面二項堆拷貝的代碼，在調用cloneBinomialTree方法拷貝二項樹時，我們試圖通過new BinomialHeapEntry()來創建一個新的結點，把新的結點作為新二項堆中的結點，但事實上我們實際調用的是this.new BinomialHeapEntry()，也就是說創建的新結點中，this$0是指向老的二項堆(this)而不是新的正在拷貝的二項堆(clone)。這使得我們得到拷貝的新二項堆之後，通過新二項堆的任一結點訪問和修改整個堆的信息時，修改的都是老的二項堆，最後產生了一系列奇怪的結果。

要想修復這個bug很簡單，把clone方法中的BinomialHeapEntry newRoot = cloneBinomialTree(root)即紅色注釋下的語句，修改為BinomialHeapEntry newRoot = clone.cloneBinomialTree(root)。這樣cloneBinomialTree方法中創建的結點都是通過clone對象創建，問題也就解決了。

問題其實比較簡單，這確實是以後在編程中值得注意的一點：拷貝內部類對象時考慮清楚拷貝後的對象this$0字段是否指向的是你希望指向的外部類對象。

查看本欄目