写在前面

1、String在java源码中是怎么实现的？
2、什么是正则表达式的DFA自动机和NFA自动机？

1、String

1.1、String底层实现

Java 6及以前版本，通过char数组，每个char占用两个字节，使得String能够很好地处理Unicode。

public final class String implements java.io.Serializable, Comparable<String>, CharSequence {  private final char[] value;  private int offset;  private int count;  // ...其他成员和方法  
}  

Java 7至Java 8版本，offset和count两个变量被移除，String.substring不再共享char[]，解决内存可能泄漏问题。

public final class String implements java.io.Serializable, Comparable<String>, CharSequence {  private final char[] value;  // ...其他成员和方法  
}  

Java9开始，把char[]改成了byte[] + coder(编码标识)

1.2、str="abc"和new String(“abc”)的区别

• str=“abc”
  会先检查"abc"在不在常量池，在就不创建了，直接拿引用
• new String(“abc”)
  先将”abc“放入常量池，再将其引用传给new的String

1.3、使用+拼接字符串

使用+拼接字符串，代码编译后，会被替换成StringBuilder。并且每+的一个字符串都可能被new一个新的StringBuilder，所以建议少用+，直接用StringBuilder

1.4、如何使用String.intern节约内存

String a = new String(“a123”).intern();
当调用intern()时，会先查看常量池中是否已有字符串”a123“, 所以当多次用到”a123“时，使用String.intern不会再创建新的字符串，从而节约内存。

1.5、分割字符，split()和indexOf()用哪个

split()使用正则表达式实现，正则表达式性能是比较不稳定的。
indexOf()能分割时尽量用indexOf()

2、正则表达式

2.1、DFA和NFA

正则表达式引擎	构造代价	执行效率	优势
NFA	小	低	支持更多，如group、环视、占有有限量词
DFA	大	高

NFA 自动机回溯

str = "arrrc"
reg = "ar{1,3}c"自动回溯会先匹配arrr,匹配到c,发现不是r,就回溯到最后一个r,用reg的c去继续匹配

2.2、怎么减少回溯?

1、贪婪模式
如上述例子就是贪婪模式
2、懒惰模式

str = "arrrc"
reg = "ar{1,3}?c"懒惰模式会先匹配ar,发现已经有一个r了,就开始用c接着匹配

3、独占模式

str = "arrc"
reg = "ar{1,3}+rc"独占模式会先匹配ar,发现已经有一个r了,就开始用rc接着匹配,不会回溯

下面这种独占模式会回溯

str = "arrc"
reg = "ar{1,3}+c"独占模式会先匹配ar,发现已经有一个r了,就开始用c接着匹配,匹配失败回溯

总结：
1、少用贪婪模式，多用独占模式
2、减少分支选择，如将”(abcd|abef)“替换为”ab(cd|ef)“
3、减少捕获嵌套。
捕获组： 一个 （）里面的就是一个不获取
非捕获组：一个（?:EXP）就是一个非捕获组

str = "<input id=1>文本</input>"
reg = "(<input.*?)(.*?)(</input)"
# 上面reg包含了3个捕获组，所以如果输出捕获结果会有整个匹配到的内容+括号里面的，4组字符串str = "<input id=1>文本</input>"
reg = "(?:<input.*?)(.*?)(?:</input)"
# 上面reg包含了1个捕获组，所以如果输出捕获结果会有整个匹配到的内容+捕获组括号里面的，2组字符串