String of Java

String 概括

string 名词,意思可以翻译为:线,弦,细绳;一串,一行等

再来看看String的类图,String的value是不是感觉很应景呢?一个个字符,串起来变成我们熟悉的字符串。
mgkwsH.md.png
这里有两个关键的field:value和hash。

String 三连击

String变量到底存储在哪里?(JDK8)

1
2
3
4
public class StringDemo {
public static void main(String[] args) {
String hello = "hello";
}

通过命令 javap -v StringDemo.class 对编译后的文件进行编码,会看到以下内容:

1
2
3
4
5
6
7
public class cn.hy.study.string.StringDemo
minor version: 0
major version: 52
flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
#1 = Methodref #4.#20 // java/lang/Object."<init>":()V
#2 = String #16 // hello

可以看到,hello 这个字符串被存在了常量池(Constant pool)中,那么常量池又会存在哪里呢?

通过下面代码,我们来看看jdk 1.8 的常量池是存在哪一块:

1
2
3
4
5
6
7
String hello = "hello";
ArrayList list = new ArrayList();
for (; ; ) {
String tmp = hello + new Random().nextInt();
hello = tmp;
list.add(tmp.intern());
}

jvm参数添加:-Xmx2m -XX:+PrintGCDetails 之后,运行不到一会儿,估计就会有下面的提醒了:

1
2
3
4
1.8
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:3332)
at ...
1
2
3
1.7
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:2367)
1
2
3
1.6
Exception in thread "main" java.lang.OutOfMemoryError: PermGen space
at java.lang.String.intern(Native Method)

堆的内存分布:

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
1.8
Heap
PSYoungGen total 1024K, used 17K [...)
eden space 512K, 3% used [...)
from space 512K, 0% used [...)
to space 512K, 0% used [...)
ParOldGen total 512K, used 401K [...)
object space 512K, 78% used [...)
Metaspace used 2728K, capacity 4486K, committed 4864K, reserved 1056768K
class space used 291K, capacity 386K, committed 512K, reserved 1048576K

1.7
Heap
PSYoungGen total 2048K, used 22K [...)
eden space 1024K, 2% used [...)
from space 1024K, 0% used [...)
to space 1024K, 0% used [...)
ParOldGen total 4096K, used 267K [...)
object space 4096K, 6% used [...)
PSPermGen total 21504K, used 2652K [...)
object space 21504K, 12% used [...)

1.6
Heap
par new generation total 1152K, used 41K [...)
eden space 1024K, 4% used [...)
from space 128K, 0% used [...)
to space 128K, 0% used [...)
concurrent mark-sweep generation total 5312K, used 279K [...)
concurrent-mark-sweep perm gen total 83968K, used 4693K [...)

我们知道jvm的内存结构,分为,堆、栈、方法区。从上面,我可以看到jdk 1.8 中字符串常量池存在于jvm的堆内存中。
综上所诉,可以看到

注:PermGen space 全程 Permanent Generation space 永久的产生的空间,也就是常说的永久代,在1.8以后已经被Meta space所代替。

String哪个方法最重要?

从问题一我们可以知道,字符串是保存到常量池中,但是常量池中保存到字符串是如何快速返回字符串给调用方呢?如果让我来设计,我会将它放在哈希表中,通过合理设计hash函数,使得字符串合理分布在哈希表中,使得我们能迅速获取已经存在常量池中的字符串。
下面是String的hashCode方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/** Cache the hash code for the string */
private int hash; // Default to 0
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;

for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

这里最难理解就是:

1
2
3
4
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
--> s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

这里为啥是31 * h
根据资料查阅,加上自己的一些理解,我觉得比较合理的解释:

  • 31 * h == (h << 5) - h,VM优化成位运算,使得计算hash code 性能更好

  • 31 是一个不大不小的奇质数,也可以使得 hashCode 尽可能均匀分布。

除了以上,我们还可以发现一个有趣的地方 if (h == 0 && value.length > 0) ,这里用到了闪存散列代码(caching the hash code),无需二次计算 hash code,是一个比较典型空间换时间的应用,它之所以行之有效,其实有一个大前提就是String是final/immutable。

哈希表,搜索的平均时间复杂度为:O(1),最坏的时间复杂度:O(n)。
质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。

String哪个方法体逻辑最难懂,分享出来。

个人觉得 split 方法是在String中相对比较难懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
        /* fastpath if the regex is a
(1)one-char String and this character is not one of the
RegEx's meta characters ".$|()[{^?*+\\", or
(2)two-char String and the first char is the backslash and
the second is not the ascii digit or ascii letter.
*/
if (((regex.value.length == 1 &&
".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
(regex.length() == 2 &&
regex.charAt(0) == '\\' &&
(((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
((ch-'a')|('z'-ch)) < 0 &&
((ch-'A')|('Z'-ch)) < 0)) &&
(ch < Character.MIN_HIGH_SURROGATE ||
ch > Character.MAX_LOW_SURROGATE))
{

这个if语句想判断 regex 是否为 fastpath 而不是正则表达式,否则直接跑下面的代码:

1
return Pattern.compile(regex).split(this, limit);

所以用这个API的时候,我们最好不要使用 ".$|()[{^?*+\\" 中的字符来进行分割,如果实在要用 需要通过 \\ 来转义。举个栗子:

1
2
3
4
5
String s = "A,b|中,c";
for (String word :
s.split("\\|")) {
System.out.println(word);
}

输出结果为:

1
2
A,b
中,c

分析完,感觉最困难的return Pattern.compile(regex).split(this, limit); 并没有分析到,下次如果有深入了解正则表达式的想法可以死磕一波。

参考

如果有不对的地方,及时指出,我会继续努力。
稳食艰难啊,老细。(中文翻译:原创不易,您的支持将鼓励我继续创作!)