String 调优
以上是几个版本JDK中String对象的组成。
JDK6的时候是通过offset和count来定位char[]数组;
JDK7去处了offset和count,解决了substring方法导致的内存泄漏问题(该方法里的char数组仍然指向原字符串导致String字符串无法回收);
JDK9使用byte[]来代替char,char是两个byte,因此9的String更节省空间,coder的作用适用于在indexOf()
函数时,计算字符串长度,coder属性有0,1两个值,0代表Latin-1(单字节编码),1代表UTF-16(双字节编码)。
在Java中,常用的构造字符串的方式有两种:
1 | String str = "abc"; |
第一种:str引用的是字符串常量池的地址;
第二种:编译类文件时,“abc”加入到类常量,类加载时,字符串将会在常量池中创建;最后在new时,调用构造函数,同时引用常量池中的“abc”字符串,在堆内存中创建一个String对象,最后将str指向String对象;
字符串常量会直接放到字符串常量池,字符串变量对象是创建在堆内存中,同时也会在字符串常量池中创建一个字符串对象,复制到堆内存对象中,并返回堆内存引用。
如果在运行时创建字符串对象,例如new 了一个包含String类型成员变量的类,那么这个字符串对象会放入到堆中,只有当调用intern方法时并且常量池中没有时,才会将这个字符串对象放到常量池中,以后当堆中其他的字符串对象调用intern方法获取字符串引用对象时,才会去常量池中判断是否有相同值的字符串的引用并且返回(JDK7以后)。JDK6的做法是调用intern方法会去常量池中创建常量并且返回字符串引用。
所以,对于类似国家、地名等具有重复性的名字,可以使用intern方法来节省空间。
常量池分为:类文件常量池,运行时常量池,字符串常量池。JDK7之前运行时常量池包含字符串常量池,都在方法区,此时对方法区的实现为永久代;
JDK7运行时常量池还在方法区,但是字符串常量池放到了堆;
JDK8时,永久代移除,变为了元空间,此时运行时常量池在元空间,字符串常量池在堆。
正则表达式
DFA自动机(Deterministic Final Automaton确定有限状态自动机):时间复杂度为O(n);
NFA自动机(Non Deterministic Final Automaton非确定有限状态自动机):时间复杂度O(ns),s为状态数,拥有捕获group等,需要基于子表达式独立进行匹配,因此编程语言库里的正则表达式基本都是基于这种方式实现;
原理
1 | text = "abbc" |
- 贪婪模式(Greddy)单独使用+、?、*或者{min,max}等量词,正则表达式会匹配尽可能多的内容
- 懒惰模式(Reluctant)在贪婪模式的正则字符串后面加?即可,尽可能少的匹配内容
- 独占模式(Possessive)在贪婪模式的正则字符串后面加+即可,匹配不上直接结束
懒惰模式和独占模式都可以尽量减少回溯,但是不能完全杜绝。
懒惰模式:
1 | text = "abbc" |
- a匹配a
- b匹配b{1,3}
- b不匹配c ,正则回溯
- b匹配b
- c匹配c
独占模式:
1 | text = "abbc" |
- a匹配a
- b匹配b{1,3}
- b匹配b{1,3}
- c不匹配b{1,3},原文开始回溯
- c匹配c
所以最终匹配成功。
1 | text = "abbc" |
- a匹配a
- b匹配b{1,3}
- b匹配b{1,3}
- c不匹配b{1,3},原文回溯
- c不匹配b
最终匹配失败。
结论
- 尽量使用懒惰模式和独占模式
- 减少分支选择
- 三次index性能大于(x|y|z)
- 减少捕获嵌套,一个捕获组通常就是一个()