不得不知道的Java内存溢出之使用非递归遍历树形结构

        最近做的项目我做的是菜单的管理,而菜单采用的是树形结构。

        在菜单的添加时,添加了一个需求,就是采用xml的形式进行导入。这个想都没有想用的dom4j,然后采用了一个很常规的递归算法,就将问题解决了,当时测试的数据模块页面加起来一共6个,加上系统一共分了四级(xml如下,PS为了省篇幅,去掉了不影响写文章的标签):

<system>
	<module name="模块1" sn="mk3" priority="1" description="这是第一个模块" >
		<page name="页面1" sn="qwer9" priority="1" url="/gxpt_web_*_*/*/*.action" description="这里第一个模块里面的页面">
		</page>
		<module name="模块2" sn="mk4" priority="2" description="这是第二个模块" >
			<page name="页面2" sn="qwer8" priority="1" url="/gxpt_web_*_*/*/*.action" description="这里第二个模块里面的页面">
			</page>
		</module>
	</module>	
	<page name="页面3" sn="qwer7" priority="3" url="/gxpt_web_*_*/*/*.action" description="这是一个根目录下的页面">
	</page>
</system>

        而我的算法呢,也是超级简单的,只说明算法,如下:

        

import(ListOfElement){
	for(iterator iter=ListOfElement.iterator();iter.hasNext();){
		Element ele=iter.next();
		Object o=Xml2Obj(ele);	//Xml2Obj是一个将Element转成Obj的方法
		
		if(ele.elements()!=null && ele.elements().size()>0){
			import(ele.elements());
		}
	}
}

        而且事实证明也可以使用,但是后来交付使用的时候,对方一导入,发现页面就呈现假死的状态,看了下控制台,说内存溢出。于是就查了下JBoss怎样将内存弄大,结果弄大了,发现速度不是一般的慢。

        这怎么能行,于是上网查了一下,说递归极有可能造成内存溢出(后来发现这确是我的程序造成内在溢出的原因之一)。不论怎么说,先把递归改了吧。

        这下我可挠头了,因为之前看数据结构与算法的时候,到树的遍历的时候,都是用的递归。而非递归的周游树,只在二叉树那才有。但既然都是树,二叉树可以使用那种方法周游,这个应该也能才对。在此严重鄙视一下编书的人,为什么不在一个公共的时候写所有的通用的!

        稍微多看了会(没有认真学过指针,看起来真心有点费劲),也从网上找了个论文来看(没看懂…),然后顺利的将递归改为了非递归:

        算法如下:

import(ListOfElement){
	Queue queue=new LinkedList();	//采用Java里面的队列(LILO)
	for(iterator iter=ListOfElement.iterator();iter.hasNext();){
		queue.add(iter.next());
		while(!queue.isEmpty()){
			Element ele=queue.poll();  //poll和remove的区别是如果为空,remove会抛异常,而poll返回空
			Object o=Xml2Obj(ele);	
			if(ele.elements()!=null && ele.elements().size()>0){				
				for(iterator iterChild=ele.elements();iterChild.hasNext){
					queue.add(iterChild.next());
				}
			}
		}
	}
}

        但是为什么说递归容易造成内存溢出呢?是因为在递归调用的时候,如果深度无法控制,会造成很长的方法链存在,而当达到一定数量后,内存会成倍的增长。

        但有一点需要说明:那就是并不是你用了递归就一定造成内在溢出,因为我改成非递归后,发现内在还是溢出。那么还有什么原因造成了我的内存溢出呢?

        PS:如果不改成非递归,修改了那个地方还是溢出,所以我的代码有两处漏洞造成了内在溢出。下个问题到底是什么呢?下篇文章进行说明。

不得不知道的Java内存溢出之使用非递归遍历树形结构,布布扣,bubuko.com

不得不知道的Java内存溢出之使用非递归遍历树形结构

上一篇:C++中的allocator类(内存分配器)


下一篇:Java回调机制解析