爆栈

什么是爆栈

爆栈:栈满(StackOverFlow)使得方法无法获取栈空间,而导致应用crash。
爆栈是StackOverFlow的一种,只不过上层调用的是本地方法,才有可能导致出现crash,而非Native方法,则会直接抛出StackOverFlow OOM错误。

栈默认大小

系统 栈大小(默认)
JVM 1M
Windows 1M
CentOS7 8M
MacOS 8M

爆栈问题解决办法

手动扩栈

jvm

jvm中,默认栈大小是1M,可以通过如下命令查看。

1
$ java -XX:+PrintFlagsFinal -version | grep -i 'stack'

手动扩大JVM栈可以通过显式设置-Xss或-XX:ThreadStackSize。

CentOS系统

1
2
3
4
# 显示当前用户的栈大小
$ ulimit -a
# 将当前用户的栈大小设置为32M bytes
$ ulimit -s 32768

使用BFS

DFS(深度优先),有可能递归深度很深,因此会造成stack overflow。
BFS(广度优先),宽度有可能扩得很宽,因此耗费额外堆空间,但不会爆栈。

BFS(Breadth First Search),其主要思想是从起始点开始,将其邻近的所有顶点都加到一个队列(FIFO)中去,然后标记下这些顶点离起始顶点的距离为1.最后将起始顶点标记为已访问,今后就不会再访问。然后再从队列中取出最先进队的顶点A,也取出其周边邻近节点,加入队列末尾,将这些顶点的距离相对A再加1,最后离开这个顶点A。依次下去,直到队列为空为止。从上面描述的过程我们知道每个顶点被访问的次数最多一次(已访问的节点不会再访问),而对于连通图来说,每个顶点都会被访问。加上每个顶点的邻接链表都会被遍历,因此BFS的时间复杂度是Θ(V+E),其中V是顶点个数,E是边数,也就是所有邻接表中的元素个数。为了更好的说明这个过程,下图列出了对一个图的BFS的过程
BFS.png
示例代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void bfs(HashMap<Character, LinkedList<Character>> graph,HashMap<Character, Integer> dist,char start)
{
Queue<Character> q=new LinkedList<>();
q.add(start);//将s作为起始顶点加入队列
dist.put(start, 0);
int i=0;
while(!q.isEmpty())
{
char top=q.poll();//取出队首元素
i++;
System.out.println("The "+i+"th element:"+top+" Distance from s is:"+dist.get(top));
int d=dist.get(top)+1;//得出其周边还未被访问的节点的距离
for (Character c : graph.get(top)) {
if(!dist.containsKey(c))//如果dist中还没有该元素说明还没有被访问
{
dist.put(c, d);
q.add(c);
}
}
}
}

使用数组模拟栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Stack {

//将存储的元素定义为 Object
Object[] elements;

//定义一个指向栈顶元素的 标志
int index;

//无参的构造函数
Stack() {

}
//有参数的构造函数
Stack(int max){
elements=new Object[max];
}

//入栈的操作
public void push(Object element) throws StackOperationException{
if(index==elements.length){
throw new StackOperationException("栈已满");
}

elements[index]=element;

index++;
}

//出栈操作
public Object pop() throws StackOperationException{

if(index==0){
throw new StackOperationException("栈中没有元素");
}
index--;

return elements[index];
}
坚持原创技术分享,您的支持将鼓励我继续创作!
0%