土成
2017-03-09 03:20
采纳率: 83.3%
浏览 1.0k
已采纳

effective java书中,为什么常规的递归克隆当链表过长时会导致栈溢出?

 public class HashTable implements Cloneable {  
    private Entry [] buckets = ... ;  

    public static class Entry {  
        final Object key ;  
        Object value ;  
        Entry next ;  

        public Entry(Object key, Object value, Entry next) {  
            this.key = key ;  
            this.value = value ;  
            this.next = next ;  
        }  

        // 递归地深层复制每个链表节点对象   
        Entry deepCopy() {  
            return new Entry(key, value,  
                    next == null ? null : next.deepCopy()) ;  
        }  
    }  

    @Override  
    public HashTable clone() {  
        try {  
            HashTable result = (HashTable) super.clone() ;  
            result.buckets = new Entry[buckets.length] ;  
            //采用循环的方式对每个桶引用的单链表进行深层拷贝  
            for (int i = 0; i < buckets.length; i++) {  
                if (buckets[i] != null) {  
                    result.buckets[i] = buckets[i].deepCopy() ;  
                }  
            }  
            return result ;  
        } catch(CloneNotSupportedException e) {  
            throw new AssertionError() ;  
        }  
    }  
    ...//其余方法省略  
}  

effective java书中说这种方法虽然灵活,但是针对列表中的每个元素,都要消耗一段栈空间。如果链表过长,就容易导致栈溢出。

而如果用迭代的话就可以避免:

 Entry deepCopy() {  
    Entry result = new Entry(key, value, next) ;  
    for (Entry p = result; p.next != null; p = p.next) {  
        p.next = new Entry(p.next.key, p.next.value, p.next.next) ;  
    }  
    return result ;  
}  

想知道为什么会出现栈溢出?用迭代为什么可以避免?求大神解答。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • oyljerry 2017-03-09 03:32
    已采纳

    递归的时候,局部变量都分配在栈上,然后递归层数太多,就会导致栈上变量太多,导致空间不够溢出
    而迭代,每次迭代结束,局部变了会释放。就不会溢出了。

    点赞 打赏 评论
  • 坤昱 2017-03-09 03:34

    上边用的是链表储存盏形式保存内存,使用的内存可以看作一个整体,内存的大小也去类型有关系,比如int类型最大内存就是2的32次方, 16位数据类型就是2的16次方, 而递归每new一次可以看作申请了一块新的内存,只要电脑内存足够大,一般不会有问题的。

    点赞 打赏 评论

相关推荐 更多相似问题