• 热门专题

Java内部类this$0字段产生的一个bug

作者:都市耕牛  发布日期:2014-05-22 20:15:50
Tag标签:字段  
  •         首先查看下面一段代码,我指出了问题代码的所在,读者先自己思考一下这段代码会有什么问题。

            这是用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();
                            // 拷贝根节点下的整棵二项树
    // BUG引入的地方 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字段是否指向的是你希望指向的外部类对象。

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规