背景

最近在折腾一个小工具,修改时加了一个正则匹配,启动后出现假死的情况,刚开始以为数据库连接问题,把更改的代码去掉后又恢复正常。后来逐步排查,发现是执行到一个正则匹配就卡住了。

问题原因

查阅资料,是因为正则对于+,*使用了最长匹配的方式,如果不能匹配,就会发生回溯,如果正则表达式中滥用了多个+,*等就会出现长时间回溯,CPU很高的情况。

https://stackoverflow.com/questions/34032350/high-cpu-utilization-on-regex-pattern-matching

http://www.regular-expressions.info/catastrophic.html

验证

我们使用以下代码验证

public class PatternTest {

    public static void main(String[] args) throws Exception{
        String input = "123456789012345";
        List<String> patternList = new ArrayList<>();
        patternList.add("\\w#");
        patternList.add("(\\w+)+#");
        patternList.add("((\\w+)+)+#");
        testSpeed(input, patternList.toArray(new String[0]));
        patternList = patternList.stream().map(e -> e.replace("+", "*")).collect(Collectors.toList());
        testSpeed(input, patternList.toArray(new String[0]));

    }

    private static void testSpeed(String input, String... regex){
        MyStopWatch stopWatch = new MyStopWatch();
        for(String item : regex){
            stopWatch.resetAndStart();
            System.out.println(Pattern.matches(item, input));
            System.out.println(stopWatch.getTime());
        }
        System.out.println("-------------------------");
    }

}

最后结果:

false
1
false
6
false
1505
-------------------------
false
0
false
4
false
37108
-------------------------

结论和问题解决

可以看出,对分组使用+或者*,然后再嵌套+或者*,在不匹配的情况下,会极大的增加回溯次数,所以我们应当尽量避免这种写法,比如将(\\w+)+ 写成\\w+就可以了