Dunwu Blog

大道至简,知易行难

深入理解 Java String 类型

String 类型可能是 Java 中应用最频繁的引用类型,但它的性能问题却常常被忽略。高效的使用字符串,可以提升系统的整体性能。当然,要做到高效使用字符串,需要深入了解其特性。

String 的不可变性

我们先来看下 String 的定义:

1
2
3
4
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence {
/** The value is used for character storage. */
private final char value[];

String 类被 final 关键字修饰,表示不可继承 String

String 类的数据存储于 char[] 数组,这个数组被 final 关键字修饰,表示 String 对象不可被更改

为什么 Java 要这样设计?

(1)保证 String 对象安全性。避免 String 被篡改。

(2)保证 hash 值不会频繁变更

(3)可以实现字符串常量池。通常有两种创建字符串对象的方式,一种是通过字符串常量的方式创建,如 String str="abc"; 另一种是字符串变量通过 new 形式的创建,如 String str = new String("abc")

使用第一种方式创建字符串对象时,JVM 首先会检查该对象是否在字符串常量池中,如果在,就返回该对象引用,否则新的字符串将在常量池中被创建。这种方式可以减少同一个值的字符串对象的重复创建,节约内存。

String str = new String("abc") 这种方式,首先在编译类文件时,"abc" 常量字符串将会放入到常量结构中,在类加载时,"abc" 将会在常量池中创建;其次,在调用 new 时,JVM 命令将会调用 String 的构造函数,同时引用常量池中的 "abc" 字符串,在堆内存中创建一个 String 对象;最后,str 将引用 String 对象。

String 的性能考量

字符串拼接

字符串常量的拼接,编译器会将其优化为一个常量字符串

【示例】字符串常量拼接

1
2
3
4
5
6
public static void main(String[] args) {
// 本行代码在 class 文件中,会被编译器直接优化为:
// String str = "abc";
String str = "a" + "b" + "c";
System.out.println("str = " + str);
}

字符串变量的拼接,编译器会优化成 StringBuilder 的方式

【示例】字符串变量的拼接

1
2
3
4
5
6
7
8
public static void main(String[] args) {
String str = "";
for(int i=0; i<1000; i++) {
// 本行代码会被编译器优化为:
// str = (new StringBuilder(String.valueOf(str))).append(i).toString();
str = str + i;
}
}

但是,每次循环都会生成一个新的 StringBuilder 实例,同样也会降低系统的性能。

字符串拼接的正确方案:

  • 如果需要使用字符串拼接,应该优先考虑 StringBuilderappend 方法替代使用 +
  • 如果在并发编程中,String 对象的拼接涉及到线程安全,可以使用 StringBuffer。但是要注意,由于 StringBuffer 是线程安全的,涉及到锁竞争,所以从性能上来说,要比 StringBuilder 差一些。

字符串分割

Stringsplit() 方法使用正则表达式实现其强大的分割功能。而正则表达式的性能是非常不稳定的,使用不恰当会引起回溯问题,很可能导致 CPU 居高不下。

所以,应该慎重使用 split() 方法,可以考虑用 String.indexOf() 方法代替 split() 方法完成字符串的分割。如果实在无法满足需求,你就在使用 Split() 方法时,对回溯问题加以重视就可以了。

String.intern

在每次赋值的时候使用 Stringintern 方法,如果常量池中有相同值,就会重复使用该对象,返回对象引用,这样一开始的对象就可以被回收掉

在字符串常量中,默认会将对象放入常量池;在字符串变量中,对象是会创建在堆内存中,同时也会在常量池中创建一个字符串对象,复制到堆内存对象中,并返回堆内存对象引用。

如果调用 intern 方法,会去查看字符串常量池中是否有等于该对象的字符串,如果没有,就在常量池中新增该对象,并返回该对象引用;如果有,就返回常量池中的字符串引用。堆内存中原有的对象由于没有引用指向它,将会通过垃圾回收器回收。

【示例】

1
2
3
4
5
6
7
8
9
10
public class SharedLocation {

private String city;
private String region;
private String countryCode;
}

SharedLocation sharedLocation = new SharedLocation();
sharedLocation.setCity(messageInfo.getCity().intern()); sharedLocation.setCountryCode(messageInfo.getRegion().intern());
sharedLocation.setRegion(messageInfo.getCountryCode().intern());

使用 intern 方法需要注意:一定要结合实际场景。因为常量池的实现是类似于一个 HashTable 的实现方式,HashTable 存储的数据越大,遍历的时间复杂度就会增加。如果数据过大,会增加整个字符串常量池的负担。

String、StringBuffer、StringBuilder 有什么区别

String 是 Java 语言非常基础和重要的类,提供了构造和管理字符串的各种基本逻辑。它是典型的 Immutable 类,被声明成为 final class,所有属性也都是 final 的。也由于它的不可变性,类似拼接、裁剪字符串等动作,都会产生新的 String 对象。由于字符串操作的普遍性,所以相关操作的效率往往对应用性能有明显影响。

StringBuffer 是为解决上面提到拼接产生太多中间对象的问题而提供的一个类,我们可以用 append 或者 add 方法,把字符串添加到已有序列的末尾或者指定位置。StringBuffer 是一个线程安全的可修改字符序列。StringBuffer 的线程安全是通过在各种修改数据的方法上用 synchronized 关键字修饰实现的。

StringBuilder 是 Java 1.5 中新增的,在能力上和 StringBuffer 没有本质区别,但是它去掉了线程安全的部分,有效减小了开销,是绝大部分情况下进行字符串拼接的首选。

StringBufferStringBuilder 底层都是利用可修改的(char,JDK 9 以后是 byte)数组,二者都继承了 AbstractStringBuilder,里面包含了基本操作,区别仅在于最终的方法是否加了 synchronized。构建时初始字符串长度加 16(这意味着,如果没有构建对象时输入最初的字符串,那么初始值就是 16)。我们如果确定拼接会发生非常多次,而且大概是可预计的,那么就可以指定合适的大小,避免很多次扩容的开销。扩容会产生多重开销,因为要抛弃原有数组,创建新的(可以简单认为是倍数)数组,还要进行 arraycopy

**除非有线程安全的需要,不然一般都使用 StringBuilder**。

参考资料

Java 正则从入门到精通

关键词:Pattern、Matcher、捕获与非捕获、反向引用、零宽断言、贪婪与懒惰、元字符、DFA、NFA

正则简介

正则表达式是什么

正则表达式(Regular Expression)是一个用正则符号写出的公式,程序对这个公式进行语法分析,建立一个语法分析树,再根据这个分析树结合正则表达式的引擎生成执行程序(这个执行程序我们把它称作状态机,也叫状态自动机),用于字符匹配。

如何学习正则

正则表达式是一个强大的文本匹配工具,但是它的规则很复杂,理解起来较为困难,容易让人望而生畏。

刚接触正则时,我看了一堆正则的语义说明,但是仍然不明所以。后来,我多接触一些正则的应用实例,渐渐有了感觉,再结合语义说明,终有领悟。我觉得正则表达式和武侠修练武功差不多,应该先练招式,再练心法。如果一开始就直接看正则的规则,保证你会懵逼。当你熟悉基本招式(正则基本使用案例)后,也该修炼修炼心法(正则语法)了。真正的高手不能只靠死记硬背那么几招把式。就像张三丰教张无忌太极拳一样,领悟心法,融会贯通,少侠你就可以无招胜有招,成为传说中的绝世高手。

以上闲话可归纳为一句:学习正则应该从实例去理解规则。

正则工具类

JDK 中的 java.util.regex 包提供了对正则表达式的支持。

java.util.regex 有三个核心类:

  • Pattern 类:Pattern 是一个正则表达式的编译表示。
  • Matcher 类:Matcher 是对输入字符串进行解释和匹配操作的引擎。
  • PatternSyntaxException:PatternSyntaxException 是一个非强制异常类,它表示一个正则表达式模式中的语法错误。

注:需要格外注意一点,在 Java 中使用反斜杠”\“时必须写成 "\\"。所以本文的代码出现形如 String regex = "\\$\\{.*?\\}" 其实就是 \$\{.\*?\}

Pattern 类

Pattern类没有公共构造方法。要创建一个Pattern对象,你必须首先调用其静态方法compile,加载正则规则字符串,然后返回一个 Pattern 对象。

Pattern类一样,Matcher类也没有公共构造方法。你需要调用Pattern对象的matcher方法来获得一个Matcher对象。

【示例】Pattern 和 Matcher 的初始化

1
2
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);

Matcher 类

Matcher 类可以说是 java.util.regex 中的核心类,它有三类功能:校验、查找、替换。

校验

为了校验文本是否与正则规则匹配,Matcher 提供了以下几个返回值为 boolean 的方法。

序号 方法及说明
1 **public boolean lookingAt() ** 尝试将从区域开头开始的输入序列与该模式匹配。
2 **public boolean find() **尝试查找与该模式匹配的输入序列的下一个子序列。
3 public boolean find(int start)重置此匹配器,然后尝试查找匹配该模式、从指定索引开始的输入序列的下一个子序列。
4 **public boolean matches() **尝试将整个区域与模式匹配。

如果你傻傻分不清上面的查找方法有什么区别,那么下面一个例子就可以让你秒懂。

【示例】lookingAt、find、matches

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
39
40
41
public static void main(String[] args) {
checkLookingAt("hello", "helloworld");
checkLookingAt("world", "helloworld");

checkFind("hello", "helloworld");
checkFind("world", "helloworld");

checkMatches("hello", "helloworld");
checkMatches("world", "helloworld");
checkMatches("helloworld", "helloworld");
}

private static void checkLookingAt(String regex, String content) {
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
if (m.lookingAt()) {
System.out.println(content + "\tlookingAt: " + regex);
} else {
System.out.println(content + "\tnot lookingAt: " + regex);
}
}

private static void checkFind(String regex, String content) {
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
if (m.find()) {
System.out.println(content + "\tfind: " + regex);
} else {
System.out.println(content + "\tnot find: " + regex);
}
}

private static void checkMatches(String regex, String content) {
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
if (m.matches()) {
System.out.println(content + "\tmatches: " + regex);
} else {
System.out.println(content + "\tnot matches: " + regex);
}
}

输出:

1
2
3
4
5
6
7
helloworld	lookingAt: hello
helloworld not lookingAt: world
helloworld find: hello
helloworld find: world
helloworld not matches: hello
helloworld not matches: world
helloworld matches: helloworld

说明

regex = "world" 表示的正则规则是以 world 开头的字符串,regex = "hello"regex = "helloworld" 也是同理。

  • lookingAt方法从头部开始,检查 content 字符串是否有子字符串于正则规则匹配。
  • find方法检查 content 字符串是否有子字符串于正则规则匹配,不管字符串所在位置。
  • matches方法检查 content 字符串整体是否与正则规则匹配。

查找

为了查找文本匹配正则规则的位置,Matcher提供了以下方法:

序号 方法及说明
1 **public int start() **返回以前匹配的初始索引。
2 public int start(int group) 返回在以前的匹配操作期间,由给定组所捕获的子序列的初始索引
3 **public int end()**返回最后匹配字符之后的偏移量。
4 **public int end(int group)**返回在以前的匹配操作期间,由给定组所捕获子序列的最后字符之后的偏移量。
5 **public String group()**返回前一个符合匹配条件的子序列。
6 **public String group(int group)**返回指定的符合匹配条件的子序列。

【示例】使用 start()、end()、group() 查找所有匹配正则条件的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
final String regex = "world";
final String content = "helloworld helloworld";
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
System.out.println("content: " + content);

int i = 0;
while (m.find()) {
i++;
System.out.println("[" + i + "th] found");
System.out.print("start: " + m.start() + ", ");
System.out.print("end: " + m.end() + ", ");
System.out.print("group: " + m.group() + "\n");
}
}

输出

1
2
3
4
5
content: helloworld helloworld
[1th] found
start: 5, end: 10, group: world
[2th] found
start: 16, end: 21, group: world

说明

例子很直白,不言自明了吧。

替换

替换方法是替换输入字符串里文本的方法:

序号 方法及说明
1 **public Matcher appendReplacement(StringBuffer sb, String replacement)**实现非终端添加和替换步骤。
2 **public StringBuffer appendTail(StringBuffer sb)**实现终端添加和替换步骤。
3 **public String replaceAll(String replacement) ** 替换模式与给定替换字符串相匹配的输入序列的每个子序列。
4 public String replaceFirst(String replacement) 替换模式与给定替换字符串匹配的输入序列的第一个子序列。
5 **public static String quoteReplacement(String s)**返回指定字符串的字面替换字符串。这个方法返回一个字符串,就像传递给 Matcher 类的 appendReplacement 方法一个字面字符串一样工作。

【示例】replaceFirst 和 replaceAll

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
String regex = "can";
String replace = "can not";
String content = "I can because I think I can.";

Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);

System.out.println("content: " + content);
System.out.println("replaceFirst: " + m.replaceFirst(replace));
System.out.println("replaceAll: " + m.replaceAll(replace));
}

输出

1
2
3
content: I can because I think I can.
replaceFirst: I can not because I think I can.
replaceAll: I can not because I think I can not.

说明

replaceFirst:替换第一个匹配正则规则的子序列。

replaceAll:替换所有匹配正则规则的子序列。

【示例】appendReplacement、appendTail 和 replaceAll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
String regex = "can";
String replace = "can not";
String content = "I can because I think I can.";
StringBuffer sb = new StringBuffer();
StringBuffer sb2 = new StringBuffer();

System.out.println("content: " + content);
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
while (m.find()) {
m.appendReplacement(sb, replace);
}
System.out.println("appendReplacement: " + sb);
m.appendTail(sb);
System.out.println("appendTail: " + sb);
}

输出

1
2
3
content: I can because I think I can.
appendReplacement: I can not because I think I can not
appendTail: I can not because I think I can not.

说明

从输出结果可以看出,appendReplacementappendTail方法组合起来用,功能和replaceAll是一样的。

如果你查看replaceAll的源码,会发现其内部就是使用appendReplacementappendTail方法组合来实现的。

【示例】quoteReplacement 和 replaceAll,解决特殊字符替换问题

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
String regex = "\\$\\{.*?\\}";
String replace = "${product}";
String content = "product is ${productName}.";

Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
String replaceAll = m.replaceAll(replace);

System.out.println("content: " + content);
System.out.println("replaceAll: " + replaceAll);
}

输出

1
2
3
4
5
6
7
8
9
10
Exception in thread "main" java.lang.IllegalArgumentException: No group with name {product}
at java.util.regex.Matcher.appendReplacement(Matcher.java:849)
at java.util.regex.Matcher.replaceAll(Matcher.java:955)
at org.zp.notes.javase.regex.RegexDemo.wrongMethod(RegexDemo.java:42)
at org.zp.notes.javase.regex.RegexDemo.main(RegexDemo.java:18)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:498)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

说明

String regex = "\\$\\{.*?\\}";表示匹配类似${name}这样的字符串。由于${}都是特殊字符,需要用反义字符\来修饰才能被当做一个字符串字符来处理。

上面的例子是想将 ${productName} 替换为 ${product} ,然而replaceAll方法却将传入的字符串中的$当做特殊字符来处理了。结果产生异常。

如何解决这个问题?

JDK1.5 引入了quoteReplacement方法。它可以用来转换特殊字符。其实源码非常简单,就是判断字符串中如果有\$,就为它加一个转义字符\

我们对上面的代码略作调整:

m.replaceAll(replace)改为m.replaceAll(Matcher.quoteReplacement(replace)),新代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
String regex = "\\$\\{.*?\\}";
String replace = "${product}";
String content = "product is ${productName}.";

Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
String replaceAll = m.replaceAll(Matcher.quoteReplacement(replace));

System.out.println("content: " + content);
System.out.println("replaceAll: " + replaceAll);
}

输出

1
2
content: product is ${productName}.
replaceAll: product is ${product}.

说明

字符串中如果有\$,不能被正常解析的问题解决。

元字符

元字符(metacharacters)就是正则表达式中具有特殊意义的专用字符。

基本元字符

正则表达式的元字符难以记忆,很大程度上是因为有很多为了简化表达而出现的等价字符。而实际上最基本的元字符,并没有那么多。对于大部分的场景,基本元字符都可以搞定。让我们从一个个实例出发,由浅入深的去体会正则的奥妙。

多选(|

【示例】匹配一个确定的字符串

1
checkMatches("abc", "abc");

如果要匹配一个确定的字符串,非常简单,如例 1 所示。但是,如果你不确定要匹配的字符串,希望有多个选择,怎么办?答案是:使用元字符| ,它的含义是或。

【示例】匹配多个可选的字符串

1
2
3
4
5
6
7
8
9
// 测试正则表达式字符:|
Assert.assertTrue(checkMatches("yes|no", "yes"));
Assert.assertTrue(checkMatches("yes|no", "no"));
Assert.assertFalse(checkMatches("yes|no", "right"));

// 输出
// yes matches: yes|no
// no matches: yes|no
// right not matches: yes|no

分组(()

如果你希望表达式由多个子表达式组成,你可以使用 ()

【示例】匹配组合字符串

1
2
3
4
5
6
7
8
9
10
Assert.assertTrue(checkMatches("(play|end)(ing|ed)", "ended"));
Assert.assertTrue(checkMatches("(play|end)(ing|ed)", "ending"));
Assert.assertTrue(checkMatches("(play|end)(ing|ed)", "playing"));
Assert.assertTrue(checkMatches("(play|end)(ing|ed)", "played"));

// 输出
// ended matches: (play|end)(ing|ed)
// ending matches: (play|end)(ing|ed)
// playing matches: (play|end)(ing|ed)
// played matches: (play|end)(ing|ed)

指定单字符有效范围([]

前面展示了如何匹配字符串,但是很多时候你需要精确的匹配一个字符,这时可以使用[]

【示例】字符在指定范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 测试正则表达式字符:[]
Assert.assertTrue(checkMatches("[abc]", "b")); // 字符只能是a、b、c
Assert.assertTrue(checkMatches("[a-z]", "m")); // 字符只能是a - z
Assert.assertTrue(checkMatches("[A-Z]", "O")); // 字符只能是A - Z
Assert.assertTrue(checkMatches("[a-zA-Z]", "K")); // 字符只能是a - z和A - Z
Assert.assertTrue(checkMatches("[a-zA-Z]", "k"));
Assert.assertTrue(checkMatches("[0-9]", "5")); // 字符只能是0 - 9

// 输出
// b matches: [abc]
// m matches: [a-z]
// O matches: [A-Z]
// K matches: [a-zA-Z]
// k matches: [a-zA-Z]
// 5 matches: [0-9]

指定单字符无效范围( [^]

【示例】字符不能在指定范围

如果需要匹配一个字符的逆操作,即字符不能在指定范围,可以使用[^]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 测试正则表达式字符:[^]
Assert.assertFalse(checkMatches("[^abc]", "b")); // 字符不能是a、b、c
Assert.assertFalse(checkMatches("[^a-z]", "m")); // 字符不能是a - z
Assert.assertFalse(checkMatches("[^A-Z]", "O")); // 字符不能是A - Z
Assert.assertFalse(checkMatches("[^a-zA-Z]", "K")); // 字符不能是a - z和A - Z
Assert.assertFalse(checkMatches("[^a-zA-Z]", "k"));
Assert.assertFalse(checkMatches("[^0-9]", "5")); // 字符不能是0 - 9

// 输出
// b not matches: [^abc]
// m not matches: [^a-z]
// O not matches: [^A-Z]
// K not matches: [^a-zA-Z]
// k not matches: [^a-zA-Z]
// 5 not matches: [^0-9]

限制字符数量({}

如果想要控制字符出现的次数,可以使用 {}

字符 描述
{n} n 是一个非负整数。匹配确定的 n 次。
{n,} n 是一个非负整数。至少匹配 n 次。
{n,m} m 和 n 均为非负整数,其中 n <= m。最少匹配 n 次且最多匹配 m 次。

【示例】限制字符出现次数

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
// {n}: n 是一个非负整数。匹配确定的 n 次。
checkMatches("ap{1}", "a");
checkMatches("ap{1}", "ap");
checkMatches("ap{1}", "app");
checkMatches("ap{1}", "apppppppppp");

// {n,}: n 是一个非负整数。至少匹配 n 次。
checkMatches("ap{1,}", "a");
checkMatches("ap{1,}", "ap");
checkMatches("ap{1,}", "app");
checkMatches("ap{1,}", "apppppppppp");

// {n,m}: m 和 n 均为非负整数,其中 n <= m。最少匹配 n 次且最多匹配 m 次。
checkMatches("ap{2,5}", "a");
checkMatches("ap{2,5}", "ap");
checkMatches("ap{2,5}", "app");
checkMatches("ap{2,5}", "apppppppppp");

// 输出
// a not matches: ap{1}
// ap matches: ap{1}
// app not matches: ap{1}
// apppppppppp not matches: ap{1}
// a not matches: ap{1,}
// ap matches: ap{1,}
// app matches: ap{1,}
// apppppppppp matches: ap{1,}
// a not matches: ap{2,5}
// ap not matches: ap{2,5}
// app matches: ap{2,5}
// apppppppppp not matches: ap{2,5}

转义字符(/

如果想要查找元字符本身,你需要使用转义符,使得正则引擎将其视作一个普通字符,而不是一个元字符去处理。

1
2
3
4
5
6
* 的转义字符:\*
+ 的转义字符:\+
? 的转义字符:\?
^ 的转义字符:\^
$ 的转义字符:\$
. 的转义字符:\.

如果是转义符 \ 本身,你需要使用 \\

指定表达式字符串的开始(^)和结尾($

如果希望匹配的字符串必须以特定字符串开头,可以使用 ^

注意:请特别留意,这里的 ^ 一定要和 [^] 中的 ^ 区分。

【示例】限制字符串头部

1
2
3
4
5
6
Assert.assertTrue(checkMatches("^app[a-z]{0,}", "apple")); // 字符串必须以app开头
Assert.assertFalse(checkMatches("^app[a-z]{0,}", "aplause"));

// 输出
// apple matches: ^app[a-z]{0,}
// aplause not matches: ^app[a-z]{0,}

如果希望匹配的字符串必须以特定字符串结尾,可以使用 $

【示例】限制字符串尾部

1
2
3
4
5
6
Assert.assertTrue(checkMatches("[a-z]{0,}ing$", "playing")); // 字符串必须以ing结尾
Assert.assertFalse(checkMatches("[a-z]{0,}ing$", "long"));

// 输出
// playing matches: [a-z]{0,}ing$
// long not matches: [a-z]{0,}ing$

等价字符

等价字符,顾名思义,就是对于基本元字符表达的一种简化(等价字符的功能都可以通过基本元字符来实现)。

在没有掌握基本元字符之前,可以先不用理会,因为很容易把人绕晕。

等价字符的好处在于简化了基本元字符的写法。

表示某一类型字符的等价字符

下表中的等价字符都表示某一类型的字符。

字符 描述
. 匹配除“\n”之外的任何单个字符。
\d 匹配一个数字字符。等价于[0-9]。
\D 匹配一个非数字字符。等价于[^0-9]。
\w 匹配包括下划线的任何单词字符。类似但不等价于“[A-Za-z0-9_]”,这里的单词字符指的是 Unicode 字符集。
\W 匹配任何非单词字符。
\s 匹配任何不可见字符,包括空格、制表符、换页符等等。等价于[ \f\n\r\t\v]。
\S 匹配任何可见字符。等价于[ \f\n\r\t\v]。

【示例】基本等价字符的用法

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
// 匹配除“\n”之外的任何单个字符
Assert.assertTrue(checkMatches(".{1,}", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_"));
Assert.assertTrue(checkMatches(".{1,}", "~!@#$%^&*()+`-=[]{};:<>,./?|\\"));
Assert.assertFalse(checkMatches(".", "\n"));
Assert.assertFalse(checkMatches("[^\n]", "\n"));

// 匹配一个数字字符。等价于[0-9]
Assert.assertTrue(checkMatches("\\d{1,}", "0123456789"));
// 匹配一个非数字字符。等价于[^0-9]
Assert.assertFalse(checkMatches("\\D{1,}", "0123456789"));

// 匹配包括下划线的任何单词字符。类似但不等价于“[A-Za-z0-9_]”,这里的单词字符指的是Unicode字符集
Assert.assertTrue(checkMatches("\\w{1,}", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_"));
Assert.assertFalse(checkMatches("\\w{1,}", "~!@#$%^&*()+`-=[]{};:<>,./?|\\"));
// 匹配任何非单词字符
Assert.assertFalse(checkMatches("\\W{1,}", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_"));
Assert.assertTrue(checkMatches("\\W{1,}", "~!@#$%^&*()+`-=[]{};:<>,./?|\\"));

// 匹配任何不可见字符,包括空格、制表符、换页符等等。等价于[ \f\n\r\t\v]
Assert.assertTrue(checkMatches("\\s{1,}", " \f\r\n\t"));
// 匹配任何可见字符。等价于[^ \f\n\r\t\v]
Assert.assertFalse(checkMatches("\\S{1,}", " \f\r\n\t"));

// 输出
// ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_ matches: .{1,}
// ~!@#$%^&*()+`-=[]{};:<>,./?|\\ matches: .{1,}
// \n not matches: .
// \n not matches: [^\n]
// 0123456789 matches: \\d{1,}
// 0123456789 not matches: \\D{1,}
// ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_ matches: \\w{1,}
// ~!@#$%^&*()+`-=[]{};:<>,./?|\\ not matches: \\w{1,}
// ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_ not matches: \\W{1,}
// ~!@#$%^&*()+`-=[]{};:<>,./?|\\ matches: \\W{1,}
// \f\r\n\t matches: \\s{1,}
// \f\r\n\t not matches: \\S{1,}

限制字符数量的等价字符

在基本元字符章节中,已经介绍了限制字符数量的基本元字符 - {}

此外,还有 *+? 这个三个为了简化写法而出现的等价字符,我们来认识一下。

字符 描述
* 匹配前面的子表达式零次或多次。等价于{0,}。
+ 匹配前面的子表达式一次或多次。等价于{1,}。
? 匹配前面的子表达式零次或一次。等价于 {0,1}。

案例 限制字符数量的等价字符

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
// *: 匹配前面的子表达式零次或多次。* 等价于{0,}。
checkMatches("ap*", "a");
checkMatches("ap*", "ap");
checkMatches("ap*", "app");
checkMatches("ap*", "apppppppppp");

// +: 匹配前面的子表达式一次或多次。+ 等价于 {1,}。
checkMatches("ap+", "a");
checkMatches("ap+", "ap");
checkMatches("ap+", "app");
checkMatches("ap+", "apppppppppp");

// ?: 匹配前面的子表达式零次或一次。? 等价于 {0,1}。
checkMatches("ap?", "a");
checkMatches("ap?", "ap");
checkMatches("ap?", "app");
checkMatches("ap?", "apppppppppp");

// 输出
// a matches: ap*
// ap matches: ap*
// app matches: ap*
// apppppppppp matches: ap*
// a not matches: ap+
// ap matches: ap+
// app matches: ap+
// apppppppppp matches: ap+
// a matches: ap?
// ap matches: ap?
// app not matches: ap?
// apppppppppp not matches: ap?

元字符优先级顺序

正则表达式从左到右进行计算,并遵循优先级顺序,这与算术表达式非常类似。

下表从最高到最低说明了各种正则表达式运算符的优先级顺序:

运算符 说明
\ 转义符
()(?:)(?=)[] 括号和中括号
*+?{n}{n,}{n,m} 限定符
^$*任何字符任何字符* 定位点和序列
` `

字符具有高于替换运算符的优先级,使得 m|food 匹配 mfood 。若要匹配 moodfood ,请使用括号创建子表达式,从而产生 (m|f)ood

分组构造

在基本元字符章节,提到了 () 字符可以用来对表达式分组。实际上分组还有更多复杂的用法。

所谓分组构造,是用来描述正则表达式的子表达式,用于捕获字符串中的子字符串。

捕获与非捕获

下表为分组构造中的捕获和非捕获分类。

表达式 描述 捕获或非捕获
(exp) 匹配的子表达式 捕获
(?<name>exp) 命名的反向引用 捕获
(?:exp) 非捕获组 非捕获
(?=exp) 零宽度正预测先行断言 非捕获
(?!exp) 零宽度负预测先行断言 非捕获
(?<=exp) 零宽度正回顾后发断言 非捕获
(?<!exp) 零宽度负回顾后发断言 非捕获

注:Java 正则引擎不支持平衡组。

反向引用

带编号的反向引用

带编号的反向引用使用以下语法:\number

其中number 是正则表达式中捕获组的序号位置。 例如,\4 匹配第四个捕获组的内容。 如果正则表达式模式中未定义number,则将发生分析错误

【示例】匹配重复的单词和紧随每个重复的单词的单词(不命名子表达式)

1
2
3
4
5
6
7
8
// (\w+)\s\1\W(\w+) 匹配重复的单词和紧随每个重复的单词的单词
Assert.assertTrue(findAll("(\\w+)\\s\\1\\W(\\w+)",
"He said that that was the the correct answer.") > 0);

// 输出
// regex = (\w+)\s\1\W(\w+), content: He said that that was the the correct answer.
// [1th] start: 8, end: 21, group: that that was
// [2th] start: 22, end: 37, group: the the correct

说明:

  • (\w+):匹配一个或多个单词字符。
  • \s:与空白字符匹配。
  • \1:匹配第一个组,即(\w+)。
  • \W:匹配包括空格和标点符号的一个非单词字符。 这样可以防止正则表达式模式匹配从第一个捕获组的单词开头的单词。

命名的反向引用

命名后向引用通过使用下面的语法进行定义:\k<name >

【示例】匹配重复的单词和紧随每个重复的单词的单词(命名子表达式)

1
2
3
4
5
6
7
8
// (?<duplicateWord>\w+)\s\k<duplicateWord>\W(?<nextWord>\w+) 匹配重复的单词和紧随每个重复的单词的单词
Assert.assertTrue(findAll("(?<duplicateWord>\\w+)\\s\\k<duplicateWord>\\W(?<nextWord>\\w+)",
"He said that that was the the correct answer.") > 0);

// 输出
// regex = (?<duplicateWord>\w+)\s\k<duplicateWord>\W(?<nextWord>\w+), content: He said that that was the the correct answer.
// [1th] start: 8, end: 21, group: that that was
// [2th] start: 22, end: 37, group: the the correct

说明:

  • (?<duplicateWord>\w+):匹配一个或多个单词字符。 命名此捕获组 duplicateWord。
  • \s: 与空白字符匹配。
  • \k<duplicateWord>:匹配名为 duplicateWord 的捕获的组。
  • \W:匹配包括空格和标点符号的一个非单词字符。 这样可以防止正则表达式模式匹配从第一个捕获组的单词开头的单词。
  • (?<nextWord>\w+):匹配一个或多个单词字符。 命名此捕获组 nextWord。

非捕获组

(?:exp) 表示当一个限定符应用到一个组,但组捕获的子字符串并非所需时,通常会使用非捕获组构造。

【示例】匹配以.结束的语句。

1
2
3
4
5
6
// 匹配由句号终止的语句。
Assert.assertTrue(findAll("(?:\\b(?:\\w+)\\W*)+\\.", "This is a short sentence. Never end") > 0);

// 输出
// regex = (?:\b(?:\w+)\W*)+\., content: This is a short sentence. Never end
// [1th] start: 0, end: 25, group: This is a short sentence.

零宽断言

用于查找在某些内容(但并不包括这些内容)之前或之后的东西,也就是说它们像\b,^,$那样用于指定一个位置,这个位置应该满足一定的条件(即断言),因此它们也被称为零宽断言。

表达式 描述
(?=exp) 匹配 exp 前面的位置
(?<=exp) 匹配 exp 后面的位置
(?!exp) 匹配后面跟的不是 exp 的位置
(?<!exp) 匹配前面不是 exp 的位置

匹配 exp 前面的位置

(?=exp) 表示输入字符串必须匹配子表达式中的正则表达式模式,尽管匹配的子字符串未包含在匹配结果中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// \b\w+(?=\sis\b) 表示要捕获is之前的单词
Assert.assertTrue(findAll("\\b\\w+(?=\\sis\\b)", "The dog is a Malamute.") > 0);
Assert.assertFalse(findAll("\\b\\w+(?=\\sis\\b)", "The island has beautiful birds.") > 0);
Assert.assertFalse(findAll("\\b\\w+(?=\\sis\\b)", "The pitch missed home plate.") > 0);
Assert.assertTrue(findAll("\\b\\w+(?=\\sis\\b)", "Sunday is a weekend day.") > 0);

// 输出
// regex = \b\w+(?=\sis\b), content: The dog is a Malamute.
// [1th] start: 4, end: 7, group: dog
// regex = \b\w+(?=\sis\b), content: The island has beautiful birds.
// not found
// regex = \b\w+(?=\sis\b), content: The pitch missed home plate.
// not found
// regex = \b\w+(?=\sis\b), content: Sunday is a weekend day.
// [1th] start: 0, end: 6, group: Sunday

说明:

  • \b:在单词边界处开始匹配。
  • \w+:匹配一个或多个单词字符。
  • (?=\sis\b):确定单词字符是否后接空白字符和字符串“is”,其在单词边界处结束。 如果如此,则匹配成功。

匹配 exp 后面的位置

(?<=exp) 表示子表达式不得在输入字符串当前位置左侧出现,尽管子表达式未包含在匹配结果中。零宽度正回顾后发断言不会回溯。

1
2
3
4
5
6
7
// (?<=\b20)\d{2}\b 表示要捕获以20开头的数字的后面部分
Assert.assertTrue(findAll("(?<=\\b20)\\d{2}\\b", "2010 1999 1861 2140 2009") > 0);

// 输出
// regex = (?<=\b20)\d{2}\b, content: 2010 1999 1861 2140 2009
// [1th] start: 2, end: 4, group: 10
// [2th] start: 22, end: 24, group: 09

说明:

  • \d{2}:匹配两个十进制数字。
  • {?<=\b20):如果两个十进制数字的字边界以小数位数“20”开头,则继续匹配。
  • \b:在单词边界处结束匹配。

匹配后面跟的不是 exp 的位置

(?!exp) 表示输入字符串不得匹配子表达式中的正则表达式模式,尽管匹配的子字符串未包含在匹配结果中。

【示例】捕获未以“un”开头的单词

1
2
3
4
5
6
7
8
9
// \b(?!un)\w+\b 表示要捕获未以“un”开头的单词
Assert.assertTrue(findAll("\\b(?!un)\\w+\\b", "unite one unethical ethics use untie ultimate") > 0);

// 输出
// regex = \b(?!un)\w+\b, content: unite one unethical ethics use untie ultimate
// [1th] start: 6, end: 9, group: one
// [2th] start: 20, end: 26, group: ethics
// [3th] start: 27, end: 30, group: use
// [4th] start: 37, end: 45, group: ultimate

说明:

  • \b:在单词边界处开始匹配。
  • (?!un):确定接下来的两个的字符是否为“un”。 如果没有,则可能匹配。
  • \w+:匹配一个或多个单词字符。
  • \b:在单词边界处结束匹配。

匹配前面不是 exp 的位置

(?<!exp) 表示子表达式不得在输入字符串当前位置的左侧出现。 但是,任何不匹配子表达式 的子字符串不包含在匹配结果中。

【示例】捕获任意工作日

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// (?<!(Saturday|Sunday) )\b\w+ \d{1,2}, \d{4}\b 表示要捕获任意工作日(即周一到周五)
Assert.assertTrue(findAll("(?<!(Saturday|Sunday) )\\b\\w+ \\d{1,2}, \\d{4}\\b", "Monday February 1, 2010") > 0);
Assert.assertTrue(findAll("(?<!(Saturday|Sunday) )\\b\\w+ \\d{1,2}, \\d{4}\\b", "Wednesday February 3, 2010") > 0);
Assert.assertFalse(findAll("(?<!(Saturday|Sunday) )\\b\\w+ \\d{1,2}, \\d{4}\\b", "Saturday February 6, 2010") > 0);
Assert.assertFalse(findAll("(?<!(Saturday|Sunday) )\\b\\w+ \\d{1,2}, \\d{4}\\b", "Sunday February 7, 2010") > 0);
Assert.assertTrue(findAll("(?<!(Saturday|Sunday) )\\b\\w+ \\d{1,2}, \\d{4}\\b", "Monday, February 8, 2010") > 0);

// 输出
// regex = (?<!(Saturday|Sunday) )\b\w+ \d{1,2}, \d{4}\b, content: Monday February 1, 2010
// [1th] start: 7, end: 23, group: February 1, 2010
// regex = (?<!(Saturday|Sunday) )\b\w+ \d{1,2}, \d{4}\b, content: Wednesday February 3, 2010
// [1th] start: 10, end: 26, group: February 3, 2010
// regex = (?<!(Saturday|Sunday) )\b\w+ \d{1,2}, \d{4}\b, content: Saturday February 6, 2010
// not found
// regex = (?<!(Saturday|Sunday) )\b\w+ \d{1,2}, \d{4}\b, content: Sunday February 7, 2010
// not found
// regex = (?<!(Saturday|Sunday) )\b\w+ \d{1,2}, \d{4}\b, content: Monday, February 8, 2010
// [1th] start: 8, end: 24, group: February 8, 2010

贪婪与懒惰

当正则表达式中包含能接受重复的限定符时,通常的行为是(在使整个表达式能得到匹配的前提下)匹配尽可能多的字符。以这个表达式为例:a.*b,它将会匹配最长的以 a 开始,以 b 结束的字符串。如果用它来搜索 aabab 的话,它会匹配整个字符串 aabab。这被称为贪婪匹配。

有时,我们更需要懒惰匹配,也就是匹配尽可能少的字符。前面给出的限定符都可以被转化为懒惰匹配模式,只要在它后面加上一个问号?。这样.*?就意味着匹配任意数量的重复,但是在能使整个匹配成功的前提下使用最少的重复。

表达式 描述
*? 重复任意次,但尽可能少重复
+? 重复 1 次或更多次,但尽可能少重复
?? 重复 0 次或 1 次,但尽可能少重复
{n,m}? 重复 n 到 m 次,但尽可能少重复
{n,}? 重复 n 次以上,但尽可能少重复

【示例】Java 正则中贪婪与懒惰的示例

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
// 贪婪匹配
Assert.assertTrue(findAll("a\\w*b", "abaabaaabaaaab") > 0);

// 懒惰匹配
Assert.assertTrue(findAll("a\\w*?b", "abaabaaabaaaab") > 0);
Assert.assertTrue(findAll("a\\w+?b", "abaabaaabaaaab") > 0);
Assert.assertTrue(findAll("a\\w??b", "abaabaaabaaaab") > 0);
Assert.assertTrue(findAll("a\\w{0,4}?b", "abaabaaabaaaab") > 0);
Assert.assertTrue(findAll("a\\w{3,}?b", "abaabaaabaaaab") > 0);

// 输出
// regex = a\w*b, content: abaabaaabaaaab
// [1th] start: 0, end: 14, group: abaabaaabaaaab
// regex = a\w*?b, content: abaabaaabaaaab
// [1th] start: 0, end: 2, group: ab
// [2th] start: 2, end: 5, group: aab
// [3th] start: 5, end: 9, group: aaab
// [4th] start: 9, end: 14, group: aaaab
// regex = a\w+?b, content: abaabaaabaaaab
// [1th] start: 0, end: 5, group: abaab
// [2th] start: 5, end: 9, group: aaab
// [3th] start: 9, end: 14, group: aaaab
// regex = a\w??b, content: abaabaaabaaaab
// [1th] start: 0, end: 2, group: ab
// [2th] start: 2, end: 5, group: aab
// [3th] start: 6, end: 9, group: aab
// [4th] start: 11, end: 14, group: aab
// regex = a\w{0,4}?b, content: abaabaaabaaaab
// [1th] start: 0, end: 2, group: ab
// [2th] start: 2, end: 5, group: aab
// [3th] start: 5, end: 9, group: aaab
// [4th] start: 9, end: 14, group: aaaab
// regex = a\w{3,}?b, content: abaabaaabaaaab
// [1th] start: 0, end: 5, group: abaab
// [2th] start: 5, end: 14, group: aaabaaaab

说明:

本例中代码展示的是使用不同贪婪或懒惰策略去查找字符串 abaabaaabaaaab 中匹配a 开头,以 b 结尾的所有子字符串。请从输出结果中,细细体味使用不同的贪婪或懒惰策略,对于匹配子字符串有什么影响。

正则附录

匹配正则字符串的方法

由于正则表达式中很多元字符本身就是转义字符,在 Java 字符串的规则中不会被显示出来。

为此,可以使用一个工具类org.apache.commons.lang3.StringEscapeUtils来做特殊处理,使得转义字符可以打印。这个工具类提供的都是静态方法,从方法命名大致也可以猜出用法,这里不多做说明。

如果你了解 maven,可以直接引入依赖

1
2
3
4
5
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>${commons-lang3.version}</version>
</dependency>

【示例】本文为了展示正则匹配规则用到的方法

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
private boolean checkMatches(String regex, String content) {
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
boolean flag = m.matches();
if (m.matches()) {
System.out.println(StringEscapeUtils.escapeJava(content) + "\tmatches: " + StringEscapeUtils.escapeJava(regex));
} else {
System.out.println(StringEscapeUtils.escapeJava(content) + "\tnot matches: " + StringEscapeUtils.escapeJava(regex));
}
return flag;
}

public int findAll(String regex, String content) {
Pattern p = Pattern.compile(regex);
Matcher m = p.matcher(content);
System.out.println("regex = " + regex + ", content: " + content);

int count = 0;
while (m.find()) {
count++;
System.out.println("[" + count + "th] " + "start: " + m.start() + ", end: " + m.end()
+ ", group: " + m.group());
}
if (0 == count) {
System.out.println("not found");
}
return count;
}

速查元字符字典

为了方便快查正则的元字符含义,在本节根据元字符的功能集中罗列正则的各种元字符。

限定符

字符 描述
* 匹配前面的子表达式零次或多次。例如,zo* 能匹配 “z” 以及 “zoo”。* 等价于{0,}。
+ 匹配前面的子表达式一次或多次。例如,’zo+’ 能匹配 “zo” 以及 “zoo”,但不能匹配 “z”。+ 等价于 {1,}。
? 匹配前面的子表达式零次或一次。例如,”do(es)?” 可以匹配 “do” 或 “does” 中的”do” 。? 等价于 {0,1}。
{n} n 是一个非负整数。匹配确定的 n 次。例如,’o{2}’ 不能匹配 “Bob” 中的 ‘o’,但是能匹配 “food” 中的两个 o。
{n,} n 是一个非负整数。至少匹配 n 次。例如,’o{2,}’ 不能匹配 “Bob” 中的 ‘o’,但能匹配 “foooood” 中的所有 o。’o{1,}’ 等价于 ‘o+’。’o{0,}’ 则等价于 ‘o*‘。
{n,m} m 和 n 均为非负整数,其中 n <= m。最少匹配 n 次且最多匹配 m 次。例如,”o{1,3}” 将匹配 “fooooood” 中的前三个 o。’o{0,1}’ 等价于 ‘o?’。请注意在逗号和两个数之间不能有空格。

定位符

字符 描述
^ 匹配输入字符串开始的位置。如果设置了 RegExp 对象的 Multiline 属性,^ 还会与 \n 或 \r 之后的位置匹配。
$ 匹配输入字符串结尾的位置。如果设置了 RegExp 对象的 Multiline 属性,$ 还会与 \n 或 \r 之前的位置匹配。
\b 匹配一个字边界,即字与空格间的位置。
\B 非字边界匹配。

非打印字符

字符 描述
\cx 匹配由 x 指明的控制字符。例如, \cM 匹配一个 Control-M 或回车符。x 的值必须为 A-Z 或 a-z 之一。否则,将 c 视为一个原义的 ‘c’ 字符。
\f 匹配一个换页符。等价于 \x0c 和 \cL。
\n 匹配一个换行符。等价于 \x0a 和 \cJ。
\r 匹配一个回车符。等价于 \x0d 和 \cM。
\s 匹配任何空白字符,包括空格、制表符、换页符等等。等价于 [ \f\n\r\t\v]。
\S 匹配任何非空白字符。等价于 [ \f\n\r\t\v]。
\t 匹配一个制表符。等价于 \x09 和 \cI。
\v 匹配一个垂直制表符。等价于 \x0b 和 \cK。

分组

表达式 描述
(exp) 匹配的子表达式。()中的内容就是子表达式。
(?<name>exp) 命名的子表达式(反向引用)。
(?:exp) 非捕获组,表示当一个限定符应用到一个组,但组捕获的子字符串并非所需时,通常会使用非捕获组构造。
(?=exp) 匹配 exp 前面的位置。
(?<=exp) 匹配 exp 后面的位置。
(?!exp) 匹配后面跟的不是 exp 的位置。
(?<!exp) 匹配前面不是 exp 的位置。

特殊符号

字符 描述
\ 将下一个字符标记为或特殊字符、或原义字符、或向后引用、或八进制转义符。例如, ‘n’ 匹配字符 ‘n’。’\n’ 匹配换行符。序列 ‘\‘ 匹配 “",而 ‘(‘ 则匹配 “(“。
| 指明两项之间的一个选择。
[] 匹配方括号范围内的任意一个字符。形式如:[xyz]、[^xyz]、[a-z]、[^a-z]、[x,y,z]

正则实战

虽然本系列洋洋洒洒的大谈特谈正则表达式。但是我还是要在这里建议,如果一个正则表达式没有经过充分测试,还是要谨慎使用。

正则是把双刃剑,它可以为你节省大量的代码行。但是由于它不易阅读,维护起来可是头疼的哦(你需要一个字符一个字符的去理解)。

最实用的正则

校验中文

校验字符串中只能有中文字符(不包括中文标点符号)。中文字符的 Unicode 编码范围是 \u4e00\u9fa5

如有兴趣,可以参考百度百科-Unicode

1
^[\u4e00-\u9fa5]+$
  • 匹配: 春眠不觉晓
  • 不匹配:春眠不觉晓,

校验身份证号码

身份证为 15 位或 18 位。15 位是第一代身份证。从 1999 年 10 月 1 日起,全国实行公民身份证号码制度,居民身份证编号由原 15 位升至 18 位。

  • 15 位身份证:由 15 位数字组成。排列顺序从左至右依次为:六位数字地区码;六位数字出生日期;三位顺序号,其中 15 位男为单数,女为双数。
  • 18 位身份证:由十七位数字本体码和一位数字校验码组成。排列顺序从左至右依次为:六位数字地区码;八位数字出生日期;三位数字顺序码和一位数字校验码(也可能是 X)。

身份证号含义详情请见:百度百科-居民身份证号码

地区码(6 位)

1
(1[1-5]|2[1-3]|3[1-7]|4[1-3]|5[0-4]|6[1-5])\d{4}

出生日期(8 位)

注:下面的是 18 位身份证的有效出生日期,如果是 15 位身份证,只要将第一个\d{4}改为\d{2}即可。

1
((\d{4}((0[13578]|1[02])(0[1-9]|[12]\d|3[01])|(0[13456789]|1[012])(0[1-9]|[12]\d|30)|02(0[1-9]|1\d|2[0-8])))|([02468][048]|[13579][26])0229)

15 位有效身份证

1
^((1[1-5]|2[1-3]|3[1-7]|4[1-3]|5[0-4]|6[1-5])\d{4})((\d{2}((0[13578]|1[02])(0[1-9]|[12]\d|3[01])|(0[13456789]|1[012])(0[1-9]|[12]\d|30)|02(0[1-9]|1\d|2[0-8])))|([02468][048]|[13579][26])0229)(\d{3})$
  • 匹配:110001700101031

  • 不匹配:110001701501031

18 位有效身份证

1
^((1[1-5]|2[1-3]|3[1-7]|4[1-3]|5[0-4]|6[1-5])\d{4})((\d{4}((0[13578]|1[02])(0[1-9]|[12]\d|3[01])|(0[13456789]|1[012])(0[1-9]|[12]\d|30)|02(0[1-9]|1\d|2[0-8])))|([02468][048]|[13579][26])0229)(\d{3}(\d|X))$
  • 匹配:110001199001010310 | 11000019900101015X

  • 不匹配:990000199001010310 | 110001199013010310

校验有效用户名、密码

描述:长度为 6-18 个字符,允许输入字母、数字、下划线,首字符必须为字母。

1
^[a-zA-Z]\w{5,17}$

校验邮箱

描述:不允许使用 IP 作为域名,如 : hello@154.145.68.12

@符号前的邮箱用户和.符号前的域名(domain)必须满足以下条件:

  • 字符只能是英文字母、数字、下划线_.-
  • 首字符必须为字母或数字;
  • _.- 不能连续出现。

域名的根域只能为字母,且至少为两个字符。

1
^[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$

校验 URL

描述:校验 URL。支持 http、https、ftp、ftps。

1
^(ht|f)(tp|tps)\://[a-zA-Z0-9\-\.]+\.([a-zA-Z]{2,3})?(/\S*)?$

校验时间

描述:校验时间。时、分、秒必须是有效数字,如果数值不是两位数,十位需要补零。

1
^([0-1][0-9]|[2][0-3]):([0-5][0-9])$
  • 匹配:00:00:00 | 23:59:59 | 17:06:30

  • 不匹配:17:6:30 | 24:16:30

校验日期

描述:校验日期。日期满足以下条件:

  • 格式 yyyy-MM-dd 或 yyyy-M-d
  • 连字符可以没有或是“-”、“/”、“.”之一
  • 闰年的二月可以有 29 日;而平年不可以。
  • 一、三、五、七、八、十、十二月为 31 日。四、六、九、十一月为 30 日。
1
^(?:(?!0000)[0-9]{4}([-/.]?)(?:(?:0?[1-9]|1[0-2])\1(?:0?[1-9]|1[0-9]|2[0-8])|(?:0?[13-9]|1[0-2])\1(?:29|30)|(?:0?[13578]|1[02])\1(?:31))|(?:[0-9]{2}(?:0[48]|[2468][048]|[13579][26])|(?:0[48]|[2468][048]|[13579][26])00)([-/.]?)0?2\2(?:29))$
  • 匹配:2016/1/1 | 2016/01/01 | 20160101 | 2016-01-01 | 2016.01.01 | 2000-02-29
  • 不匹配:2001-02-29 | 2016/12/32 | 2016/6/31 | 2016/13/1 | 2016/0/1

校验中国手机号码

描述:中国手机号码正确格式:11 位数字。

移动有 16 个号段:134、135、136、137、138、139、147、150、151、152、157、158、159、182、187、188。其中 147、157、188 是 3G 号段,其他都是 2G 号段。联通有 7 种号段:130、131、132、155、156、185、186。其中 186 是 3G(WCDMA)号段,其余为 2G 号段。电信有 4 个号段:133、153、180、189。其中 189 是 3G 号段(CDMA2000),133 号段主要用作无线网卡号。总结:13 开头手机号 0-9;15 开头手机号 0-3、5-9;18 开头手机号 0、2、5-9。

此外,中国在国际上的区号为 86,所以手机号开头有+86、86 也是合法的。

以上信息来源于 百度百科-手机号

1
^((\+)?86\s*)?((13[0-9])|(15([0-3]|[5-9]))|(18[0,2,5-9]))\d{8}$
  • 匹配:+86 18012345678 | 86 18012345678 | 15812345678

  • 不匹配:15412345678 | 12912345678 | 180123456789

校验中国固话号码

描述:固话号码,必须加区号(以 0 开头)。
3 位有效区号:010、020~029,固话位数为 8 位。
4 位有效区号:03xx 开头到 09xx,固话位数为 7。

如果想了解更详细的信息,请参考 百度百科-电话区号

1
^(010|02[0-9])(\s|-)\d{8}|(0[3-9]\d{2})(\s|-)\d{7}$
  • 匹配:010-12345678 | 010 12345678 | 0512-1234567 | 0512 1234567

  • 不匹配:1234567 | 12345678

校验 IPv4 地址

描述:IP 地址是一个 32 位的二进制数,通常被分割为 4 个“8 位二进制数”(也就是 4 个字节)。IP 地址通常用“点分十进制”表示成(a.b.c.d)的形式,其中,a,b,c,d 都是 0~255 之间的十进制整数。

1
^([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$
  • 匹配:0.0.0.0 | 255.255.255.255 | 127.0.0.1

  • 不匹配:10.10.10 | 10.10.10.256

校验 IPv6 地址

描述:IPv6 的 128 位地址通常写成 8 组,每组为四个十六进制数的形式。

IPv6 地址可以表示为以下形式:

显然,IPv6 地址的表示方式很复杂。你也可以参考:

百度百科-IPv6

Stack overflow 上的 IPv6 正则表达高票答案

1
(([0-9a-fA-F]{1,4}:){7,7}[0-9a-fA-F]{1,4}|([0-9a-fA-F]{1,4}:){1,7}:|([0-9a-fA-F]{1,4}:){1,6}:[0-9a-fA-F]{1,4}|([0-9a-fA-F]{1,4}:){1,5}(:[0-9a-fA-F]{1,4}){1,2}|([0-9a-fA-F]{1,4}:){1,4}(:[0-9a-fA-F]{1,4}){1,3}|([0-9a-fA-F]{1,4}:){1,3}(:[0-9a-fA-F]{1,4}){1,4}|([0-9a-fA-F]{1,4}:){1,2}(:[0-9a-fA-F]{1,4}){1,5}|[0-9a-fA-F]{1,4}:((:[0-9a-fA-F]{1,4}){1,6})|:((:[0-9a-fA-F]{1,4}){1,7}|:)|fe80:(:[0-9a-fA-F]{0,4}){0,4}%[0-9a-zA-Z]{1,}|::(ffff(:0{1,4}){0,1}:){0,1}((25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])\.){3,3}(25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])|([0-9a-fA-F]{1,4}:){1,4}:((25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])\.){3,3}(25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9]))
  • 匹配:1:2:3:4:5:6:7:8 | 1:: | 1::8 | 1::6:7:8 | 1::5:6:7:8 | 1::4:5:6:7:8 | 1::3:4:5:6:7:8 | ::2:3:4:5:6:7:8 | 1:2:3:4:5:6:7:: | 1:2:3:4:5:6::8 | 1:2:3:4:5::8 | 1:2:3:4::8 | 1:2:3::8 | 1:2::8 | 1::8 | ::8 | fe80::7:8%1 | ::255.255.255.255 | 2001:db8:3:4::192.0.2.33 | 64:ff9b::192.0.2.33

  • 不匹配:1.2.3.4.5.6.7.8 | 1::2::3

特定字符

  • 匹配长度为 3 的字符串:^.{3}$
  • 匹配由 26 个英文字母组成的字符串:^[A-Za-z]+$
  • 匹配由 26 个大写英文字母组成的字符串:^[A-Z]+$
  • 匹配由 26 个小写英文字母组成的字符串:^[a-z]+$
  • 匹配由数字和 26 个英文字母组成的字符串:^[A-Za-z0-9]+$
  • 匹配由数字、26 个英文字母或者下划线组成的字符串:^\w+$

特定数字

  • 匹配正整数:^[1-9]\d*$
  • 匹配负整数:^-[1-9]\d*$
  • 匹配整数:^(-?[1-9]\d*)|0$
  • 匹配正浮点数:^[1-9]\d*\.\d+|0\.\d+$
  • 匹配负浮点数:^-([1-9]\d*\.\d*|0\.\d*[1-9]\d*)$
  • 匹配浮点数:^-?([1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0)$

正则表达式的性能

目前实现正则表达式引擎的方式有两种:DFA 自动机(Deterministic Final Automata 确定有限状态自动机)和 NFA 自动机(Non deterministic Finite Automaton 非确定有限状态自动机)。对比来看,构造 DFA 自动机的代价远大于 NFA 自动机,但 DFA 自动机的执行效率高于 NFA 自动机。

假设一个字符串的长度是 n,如果用 DFA 自动机作为正则表达式引擎,则匹配的时间复杂度为 O(n);如果用 NFA 自动机作为正则表达式引擎,由于 NFA 自动机在匹配过程中存在大量的分支和回溯,假设 NFA 的状态数为 s,则该匹配算法的时间复杂度为 O(ns)。

NFA 自动机的优势是支持更多功能。例如,捕获 group、环视、占有优先量词等高级功能。这些功能都是基于子表达式独立进行匹配,因此在编程语言里,使用的正则表达式库都是基于 NFA 实现的。

NFA 自动机的回溯

用 NFA 自动机实现的比较复杂的正则表达式,在匹配过程中经常会引起回溯问题。大量的回溯会长时间地占用 CPU,从而带来系统性能开销。

1
2
text=“abbc”
regex=“ab{1,3}c”

这个例子匹配目的是:匹配以 a 开头,以 c 结尾,中间有 1-3 个 b 字符的字符串。NFA 自动机对其解析的过程是这样的:

  • 读取正则表达式第一个匹配符 a 和字符串第一个字符 a 进行比较,a 对 a,匹配。
  • 然后,读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b 进行比较,匹配。但因为 b{1,3} 表示 1-3 个 b 字符串,NFA 自动机又具有贪婪特性,所以此时不会继续读取正则表达式的下一个匹配符,而是依旧使用 b{1,3} 和字符串的第三个字符 b 进行比较,结果还是匹配。
  • 接着继续使用 b{1,3} 和字符串的第四个字符 c 进行比较,发现不匹配了,此时就会发生回溯,已经读取的字符串第四个字符 c 将被吐出去,指针回到第三个字符 b 的位置。
  • 那么发生回溯以后,匹配过程怎么继续呢?程序会读取正则表达式的下一个匹配符 c,和字符串中的第四个字符 c 进行比较,结果匹配,结束。

如何避免回溯

贪婪模式(Greedy)

顾名思义,就是在数量匹配中,如果单独使用 +、 ? 、* 或{min,max} 等量词,正则表达式会匹配尽可能多的内容。

例如,上边那个例子:

1
2
text=“abbc”
regex=“ab{1,3}c”

就是在贪婪模式下,NFA 自动机读取了最大的匹配范围,即匹配 3 个 b 字符。匹配发生了一次失败,就引起了一次回溯。如果匹配结果是“abbbc”,就会匹配成功。

1
2
text=“abbbc”
regex=“ab{1,3}c”

懒惰模式(Reluctant)

在该模式下,正则表达式会尽可能少地重复匹配字符。如果匹配成功,它会继续匹配剩余的字符串。

例如,在上面例子的字符后面加一个“?”,就可以开启懒惰模式。

1
2
text=“abc”
regex=“ab{1,3}?c”

匹配结果是“abc”,该模式下 NFA 自动机首先选择最小的匹配范围,即匹配 1 个 b 字符,因此就避免了回溯问题。

独占模式(Possessive)

同贪婪模式一样,独占模式一样会最大限度地匹配更多内容;不同的是,在独占模式下,匹配失败就会结束匹配,不会发生回溯问题。

还是上边的例子,在字符后面加一个“+”,就可以开启独占模式。

1
2
text=“abbc”
regex=“ab{1,3}+bc”

结果是不匹配,结束匹配,不会发生回溯问题。

讲到这里,你应该非常清楚了,避免回溯的方法就是:使用懒惰模式和独占模式。

正则表达式的优化

少用贪婪模式,多用独占模式

贪婪模式会引起回溯问题,可以使用独占模式来避免回溯。

减少分支选择

分支选择类型 (X|Y|Z) 的正则表达式会降低性能,我们在开发的时候要尽量减少使用。如果一定要用,我们可以通过以下几种方式来优化:

  • 首先,我们需要考虑选择的顺序,将比较常用的选择项放在前面,使它们可以较快地被匹配;
  • 其次,我们可以尝试提取共用模式,例如,将 (abcd|abef) 替换为 ab(cd|ef),后者匹配速度较快,因为 NFA 自动机会尝试匹配 ab,如果没有找到,就不会再尝试任何选项;
  • 最后,如果是简单的分支选择类型,我们可以用三次 index 代替 (X|Y|Z),如果测试的话,你就会发现三次 index 的效率要比 (X|Y|Z) 高出一些。

减少捕获嵌套

  • 捕获组是指把正则表达式中,子表达式匹配的内容保存到以数字编号或显式命名的数组中,方便后面引用。一般一个 () 就是一个捕获组,捕获组可以进行嵌套。
  • 非捕获组则是指参与匹配却不进行分组编号的捕获组,其表达式一般由 (?:exp) 组成。

在正则表达式中,每个捕获组都有一个编号,编号 0 代表整个匹配到的内容。我们可以看下面的例子:

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
String text = "<input high=\"20\" weight=\"70\">test</input>";
String reg="(<input.*?>)(.*?)(</input>)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while(m.find()) {
System.out.println(m.group(0));// 整个匹配到的内容
System.out.println(m.group(1));//(<input.*?>)
System.out.println(m.group(2));//(.*?)
System.out.println(m.group(3));//(</input>)
}
}

运行结果:

1
2
3
4
<input high=\"20\" weight=\"70\">test</input>
<input high=\"20\" weight=\"70\">
test
</input>

如果你并不需要获取某一个分组内的文本,那么就使用非捕获分组。例如,使用“(?:X)”代替“(X)”,我们再看下面的例子:

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
String text = "<input high=\"20\" weight=\"70\">test</input>";
String reg="(?:<input.*?>)(.*?)(?:</input>)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while(m.find()) {
System.out.println(m.group(0));// 整个匹配到的内容
System.out.println(m.group(1));//(.*?)
}
}

运行结果:

1
2
<input high=\"20\" weight=\"70\">test</input>
test

综上可知:减少不需要获取的分组,可以提高正则表达式的性能。

参考资料

Java 并发之内存模型

Java 内存模型(Java Memory Model),简称 JMM。Java 内存模型的目标是为了解决由可见性和有序性导致的并发安全问题。Java 内存模型通过 屏蔽各种硬件和操作系统的内存访问差异,以实现让 Java 程序在各种平台下都能达到一致的内存访问效果

物理内存模型

物理机遇到的并发问题与虚拟机中的情况有不少相似之处,物理机对并发的处理方案对于虚拟机的实现也有相当大的参考意义。

硬件处理效率存在很大差异

技术在进步,CPU、内存、I/O 设备的性能也在不断提高。但是,始终存在一个核心矛盾:CPU、内存、I/O 设备存在很大的速度差异 - CPU 远快于内存,内存远快于 I/O 设备。木桶短板理论告诉我们:一只木桶能装多少水,取决于最短的那块木板。同理,程序整体性能取决于最慢的操作(即 I/O 操作),所以单方面提高 CPU、内存的性能是无效的。

为了合理利用 CPU 的高性能,平衡这三者的速度差异,计算机体系机构、操作系统、编译程序都做出了贡献,主要体现为:

  • CPU 增加了缓存,以均衡与 CPU 内存的速度差异;
  • 编译程序优化指令执行次序,使得缓存能够得到更加合理地利用。
  • 操作系统增加了进程、线程,以分时复用 CPU,进而均衡 CPU 与 I/O 的速度差异;

缓存导致的可见性问题,编译优化带来的有序性问题,线程切换带来的原子性问题。

缓存一致性

高速缓存解决了 硬件效率问题,但是引入了一个新的问题:缓存一致性(Cache Coherence)

在多处理器系统中,每个处理器都有自己的高速缓存,而它们又共享同一主内存。当多个处理器的运算任务都涉及同一块主内存区域时,将可能导致各自的缓存数据不一致。

为了解决缓存一致性问题,需要各个处理器访问缓存时都遵循一些协议,在读写时要根据协议来进行操作

指令重排序

为了使缓存得到更加合理地使用,计算机在执行程序代码的时候,会对指令进行重排序。

什么是指令重排序? 简单来说就是系统在执行代码的时候并不一定是按照你写的代码的顺序依次执行。

常见的指令重排序有下面 2 种情况:

  • 编译器优化重排:编译器(包括 JVM、JIT 编译器等)在不改变单线程程序语义的前提下,重新安排语句的执行顺序。
  • 指令并行重排:现代处理器采用了指令级并行技术 (Instruction-Level Parallelism,ILP) 来将多条指令重叠执行。如果不存在数据依赖性,处理器可以改变语句对应机器指令的执行顺序。

另外,内存系统也会有“重排序”,但又不是真正意义上的重排序。在 JMM 里表现为主存和本地内存的内容可能不一致,进而导致程序在多线程下执行可能出现问题。

Java 源代码会经历 编译器优化重排 —> 指令并行重排 —> 内存系统重排 的过程,最终才变成操作系统可执行的指令序列。

指令重排序可以保证串行语义一致,但是没有义务保证多线程间的语义也一致 ,所以在多线程下,指令重排序可能会导致一些问题。

对于编译器优化重排和处理器的指令重排序(指令并行重排和内存系统重排都属于是处理器级别的指令重排序),处理该问题的方式不一样。

  • 对于编译器,通过禁止特定类型的编译器重排序的方式来禁止重排序。
  • 对于处理器,通过插入内存屏障(Memory Barrier,或有时叫做内存栅栏,Memory Fence)的方式来禁止特定类型的处理器重排序。

Java 内存模型

内存模型 这个概念。我们可以理解为:在特定的操作协议下,对特定的内存或高速缓存进行读写访问的过程抽象。不同架构的物理计算机可以有不一样的内存模型,JVM 也有自己的内存模型。

JVM 中试图定义一种 Java 内存模型(Java Memory Model, JMM)来屏蔽各种硬件和操作系统的内存访问差异,以实现让 Java 程序 在各种平台下都能达到一致的内存访问效果

Java 并发简介 中已经介绍了,并发安全需要满足可见性、有序性、原子性。其中,导致可见性的原因是缓存,导致有序性的原因是编译优化。那解决可见性、有序性最直接的办法就是禁用缓存和编译优化 。但这么做,性能就堪忧了。

合理的方案应该是按需禁用缓存以及编译优化。那么,如何做到呢?,Java 内存模型规范了 JVM 如何提供按需禁用缓存和编译优化的方法。具体来说,这些方法包括 volatilesynchronizedfinal 三个关键字,以及 Happens-Before 规则

主内存和工作内存

JMM 的主要目标是 定义程序中各个变量的访问规则,即在虚拟机中将变量存储到内存和从内存中取出变量这样的底层细节。此处的变量(Variables)与 Java 编程中所说的变量有所区别,它包括了实例字段、静态字段和构成数值对象的元素,但不包括局部变量与方法参数,因为后者是线程私有的,不会被共享,自然就不会存在竞争问题。为了获得较好的执行效能,JMM 并没有限制执行引擎使用处理器的特定寄存器或缓存来和主存进行交互,也没有限制即使编译器进行调整代码执行顺序这类优化措施。

JMM 规定了所有的变量都存储在主内存(Main Memory)中

每条线程还有自己的工作内存(Working Memory),工作内存中保留了该线程使用到的变量的主内存的副本。工作内存是 JMM 的一个抽象概念,并不真实存在,它涵盖了缓存,写缓冲区,寄存器以及其他的硬件和编译器优化。

线程对变量的所有操作都必须在工作内存中进行,而不能直接读写主内存中的变量。不同的线程间也无法直接访问对方工作内存中的变量,线程间变量值的传递均需要通过主内存来完成

说明:

这里说的主内存、工作内存与 Java 内存区域中的堆、栈、方法区等不是同一个层次的内存划分。

JMM 内存操作的问题

类似于物理内存模型面临的问题,JMM 存在以下两个问题:

  • 工作内存数据一致性 - 各个线程操作数据时会保存使用到的主内存中的共享变量副本,当多个线程的运算任务都涉及同一个共享变量时,将导致各自的的共享变量副本不一致。如果真的发生这种情况,数据同步回主内存以谁的副本数据为准? Java 内存模型主要通过一系列的数据同步协议、规则来保证数据的一致性。
  • 指令重排序优化 - Java 中重排序通常是编译器或运行时环境为了优化程序性能而采取的对指令进行重新排序执行的一种手段。重排序分为两类:编译期重排序和运行期重排序,分别对应编译时和运行时环境。 同样的,指令重排序不是随意重排序,它需要满足以下两个条件:
    • 在单线程环境下不能改变程序运行的结果。即时编译器(和处理器)需要保证程序能够遵守 as-if-serial 属性。通俗地说,就是在单线程情况下,要给程序一个顺序执行的假象。即经过重排序的执行结果要与顺序执行的结果保持一致。
    • 存在数据依赖关系的不允许重排序。
    • 多线程环境下,如果线程处理逻辑之间存在依赖关系,有可能因为指令重排序导致运行结果与预期不同。

内存间交互操作

JMM 定义了 8 个操作来完成主内存和工作内存之间的交互操作。JVM 实现时必须保证下面介绍的每种操作都是 原子的(对于 double 和 long 型的变量来说,load、store、read、和 write 操作在某些平台上允许有例外 )。

  • lock (锁定) - 作用于主内存的变量,它把一个变量标识为一条线程独占的状态。
  • unlock (解锁) - 作用于主内存的变量,它把一个处于锁定状态的变量释放出来,释放后的变量才可以被其他线程锁定。
  • read (读取) - 作用于主内存的变量,它把一个变量的值从主内存传输到线程的工作内存中,以便随后的 load 动作使用。
  • write (写入) - 作用于主内存的变量,它把 store 操作从工作内存中得到的变量的值放入主内存的变量中。
  • load (载入) - 作用于工作内存的变量,它把 read 操作从主内存中得到的变量值放入工作内存的变量副本中。
  • use (使用) - 作用于工作内存的变量,它把工作内存中一个变量的值传递给执行引擎,每当虚拟机遇到一个需要使用到变量的值得字节码指令时就会执行这个操作。
  • assign (赋值) - 作用于工作内存的变量,它把一个从执行引擎接收到的值赋给工作内存的变量,每当虚拟机遇到一个给变量赋值的字节码指令时执行这个操作。
  • store (存储) - 作用于工作内存的变量,它把工作内存中一个变量的值传送到主内存中,以便随后 write 操作使用。

如果要把一个变量从主内存中复制到工作内存,就需要按序执行 readload 操作;如果把变量从工作内存中同步回主内存中,就需要按序执行 storewrite 操作。但 Java 内存模型只要求上述操作必须按顺序执行,而没有保证必须是连续执行。

JMM 还规定了上述 8 种基本操作,需要满足以下规则:

  • read 和 load 必须成对出现store 和 write 必须成对出现。即不允许一个变量从主内存读取了但工作内存不接受,或从工作内存发起回写了但主内存不接受的情况出现。
  • 不允许一个线程丢弃它的最近 assign 的操作,即变量在工作内存中改变了之后必须把变化同步到主内存中。
  • 不允许一个线程无原因的(没有发生过任何 assign 操作)把数据从工作内存同步回主内存中
  • 一个新的变量只能在主内存中诞生,不允许在工作内存中直接使用一个未被初始化(load 或 assign )的变量。换句话说,就是对一个变量实施 use 和 store 操作之前,必须先执行过了 load 或 assign 操作。
  • 一个变量在同一个时刻只允许一条线程对其进行 lock 操作,但 lock 操作可以被同一条线程重复执行多次,多次执行 lock 后,只有执行相同次数的 unlock 操作,变量才会被解锁。所以 lock 和 unlock 必须成对出现
  • 如果对一个变量执行 lock 操作,将会清空工作内存中此变量的值,在执行引擎使用这个变量前,需要重新执行 load 或 assign 操作初始化变量的值。
  • 如果一个变量事先没有被 lock 操作锁定,则不允许对它执行 unlock 操作,也不允许去 unlock 一个被其他线程锁定的变量。
  • 对一个变量执行 unlock 操作之前,必须先把此变量同步到主内存中(执行 store 和 write 操作)

并发安全特性

并发最重要的问题是并发安全问题。所谓并发安全,是指保证程序的正确性,使得并发处理结果符合预期。

并发安全需要保证几个基本特性:

  • 可见性 - 是一个线程修改了某个共享变量,其状态能够立即被其他线程知晓,通常被解释为将线程本地状态反映到主内存上,volatile 就是负责保证可见性的。
  • 有序性 - 是保证线程内串行语义,避免指令重排等。
  • 原子性 - 简单说就是相关操作不会中途被其他线程干扰,一般通过互斥机制(加锁:sychronizedLock)实现。

而这三大特性,归根结底,是为了实现多线程的 数据一致性,使得程序在多线程并发,指令重排序优化的环境中能如预期运行。上文介绍了 Java 内存交互的 8 种基本操作,它们都保证可见性、有序性、原子性。

原子性

原子性即一个操作或者多个操作,要么全部执行(执行的过程不会被任何因素打断),要么就都不执行。即使在多个线程一起执行的时候,一个操作一旦开始,就不会被其他线程所干扰。

在 Java 中,为了保证原子性,提供了两个高级的字节码指令 monitorentermonitorexit。这两个字节码,在 Java 中对应的关键字就是 synchronized

因此,在 Java 中可以使用 synchronized 来保证方法和代码块内的操作是原子性的。

可见性

可见性是指当多个线程访问同一个变量时,一个线程修改了这个变量的值,其他线程能够立即看得到修改的值

JMM 是通过 “变量修改后将新值同步回主内存变量读取前从主内存刷新变量值” 这种依赖主内存作为传递媒介的方式来实现的。

Java 实现多线程可见性的方式有:

  • volatile
  • synchronized
  • final

有序性

有序性规则表现在以下两种场景:线程内和线程间

  • 线程内 - 从某个线程的角度看方法的执行,指令会按照一种叫“串行”(as-if-serial)的方式执行,此种方式已经应用于顺序编程语言。
  • 线程间 - 这个线程“观察”到其他线程并发地执行非同步的代码时,由于指令重排序优化,任何代码都有可能交叉执行。唯一起作用的约束是:对于同步方法,同步块(synchronized 关键字修饰)以及 volatile 字段的操作仍维持相对有序。

在 Java 中,可以使用 synchronizedvolatile 来保证多线程之间操作的有序性。实现方式有所区别:

  • volatile 关键字会禁止指令重排序。
  • synchronized 关键字通过互斥保证同一时刻只允许一条线程操作。

Happens-Before

JMM 为程序中所有的操作定义了一个偏序关系,称之为 先行发生原则(Happens-Before)Happens-Before 是指 前面一个操作的结果对后续操作是可见的

1978 年,Lamport 在论文 Time, Clocks, and the Ordering of Events in a Distributed System译文解读 )中第一次提出了 Happens-Before,阐述了偏序关系(partial ordering)、逻辑时钟(Logical Clocks)概念,提出解决分布式系统中区分事件发生的时序问题的方法。Happens-Before 的语义是一种因果关系:如果 A 事件是导致 B 事件的起因,那么 A 事件一定是先于(Happens-Before)B 事件发生的。

Happens-Before 非常重要,它是判断数据是否存在竞争、线程是否安全的主要依据,依靠这个原则,我们可以通过几条规则一揽子地解决并发环境下两个操作间是否可能存在冲突的所有问题。

  • 程序顺序规则 - 在一个线程中,按照程序顺序,前面的操作 Happens-Before 于后续的任意操作。
  • 锁定规则 - 一个 unLock 操作 Happens-Before 于后面对同一个锁的 lock 操作。
  • volatile 变量规则 - 对一个 volatile 变量的写操作 Happens-Before 于后面对这个变量的读操作。
  • 线程启动规则 - Thread 对象的 start() 方法 Happens-Before 于此线程的每个一个动作。
  • 线程终止规则 - 线程中所有的操作都 Happens-Before 于线程的终止检测,我们可以通过 Thread.join() 方法是否结束、Thread.isAlive() 的返回值手段检测到线程已经终止执行。
  • 线程中断规则 - 对线程 interrupt() 方法的调用 Happens-Before 于被中断线程的代码检测到中断事件的发生,可以通过 Thread.interrupted() 方法检测到是否有中断发生。
  • 对象终结规则 - 一个对象的初始化完成 Happens-Before 于它的 finalize() 方法的开始。
  • 传递性 - 如果 A Happens-Before B,且 B Happens-Before C,那么 A Happens-Before C。

内存屏障

Java 中如何保证底层操作的有序性和可见性?可以通过内存屏障(memory barrier)。

内存屏障是被插入两个 CPU 指令之间的一种指令,用来禁止处理器指令发生重排序(像屏障一样),从而保障有序性的。另外,为了达到屏障的效果,它也会使处理器写入、读取值之前,将主内存的值写入高速缓存,清空无效队列,从而保障可见性

举个例子:

1
2
3
4
5
6
7
8
Store1;
Store2;
Load1;
StoreLoad; //内存屏障
Store3;
Load2;
Load3;
复制代码

对于上面的一组 CPU 指令(Store 表示写入指令,Load 表示读取指令),StoreLoad 屏障之前的 Store 指令无法与 StoreLoad 屏障之后的 Load 指令进行交换位置,即重排序。但是 StoreLoad 屏障之前和之后的指令是可以互换位置的,即 Store1 可以和 Store2 互换,Load2 可以和 Load3 互换。

常见有 4 种屏障

  • LoadLoad 屏障 - 对于这样的语句 Load1; LoadLoad; Load2,在 Load2 及后续读取操作要读取的数据被访问前,保证 Load1 要读取的数据被读取完毕。
  • StoreStore 屏障 - 对于这样的语句 Store1; StoreStore; Store2,在 Store2 及后续写入操作执行前,保证 Store1 的写入操作对其它处理器可见。
  • LoadStore 屏障 - 对于这样的语句 Load1; LoadStore; Store2,在 Store2 及后续写入操作被执行前,保证 Load1 要读取的数据被读取完毕。
  • StoreLoad 屏障 - 对于这样的语句 Store1; StoreLoad; Load2,在 Load2 及后续所有读取操作执行前,保证 Store1 的写入对所有处理器可见。它的开销是四种屏障中最大的(冲刷写缓冲器,清空无效化队列)。在大多数处理器的实现中,这个屏障是个万能屏障,兼具其它三种内存屏障的功能。

Java 中对内存屏障的使用在一般的代码中不太容易见到,常见的有 volatilesynchronized 关键字修饰的代码块(后面再展开介绍),还可以通过 Unsafe 这个类来使用内存屏障。

img

Synchronized 内存语义

synchronized 是 Java 中的关键字,是 利用锁的机制来实现互斥同步的

synchronized 可以保证在同一个时刻,只有一个线程可以执行某个方法或者某个代码块

  • 线程释放锁时内存语义:JMM 会把该线程对应的工作内存中的共享变量刷新到主内存中
  • 线程获取锁时内存语义:JMM 会把该线程对应的工作内存置为无效

如果不需要 LockReadWriteLock 所提供的高级同步特性,应该优先考虑使用 synchronized ,理由如下:

  • Java 1.6 以后,synchronized 做了大量的优化,其性能已经与 LockReadWriteLock 基本上持平。从趋势来看,Java 未来仍将继续优化 synchronized ,而不是 ReentrantLock
  • ReentrantLock 是 Oracle JDK 的 API,在其他版本的 JDK 中不一定支持;而 synchronized 是 JVM 的内置特性,所有 JDK 版本都提供支持。

synchronized 的应用

synchronized 有 3 种应用方式:

  • 同步实例方法 - 对于普通同步方法,锁是当前实例对象
  • 同步静态方法 - 对于静态同步方法,锁是当前类的 Class 对象
  • 同步代码块 - 对于同步方法块,锁是 synchonized 括号里配置的对象

【示例】synchronized 的使用语法

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
class Test {

// 修饰成员方法
synchronized void sync1() {
// 临界区
}

// 修饰静态方法
synchronized static void sync2() {
// 临界区
}

// 对象锁
Object obj = new Object();
// 修饰代码块,使用对象锁
void sync3() {
synchronized (obj) {
// 临界区
}
}

// 修饰代码块,使用类锁(Class)
void sync4() {
synchronized (Test.class) {
//临界区
}
}

}

用 synchronized 实现线程安全的计数器

我们先来看一个简单的示例,这段代码维护了一个计数器变量 count,并通过 get() 和 add() 分别实现了读写方法。

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
@NotThreadSafe
public class NotThreadSafeCounter {

private static int count = 0;

public int get() {
return count;
}

public void add() {
count++;
}

public static void main(String[] args) throws InterruptedException {
final int MAX = 100000;
NotThreadSafeCounter instance = new NotThreadSafeCounter();
Thread t1 = new Thread(() -> {
for (int i = 0; i < MAX; i++) {
instance.add();
}
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < MAX; i++) {
instance.add();
}
});
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println("count = " + instance.get());
}

}
// 输出:
// count = 117626
//

启动两个线程并行执行,期望最终值为 200000,但实际值为小于 200000 的随机数字。显然,上面的示例是线程不安全的。究其原因,在于 count++ 不是原子操作,不满足并发安全的原子性要求。

要解决此问题,可以用 synchronized 修饰方法, synchronized 可以保证同一时刻只有一个线程执行临界区的代码。

我们针对上面的示例来进行改造,将 add() 方法用 synchronized 修饰,如下所示。这下是不是就可以高枕无忧了呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
@NotThreadSafe
public class NotThreadSafeCounter2 {

private static int count = 0;

public int get() {
return count;
}

public synchronized void add() {
count++;
}
}

首先,add() 方法本身是线程安全的。但是,这个示例忽略了 get() 方法。因为 get() 方法未加锁,一个线程调用 add() 方法后,无法保证另一个线程调用 get() 时能立刻获取到更新后的结果,不满足并发安全的可见性要求。

如何彻底解决 get() 并发不安全的问题呢?很简单,就是 get() 方法也用 synchronized 修饰一下。最终的线程安全示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
@ThreadSafe
public class ThreadSafeCounter {

private int count = 0;

public synchronized long get() {
return count;
}

public synchronized void add() {
count++;
}
}

静态 synchronized 方法和非静态 synchronized 是否互斥

静态方法的同步是指同步在该方法所在的类对象上。因为在 JVM 中一个类只能对应一个类对象,所以同时只允许一个线程执行同一个类中的静态同步方法。

静态 synchronized 方法和非静态 synchronized 方法之间的调用互斥么?

答案是:不互斥,但可能存在并发问题!如果一个线程 A 调用一个实例对象的非静态 synchronized 方法;而线程 B 需要调用这个实例对象所属类的静态 synchronized 方法,是允许的,不会发生互斥现象,因为访问静态 synchronized 方法占用的锁是当前类的锁,而访问非静态 synchronized 方法占用的锁是当前实例对象锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
@ThreadSafe
public class ThreadSafeCounter2 {

private static int count = 0;

public synchronized long get() {
return count;
}

public synchronized static void add() {
count++;
}
}

上面这段代码实际上是用两个锁保护同一个资源。这个受保护的资源就是静态变量 count,两个锁分别是 this 和 ThreadSafeCounter2.class。我们可以用下面这幅图来形象描述这个关系。由于临界区 get() 和 add() 是用两个锁保护的,因此这两个临界区没有互斥关系,临界区 add() 对 value 的修改对临界区 get() 也没有可见性保证,这就导致并发问题了。

用 synchronized 保护多个资源

【示例】错误示例

1
2
3
4
5
6
7
8
9
10
11
class Account {
private int balance;
// 转账
synchronized void transfer(
Account target, int amt){
if (this.balance > amt) {
this.balance -= amt;
target.balance += amt;
}
}
}

在这段代码中,临界区内有两个资源,分别是转出账户的余额 this.balance 和转入账户的余额 target.balance,并且用的是一把锁 this,符合我们前面提到的,多个资源可以用一把锁来保护,这看上去完全正确呀。真的是这样吗?可惜,这个方案仅仅是看似正确,为什么呢?

问题就出在 this 这把锁上,this 这把锁可以保护自己的余额 this.balance,却保护不了别人的余额 target.balance,就像你不能用自家的锁来保护别人家的资产,也不能用自己的票来保护别人的座位一样。

应该保证使用的锁能覆盖所有受保护资源

【示例】正确姿势

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Account {
private Object lock;
private int balance;
private Account();
// 创建 Account 时传入同一个 lock 对象
public Account(Object lock) {
this.lock = lock;
}
// 转账
void transfer(Account target, int amt){
// 此处检查所有对象共享的锁
synchronized(lock) {
if (this.balance > amt) {
this.balance -= amt;
target.balance += amt;
}
}
}
}

这个办法确实能解决问题,但是有点小瑕疵,它要求在创建 Account 对象的时候必须传入同一个对象,如果创建 Account 对象时,传入的 lock 不是同一个对象,那可就惨了,会出现锁自家门来保护他家资产的荒唐事。在真实的项目场景中,创建 Account 对象的代码很可能分散在多个工程中,传入共享的 lock 真的很难。

上面的方案缺乏实践的可行性,我们需要更好的方案。还真有,就是用 Account.class 作为共享的锁。Account.class 是所有 Account 对象共享的,而且这个对象是 Java 虚拟机在加载 Account 类的时候创建的,所以我们不用担心它的唯一性。使用 Account.class 作为共享的锁,我们就无需在创建 Account 对象时传入了,代码更简单。

【示例】正确姿势

1
2
3
4
5
6
7
8
9
10
11
12
class Account {
private int balance;
// 转账
void transfer(Account target, int amt){
synchronized(Account.class) {
if (this.balance > amt) {
this.balance -= amt;
target.balance += amt;
}
}
}
}

synchronized 的原理

synchronized 代码块是由一对 monitorentermonitorexit 指令实现的,Monitor 对象是同步的基本实现单元。在 Java 6 之前,Monitor 的实现完全是依靠操作系统内部的互斥锁,因为需要进行用户态到内核态的切换,所以同步操作是一个无差别的重量级操作。

如果 synchronized 明确制定了对象参数,那就是这个对象的引用;如果没有明确指定,那就根据 synchronized 修饰的是实例方法还是静态方法,去对对应的对象实例或 Class 对象来作为锁对象。

synchronized 同步块对同一线程来说是可重入的,不会出现锁死问题。

synchronized 同步块是互斥的,即已进入的线程执行完成前,会阻塞其他试图进入的线程。

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
public void foo(Object lock) {
synchronized (lock) {
lock.hashCode();
}
}
// 上面的 Java 代码将编译为下面的字节码
public void foo(java.lang.Object);
Code:
0: aload_1
1: dup
2: astore_2
3: monitorenter
4: aload_1
5: invokevirtual java/lang/Object.hashCode:()I
8: pop
9: aload_2
10: monitorexit
11: goto 19
14: astore_3
15: aload_2
16: monitorexit
17: aload_3
18: athrow
19: return
Exception table:
from to target type
4 11 14 any
14 17 14 any

synchronized 在修饰同步代码块时,是由 monitorentermonitorexit 指令来实现同步的。进入 monitorenter 指令后,线程将持有 Monitor 对象,退出 monitorenter 指令后,线程将释放该 Monitor 对象。

synchronized 修饰同步方法时,会设置一个 ACC_SYNCHRONIZED 标志。当方法调用时,调用指令将会检查该方法是否被设置 ACC_SYNCHRONIZED 访问标志。如果设置了该标志,执行线程将先持有 Monitor 对象,然后再执行方法。在该方法运行期间,其它线程将无法获取到该 Mointor 对象,当方法执行完成后,再释放该 Monitor 对象。

每个对象实例都会有一个 MonitorMonitor 可以和对象一起创建、销毁。Monitor 是由 ObjectMonitor 实现,而 ObjectMonitor 是由 C++ 的 ObjectMonitor.hpp 文件实现。

当多个线程同时访问一段同步代码时,多个线程会先被存放在 EntryList 集合中,处于 block 状态的线程,都会被加入到该列表。接下来当线程获取到对象的 Monitor 时,Monitor 是依靠底层操作系统的 Mutex Lock 来实现互斥的,线程申请 Mutex 成功,则持有该 Mutex,其它线程将无法获取到该 Mutex。

如果线程调用 wait() 方法,就会释放当前持有的 Mutex,并且该线程会进入 WaitSet 集合中,等待下一次被唤醒。如果当前线程顺利执行完方法,也将释放 Mutex。

synchronized 的优化

Java 1.6 以后,synchronized 做了大量的优化,其性能已经与 LockReadWriteLock 基本上持平

在 JDK1.6 JVM 中,对象实例在堆内存中被分为了三个部分:对象头、实例数据和对齐填充。其中 Java 对象头由 Mark Word、指向类的指针以及数组长度三部分组成。

Mark Word 记录了对象和锁有关的信息。Mark Word 在 64 位 JVM 中的长度是 64bit,我们可以一起看下 64 位 JVM 的存储结构是怎么样的。如下图所示:

img

锁升级功能主要依赖于 Mark Word 中的锁标志位和释放偏向锁标志位,synchronized 同步锁就是从偏向锁开始的,随着竞争越来越激烈,偏向锁升级到轻量级锁,最终升级到重量级锁。

Java 1.6 引入了偏向锁和轻量级锁,从而让 synchronized 拥有了四个状态:

  • 无锁状态(unlocked)
  • 偏向锁状态(biasble)
  • 轻量级锁状态(lightweight locked)
  • 重量级锁状态(inflated)

当 JVM 检测到不同的竞争状况时,会自动切换到适合的锁实现。

当没有竞争出现时,默认会使用偏向锁。JVM 会利用 CAS 操作(compare and swap),在对象头上的 Mark Word 部分设置线程 ID,以表示这个对象偏向于当前线程,所以并不涉及真正的互斥锁。这样做的假设是基于在很多应用场景中,大部分对象生命周期中最多会被一个线程锁定,使用偏斜锁可以降低无竞争开销。

如果有另外的线程试图锁定某个已经被偏斜过的对象,JVM 就需要撤销(revoke)偏向锁,并切换到轻量级锁实现。轻量级锁依赖 CAS 操作 Mark Word 来试图获取锁,如果重试成功,就使用普通的轻量级锁;否则,进一步升级为重量级锁。

偏向锁

偏向锁的思想是偏向于第一个获取锁对象的线程,这个线程在之后获取该锁就不再需要进行同步操作,甚至连 CAS 操作也不再需要

img

轻量级锁

轻量级锁是相对于传统的重量级锁而言,它 使用 CAS 操作来避免重量级锁使用互斥量的开销。对于绝大部分的锁,在整个同步周期内都是不存在竞争的,因此也就不需要都使用互斥量进行同步,可以先采用 CAS 操作进行同步,如果 CAS 失败了再改用互斥量进行同步。

当尝试获取一个锁对象时,如果锁对象标记为 0|01,说明锁对象的锁未锁定(unlocked)状态。此时虚拟机在当前线程的虚拟机栈中创建 Lock Record,然后使用 CAS 操作将对象的 Mark Word 更新为 Lock Record 指针。如果 CAS 操作成功了,那么线程就获取了该对象上的锁,并且对象的 Mark Word 的锁标记变为 00,表示该对象处于轻量级锁状态。

img

锁消除 / 锁粗化

除了锁升级优化,Java 还使用了编译器对锁进行优化。

锁消除

锁消除是指对于被检测出不可能存在竞争的共享数据的锁进行消除

JIT 编译器在动态编译同步块的时候,借助了一种被称为逃逸分析的技术,来判断同步块使用的锁对象是否只能够被一个线程访问,而没有被发布到其它线程。

确认是的话,那么 JIT 编译器在编译这个同步块的时候不会生成 synchronized 所表示的锁的申请与释放的机器码,即消除了锁的使用。在 Java7 之后的版本就不需要手动配置了,该操作可以自动实现。

对于一些看起来没有加锁的代码,其实隐式的加了很多锁。例如下面的字符串拼接代码就隐式加了锁:

1
2
3
public static String concatString(String s1, String s2, String s3) {
return s1 + s2 + s3;
}

String 是一个不可变的类,编译器会对 String 的拼接自动优化。在 Java 1.5 之前,会转化为 StringBuffer 对象的连续 append() 操作:

1
2
3
4
5
6
7
public static String concatString(String s1, String s2, String s3) {
StringBuffer sb = new StringBuffer();
sb.append(s1);
sb.append(s2);
sb.append(s3);
return sb.toString();
}

每个 append() 方法中都有一个同步块。虚拟机观察变量 sb,很快就会发现它的动态作用域被限制在 concatString() 方法内部。也就是说,sb 的所有引用永远不会逃逸到 concatString() 方法之外,其他线程无法访问到它,因此可以进行消除。

锁粗化

锁粗化同理,就是在 JIT 编译器动态编译时,如果发现几个相邻的同步块使用的是同一个锁实例,那么 JIT 编译器将会把这几个同步块合并为一个大的同步块,从而避免一个线程“反复申请、释放同一个锁“所带来的性能开销。

如果一系列的连续操作都对同一个对象反复加锁和解锁,频繁的加锁操作就会导致性能损耗。

上一节的示例代码中连续的 append() 方法就属于这类情况。如果虚拟机探测到由这样的一串零碎的操作都对同一个对象加锁,将会把加锁的范围扩展(粗化)到整个操作序列的外部。对于上一节的示例代码就是扩展到第一个 append() 操作之前直至最后一个 append() 操作之后,这样只需要加锁一次就可以了。

自旋锁

互斥同步进入阻塞状态的开销都很大,应该尽量避免。在许多应用中,共享数据的锁定状态只会持续很短的一段时间。自旋锁的思想是让一个线程在请求一个共享数据的锁时执行忙循环(自旋)一段时间,如果在这段时间内能获得锁,就可以避免进入阻塞状态。

自旋锁虽然能避免进入阻塞状态从而减少开销,但是它需要进行忙循环操作占用 CPU 时间,它只适用于共享数据的锁定状态很短的场景。

在 Java 1.6 中引入了自适应的自旋锁。自适应意味着自旋的次数不再固定了,而是由前一次在同一个锁上的自旋次数及锁的拥有者的状态来决定。

synchronized 的误区

示例摘自:极客时间教程 - Java 业务开发常见错误 100 例

synchronized 使用范围不当导致的错误

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
public class Interesting {

volatile int a = 1;
volatile int b = 1;

public static void main(String[] args) {
Interesting interesting = new Interesting();
new Thread(() -> interesting.add()).start();
new Thread(() -> interesting.compare()).start();
}

public synchronized void add() {
log.info("add start");
for (int i = 0; i < 10000; i++) {
a++;
b++;
}
log.info("add done");
}

public void compare() {
log.info("compare start");
for (int i = 0; i < 10000; i++) {
//a 始终等于 b 吗?
if (a < b) {
log.info("a:{},b:{},{}", a, b, a > b);
//最后的 a>b 应该始终是 false 吗?
}
}
log.info("compare done");
}

}

【输出】

1
2
3
4
16:05:25.541 [Thread-0] INFO io.github.dunwu.javacore.concurrent.sync.synchronized 使用范围不当 - add start
16:05:25.544 [Thread-0] INFO io.github.dunwu.javacore.concurrent.sync.synchronized 使用范围不当 - add done
16:05:25.544 [Thread-1] INFO io.github.dunwu.javacore.concurrent.sync.synchronized 使用范围不当 - compare start
16:05:25.544 [Thread-1] INFO io.github.dunwu.javacore.concurrent.sync.synchronized 使用范围不当 - compare done

之所以出现这种错乱,是因为两个线程是交错执行 add 和 compare 方法中的业务逻辑,而且这些业务逻辑不是原子性的:a++ 和 b++ 操作中可以穿插在 compare 方法的比较代码中;更需要注意的是,a<b 这种比较操作在字节码层面是加载 a、加载 b 和比较三步,代码虽然是一行但也不是原子性的。

所以,正确的做法应该是,为 add 和 compare 都加上方法锁,确保 add 方法执行时,compare 无法读取 a 和 b:

1
2
public synchronized void add()
public synchronized void compare()

所以,使用锁解决问题之前一定要理清楚,我们要保护的是什么逻辑,多线程执行的情况又是怎样的。

synchronized 保护对象不对导致的错误

加锁前要清楚锁和被保护的对象是不是一个层面的。

静态字段属于类,类级别的锁才能保护;而非静态字段属于类实例,实例级别的锁就可以保护。

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
39
40
41
42
43
44
public class synchronized 错误使用示例 2 {

public static void main(String[] args) {
synchronized 错误使用示例 2 demo = new synchronized 错误使用示例 2();
System.out.println(demo.wrong(1000000));
System.out.println(demo.right(1000000));
}

public int wrong(int count) {
Data.reset();
IntStream.rangeClosed(1, count).parallel().forEach(i -> new Data().wrong());
return Data.getCounter();
}

public int right(int count) {
Data.reset();
IntStream.rangeClosed(1, count).parallel().forEach(i -> new Data().right());
return Data.getCounter();
}

private static class Data {

@Getter
private static int counter = 0;
private static Object locker = new Object();

public static int reset() {
counter = 0;
return counter;
}

public synchronized void wrong() {
counter++;
}

public void right() {
synchronized (locker) {
counter++;
}
}

}

}

wrong 方法中试图对一个静态对象加对象级别的 synchronized 锁,并不能保证线程安全。

锁粒度导致的问题

要尽可能的缩小加锁的范围,这可以提高并发吞吐。

如果精细化考虑了锁应用范围后,性能还无法满足需求的话,我们就要考虑另一个维度的粒度问题了,即:区分读写场景以及资源的访问冲突,考虑使用悲观方式的锁还是乐观方式的锁。

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
39
40
41
42
43
44
45
46
public class synchronized 锁粒度不当 {

public static void main(String[] args) {
Demo demo = new Demo();
demo.wrong();
demo.right();
}

private static class Demo {

private List<Integer> data = new ArrayList<>();

private void slow() {
try {
TimeUnit.MILLISECONDS.sleep(10);
} catch (InterruptedException e) {
}
}

public int wrong() {
long begin = System.currentTimeMillis();
IntStream.rangeClosed(1, 1000).parallel().forEach(i -> {
synchronized (this) {
slow();
data.add(i);
}
});
log.info("took:{}", System.currentTimeMillis() - begin);
return data.size();
}

public int right() {
long begin = System.currentTimeMillis();
IntStream.rangeClosed(1, 1000).parallel().forEach(i -> {
slow();
synchronized (data) {
data.add(i);
}
});
log.info("took:{}", System.currentTimeMillis() - begin);
return data.size();
}

}

}

volatile 内存语义

volatile 是 JVM 提供的 最轻量级的同步机制

volatile 修饰的变量,具备以下特性:

  • 线程可见性
  • 禁止指令重排序
  • 不保证原子性

线程安全需要具备:可见性、有序性、原子性。然而,volatile 不保证原子性,因此它不能彻底地保证线程安全。这也正如其命名,volatile 的中文意思是不稳定的,易变的。

保证线程可见性

这里的可见性是指当一条线程修改了 volatile 变量的值,新值对于其他线程来说是可以立即得知的。而普通变量不能做到这一点,普通变量的值在线程间传递均需要通过主内存来完成。

线程写 volatile 变量的过程:

  1. 改变线程工作内存中 volatile 变量副本的值
  2. 将改变后的副本的值从工作内存刷新到主内存

线程读 volatile 变量的过程:

  1. 从主内存中读取 volatile 变量的最新值到线程的工作内存中
  2. 从工作内存中读取 volatile 变量的副本

注意:保证可见性不等同于 volatile 变量保证并发操作的安全性

在不符合以下两点的场景中,仍然要通过枷锁来保证原子性:

  • 运算结果并不依赖变量的当前值,或者能够确保只有单一的线程修改变量的值。
  • 变量不需要与其他状态变量共同参与不变约束。

但是如果多个线程同时把更新后的变量值同时刷新回主内存,可能导致得到的值不是预期结果:

举个例子: 定义 volatile int count = 0,2 个线程同时执行 count++ 操作,每个线程都执行 500 次,最终结果小于 1000,原因是每个线程执行 count++ 需要以下 3 个步骤:

  1. 线程从主内存读取最新的 count 的值
  2. 执行引擎把 count 值加 1,并赋值给线程工作内存
  3. 线程工作内存把 count 值保存到主内存 有可能某一时刻 2 个线程在步骤 1 读取到的值都是 100,执行完步骤 2 得到的值都是 101,最后刷新了 2 次 101 保存到主内存。

禁止指令重排序

观察加入 volatile 关键字和没有加入 volatile 关键字时所生成的汇编代码发现,加入 volatile 关键字时,会多出一个 lock 前缀指令

lock 前缀指令实际上相当于一个内存屏障(也成内存栅栏),内存屏障会提供 3 个功能:

  • 它确保指令重排序时不会把其后面的指令排到内存屏障之前的位置,也不会把前面的指令排到内存屏障的后面;即在执行到内存屏障这句指令时,在它前面的操作已经全部完成;
  • 它会强制将对缓存的修改操作立即写入主存;
  • 如果是写操作,它会导致其他 CPU 中对应的缓存行无效。

在 Java 中,Unsafe 类提供了三个开箱即用的内存屏障相关的方法,屏蔽了操作系统底层的差异:

1
2
3
public native void loadFence();
public native void storeFence();
public native void fullFence();

理论上来说,你通过这个三个方法也可以实现和 volatile 禁止重排序一样的效果,只是会麻烦一些。

下面我以一个常见的面试题为例讲解一下 volatile 关键字禁止指令重排序的效果。

【示例】双重校验锁实现单例模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Singleton {

private volatile static Singleton instance;

private Singleton() { }

public static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) {
instance = new Singleton();
}
}
}
return instance;
}

}

instance 采用 volatile 关键字修饰也是很有必要的, instance = new Singleton(); 这段代码其实是分为三步执行:

  1. instance 分配内存空间
  2. 初始化 instance
  3. instance 指向分配的内存地址

但是由于 JVM 具有指令重排的特性,执行顺序有可能变成 1->3->2。指令重排在单线程环境下不会出现问题,但是在多线程环境下会导致一个线程获得还没有初始化的实例。例如,线程 T1 执行了 1 和 3,此时 T2 调用 getInstance() 后发现 instance 不为空,因此返回 instance,但此时 instance 还未被初始化。

volatile 不保证原子性

线程安全需要具备:可见性、有序性、原子性。然而,**volatile 不保证原子性,所以决定了它不能彻底地保证线程安全**。

我们通过下面的代码即可证明:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class VolatileAtomicityDemo {
public volatile static int inc = 0;

public void increase() {
inc++;
}

public static void main(String[] args) throws InterruptedException {
ExecutorService threadPool = Executors.newFixedThreadPool(5);
VolatileAtomicityDemo volatileAtomicityDemo = new VolatileAtomicityDemo();
for (int i = 0; i < 5; i++) {
threadPool.execute(() -> {
for (int j = 0; j < 500; j++) {
volatileAtomicityDemo.increase();
}
});
}
// 等待 1.5 秒,保证上面程序执行完成
Thread.sleep(1500);
System.out.println(inc);
threadPool.shutdown();
}
}

正常情况下,运行上面的代码理应输出 2500。但你真正运行了上面的代码之后,你会发现每次输出结果都小于 2500

为什么会出现这种情况呢?不是说好了,volatile 可以保证变量的可见性嘛!

也就是说,如果 volatile 能保证 inc++ 操作的原子性的话。每个线程中对 inc 变量自增完之后,其他线程可以立即看到修改后的值。5 个线程分别进行了 500 次操作,那么最终 inc 的值应该是 5*500=2500。

很多人会误认为自增操作 inc++ 是原子性的,实际上,inc++ 其实是一个复合操作,包括三步:

  1. 读取 inc 的值。
  2. 对 inc 加 1。
  3. 将 inc 的值写回内存。

volatile 是无法保证这三个操作是具有原子性的,有可能导致下面这种情况出现:

  1. 线程 1 对 inc 进行读取操作之后,还未对其进行修改。线程 2 又读取了 inc 的值并对其进行修改(+1),再将 inc 的值写回内存。
  2. 线程 2 操作完毕后,线程 1 对 inc 的值进行修改(+1),再将 inc 的值写回内存。

这也就导致两个线程分别对 inc 进行了一次自增操作后,inc 实际上只增加了 1。

其实,如果想要保证上面的代码运行正确也非常简单,利用 synchronizedLock 或者 AtomicInteger 都可以。

::: tabs#线程安全的计数器

@tab synchronized 改进

使用 synchronized 改进:

1
2
3
public synchronized void increase() {
inc++;
}

@tab AtomicInteger 改进

使用 AtomicInteger 改进:

1
2
3
4
5
public AtomicInteger inc = new AtomicInteger();

public void increase() {
inc.getAndIncrement();
}

@tab ReentrantLock 改进

使用 ReentrantLock 改进:

1
2
3
4
5
6
7
8
9
Lock lock = new ReentrantLock();
public void increase() {
lock.lock();
try {
inc++;
} finally {
lock.unlock();
}
}

:::

volatile 的应用

如果 volatile 变量修饰符使用恰当的话,它比 synchronized 的使用和执行成本更低,因为它不会引起线程上下文的切换和调度。但是,**volatile 无法替代 synchronized ,因为 volatile 无法保证操作的原子性**。

volatilesynchronized 的区别在于:

  • volatile 本质是在告诉 jvm 当前变量在寄存器(工作内存)中的值是不确定的,需要从主存中读取;synchronized 则是锁定当前变量,只有当前线程可以访问该变量,其他线程被阻塞住。
  • volatile 仅能修饰变量;synchronized 可以修饰方法和代码块。
  • volatile 仅能实现变量的修改可见性,不能保证原子性;而 synchronized 则可以保证变量的修改可见性和原子性
  • volatile 不会造成线程的阻塞;synchronized 可能会造成线程的阻塞。
  • volatile 标记的变量不会被编译器优化;synchronized 标记的变量可以被编译器优化。

通常来说,使用 volatile 必须具备以下 2 个条件

  • 对变量的写操作不依赖于当前值
  • 该变量没有包含在具有其他变量的表达式中

::: tabs#volatile 的应用

@tab 状态标记量

【示例】状态标记量

1
2
3
4
5
6
7
8
9
volatile boolean flag = false;

while(!flag) {
doSomething();
}

public void setFlag() {
flag = true;
}

@tab 双重锁实现线程安全的单例模式

【示例】双重锁实现线程安全的单例模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Singleton {
private volatile static Singleton instance = null;

private Singleton() {}

public static Singleton getInstance() {
if(instance==null) {
synchronized (Singleton.class) {
if(instance==null)
instance = new Singleton();
}
}
return instance;
}
}

:::

final 内存语义

我们知道,final 成员变量必须在声明的时候初始化或者在构造器中初始化,否则就会报编译错误。 final 关键字的可见性是指:final 字段一旦在声明时或构造器中初始化完成,则其他线程无需同步就能正确看见字段值。这是因为一旦初始化完成,final 变量的值立刻回写到主内存。

long 和 double 的特殊规则

JMM 要求 lockunlockreadloadassignusestorewrite 这 8 种操作都具有原子性,但是对于 64 位的数据类型(long 和 double),在模型中特别定义相对宽松的规定:允许虚拟机将没有被 volatile 修饰的 64 位数据的读写操作分为 2 次 32 位的操作来进行,即允许虚拟机可选择不保证 64 位数据类型的 loadstorereadwrite 这 4 个操作的原子性。由于这种非原子性,有可能导致其他线程读到同步未完成的“32 位的半个变量”的值。

不过实际开发中,Java 内存模型强烈建议虚拟机把 64 位数据的读写实现为具有原子性,目前各种平台下的商用虚拟机都选择把 64 位数据的读写操作作为原子操作来对待,因此我们在编写代码时一般不需要把用到的 longdouble 变量专门声明为 volatile

参考资料

Java 容器之 Stream

Stream 简介

在 Java8 中,Collection 新增了两个流方法,分别是 stream()parallelStream()

Stream 相当于高级版的 Iterator,他可以通过 Lambda 表达式对集合进行各种非常便利、高效的聚合操作(Aggregate Operation),或者大批量数据操作 (Bulk Data Operation)。

Stream 操作分类

官方将 Stream 中的操作分为两大类:中间操作(Intermediate operations)和终结操作(Terminal operations)。

中间操作又可以分为无状态(Stateless)与有状态(Stateful)操作,前者是指元素的处理不受之前元素的影响,后者是指该操作只有拿到所有元素之后才能继续下去。

终结操作又可以分为短路(Short-circuiting)与非短路(Unshort-circuiting)操作,前者是指遇到某些符合条件的元素就可以得到最终结果,后者是指必须处理完所有元素才能得到最终结果。

Stream 源码实现

img

BaseStreamStream 是最顶层的接口类。BaseStream 主要定义了流的基本接口方法,例如,spliterator、isParallel 等;Stream 则定义了一些流的常用操作方法,例如,map、filter 等。

Sink 接口是定义每个 Stream 操作之间关系的协议,他包含 begin()end()cancellationRequested()accpt() 四个方法。ReferencePipeline 最终会将整个 Stream 流操作组装成一个调用链,而这条调用链上的各个 Stream 操作的上下关系就是通过 Sink 接口协议来定义实现的。

ReferencePipeline 是一个结构类,他通过定义内部类组装了各种操作流。他定义了 HeadStatelessOpStatefulOp 三个内部类,实现了 BaseStreamStream 的接口方法。Head 类主要用来定义数据源操作,在初次调用 names.stream() 方法时,会加载 Head 对象,此时为加载数据源操作;接着加载的是中间操作,分别为无状态中间操作 StatelessOp 对象和有状态操作 StatefulOp 对象,此时的 Stage 并没有执行,而是通过 AbstractPipeline 生成了一个中间操作 Stage 链表;当我们调用终结操作时,会生成一个最终的 Stage,通过这个 Stage 触发之前的中间操作,从最后一个 Stage 开始,递归产生一个 Sink 链。

Stream 并行处理

Stream 处理数据的方式有两种,串行处理和并行处理。

4. 参考资料

Java I/O 之 简介

IO 即 Input/Output(输入和输出),指的是:计算机内存与外部设备之间拷贝数据的过程。由于 CPU 访问内存的速度远远高于外部设备,因此 CPU 是先把外部设备的数据读到内存里,然后再进行处理。

UNIX I/O 模型

UNIX 系统下的 I/O 模型有 5 种:

  • 同步阻塞 I/O
  • 同步非阻塞 I/O
  • I/O 多路复用
  • 信号驱动 I/O
  • 异步 I/O

如何去理解 UNIX I/O 模型,大致有以下两个维度:

  • 区分同步或异步(synchronous/asynchronous)。简单来说,同步是一种可靠的有序运行机制,当我们进行同步操作时,后续的任务是等待当前调用返回,才会进行下一步;而异步则相反,其他任务不需要等待当前调用返回,通常依靠事件、回调等机制来实现任务间次序关系。
  • 区分阻塞与非阻塞(blocking/non-blocking)。在进行阻塞操作时,当前线程会处于阻塞状态,无法从事其他任务,只有当条件就绪才能继续,比如 ServerSocket 新连接建立完毕,或数据读取、写入操作完成;而非阻塞则是不管 IO 操作是否结束,直接返回,相应操作在后台继续处理。

不能一概而论认为同步或阻塞就是低效,具体还要看应用和系统特征。

对于一个网络 I/O 通信过程,比如网络数据读取,会涉及两个对象,一个是调用这个 I/O 操作的用户线程,另外一个就是操作系统内核。一个进程的地址空间分为用户空间和内核空间,用户线程不能直接访问内核空间。

当用户线程发起 I/O 操作后,网络数据读取操作会经历两个步骤:

  • 用户线程等待内核将数据从网卡拷贝到内核空间。
  • 内核将数据从内核空间拷贝到用户空间。

各种 I/O 模型的区别就是:它们实现这两个步骤的方式是不一样的。

同步阻塞 I/O

用户线程发起 read 调用后就阻塞了,让出 CPU。内核等待网卡数据到来,把数据从网卡拷贝到内核空间,接着把数据拷贝到用户空间,再把用户线程叫醒。

img

同步非阻塞 I/O

用户线程不断的发起 read 调用,数据没到内核空间时,每次都返回失败,直到数据到了内核空间,这一次 read 调用后,在等待数据从内核空间拷贝到用户空间这段时间里,线程还是阻塞的,等数据到了用户空间再把线程叫醒。

img

I/O 多路复用

用户线程的读取操作分成两步了,线程先发起 select 调用,目的是问内核数据准备好了吗?等内核把数据准备好了,用户线程再发起 read 调用。在等待数据从内核空间拷贝到用户空间这段时间里,线程还是阻塞的。那为什么叫 I/O 多路复用呢?因为一次 select 调用可以向内核查多个数据通道(Channel)的状态,所以叫多路复用。

img

信号驱动 I/O

首先开启 Socket 的信号驱动 I/O 功能,并安装一个信号处理函数,进程继续运行并不阻塞。当数据准备好时,进程会收到一个 SIGIO 信号,可以在信号处理函数中调用 I/O 操作函数处理数据。信号驱动式 I/O 模型的优点是我们在数据报到达期间进程不会被阻塞,我们只要等待信号处理函数的通知即可

异步 I/O

用户线程发起 read 调用的同时注册一个回调函数,read 立即返回,等内核将数据准备好后,再调用指定的回调函数完成处理。在这个过程中,用户线程一直没有阻塞。

img

Java I/O 模型

在 Java 中,主要支持三种 IO 模型:

  • BIO(blocking IO)
  • NIO(non-blocking IO)
  • AIO(Asynchronous IO)

BIO(blocking IO)

BIO(blocking IO) 是同步阻塞 IO 模型。指的主要是传统的 java.io 包,它基于流模型实现。BIO 的数据传输采用同步、阻塞的方式,也就是说,在读取输入流或者写入输出流时,在读、写动作完成之前,线程会一直阻塞在那里。

如果要让 BIO 通信模型 能够同时处理多个客户端请求,就必须使用多线程(主要原因是socket.accept()socket.read()socket.write() 涉及的三个主要函数都是同步阻塞的),但会造成不必要的线程开销。不过可以通过 线程池机制 改善,线程池还可以让线程的创建和回收成本相对较低。

即使可以用线程池略微优化,但是会消耗宝贵的线程资源,并且在百万级并发场景下也撑不住。如果并发访问量增加会导致线程数急剧膨胀可能会导致线程堆栈溢出、创建新线程失败等问题,最终导致进程宕机或者僵死,不能对外提供服务。

NIO(non-blocking IO)

JDK 4 引入了 NIO,源码在 java.nio 包中。NIO(non-blocking IO) 属于 I/O 多路复用模型。NIO 提供了 ChannelSelectorBuffer 等新的抽象,可以构建多路复用的、同步非阻塞 IO 程序,同时提供了更接近操作系统底层的高性能数据操作方式。

NIO 具有以下优点:

  • 使用缓冲区优化读写流 - NIO 与传统 I/O 不同,它是基于块(Block)的,它以块为基本单位处理数据。在 NIO 中,最为重要的两个组件是缓冲区(Buffer)和通道(Channel)。Buffer 是一块连续的内存块,是 NIO 读写数据的缓冲。Buffer 可以将文件一次性读入内存再做后续处理,而传统的方式是边读文件边处理数据。Channel 表示缓冲数据的源头或者目的地,它用于读取缓冲或者写入数据,是访问缓冲的接口。
  • 使用 DirectBuffer 减少内存复制 - NIO 还提供了一个可以直接访问物理内存的类 DirectBuffer。普通的 Buffer 分配的是 JVM 堆内存,而 DirectBuffer 是直接分配物理内存。数据要输出到外部设备,必须先从用户空间复制到内核空间,再复制到输出设备,而 DirectBuffer 则是直接将步骤简化为从内核空间复制到外部设备,减少了数据拷贝。
  • 优化 I/O,避免阻塞 - 传统 I/O 的数据读写是在用户空间和内核空间来回复制,而内核空间的数据是通过操作系统层面的 I/O 接口从磁盘读取或写入。NIO 的 Channel 有自己的处理器,可以完成内核空间和磁盘之间的 I/O 操作。在 NIO 中,我们读取和写入数据都要通过 Channel,由于 Channel 是双向的,所以读、写可以同时进行。

AIO(Asynchronous IO)

AIO(Asynchronous IO) 即异步非阻塞 IO,指的是 JDK7 中,对 NIO 有了进一步的改进,也称为 NIO2,引入了异步非阻塞 IO 方式。异步 IO 操作基于事件和回调机制,可以简单理解为,应用操作直接返回,而不会阻塞在那里,当后台处理完成,操作系统会通知相应线程进行后续工作。

参考资料

跳表

什么是跳表

对于一个有序数组,可以使用高效的二分查找法,其时间复杂度为 O(log n)

但是,即使是有序的链表,也只能使用低效的顺序查找,其时间复杂度为 O(n)

img

如何提高链表的查找效率呢?

我们可以对链表加一层索引。具体来说,可以每两个结点提取一个结点到上一级,我们把抽出来的那一级叫作索引索引层。索引节点中通过一个 down 指针,指向下一级结点。通过这样的改造,就可以支持类似二分查找的算法。我们把改造之后的数据结构叫作跳表(Skip list)。

img

随着数据的不断增长,一级索引层也变得越来越长。此时,我们可以为一级索引再增加一层索引层:二级索引层。

img

随着数据的膨胀,当二级索引层也变得很长时,我们可以继续为其添加新的索引层。这种链表加多级索引的结构,就是跳表

img

跳表的时间复杂度

在一个具有多级索引的跳表中,第一级索引的结点个数大约就是 n/2,第二级索引的结点个数大约就是 n/4,第三级索引的结点个数大约就是 n/8,依次类推,也就是说,第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,那第 k 级索引结点的个数就是 n/(2k)。所以**跳表查询数据的时间复杂度就是 O(logn)**。

跳表的空间复杂度

比起单纯的单链表,跳表需要存储多级索引,肯定要消耗更多的存储空间。

假设原始链表大小为 n,那第一级索引大约有 n/2 个结点,第二级索引大约有 n/4 个结点,以此类推,每上升一级就减少一半,直到剩下 2 个结点。如果我们把每层索引的结点数写出来,就是一个等比数列。

1
索引节点数 = n/2 + n/4 + n/8 … + 8 + 4 + 2 = n-2

所以,跳表的空间复杂度是 O(n)

跳表的存储空间其实还有压缩空间。比如,我们增加索引节点的范围,由“每两个节点抽一个上级索引节点”改为“每五个节点抽一个上级索引节点”,可以显著节省存储空间。

实际上,在软件开发中,我们不必太在意索引占用的额外空间。在讲数据结构和算法时,我们习惯性地把要处理的数据看成整数,但是在实际的软件开发中,原始链表中存储的有可能是很大的对象,而索引结点只需要存储关键值和几个指针,并不需要存储对象,所以当对象比索引结点大很多时,那索引占用的额外空间就可以忽略了。

跳表的操作

跳表是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。

高效的动态插入和删除

跳表不仅支持查找操作,还支持动态的插入、删除操作,而且插入、删除操作的时间复杂度也是 O(logn)

img

  • 插入操作:对于纯粹的单链表,需要遍历每个结点,来找到插入的位置。但是,对于跳表来说,我们讲过查找某个结点的的时间复杂度是 O(log n),所以这里查找某个数据应该插入的位置,方法也是类似的,时间复杂度也是 O(log n)
  • 删除操作:如果这个结点在索引中也有出现,我们除了要删除原始链表中的结点,还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点,然后通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点。当然,如果我们用的是双向链表,就不需要考虑这个问题了。

跳表索引动态更新

当我们不停地往跳表中插入数据时,如果我们不更新索引,就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表。

img

如红黑树、AVL 树这样的平衡二叉树,是通过左右旋的方式保持左右子树的大小平衡,而跳表是通过随机函数来维护前面提到的“平衡性”。

当我们往跳表中插入数据的时候,我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢?可以通过一个随机函数,来决定将这个结点插入到哪几级索引中,比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

为什么需要跳表

跳表是一种动态数据结构,支持快速的插入、删除、查找操作,时间复杂度都是 O(logn)

跳表的空间复杂度是 O(n)。不过,跳表的实现非常灵活,可以通过改变索引构建策略,有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单,但是作为一种动态数据结构,比起红黑树来说,实现要简单多了。所以很多时候,我们为了代码的简单、易读,比起红黑树,我们更倾向用跳表。

跳表的应用场景

经典实现:Redis 的 Sorted Set、JDK 的 ConcurrentSkipListMapConcurrentSkipListSet 都是基于跳表实现。

为什么 Redis 要用跳表来实现有序集合,而不是红黑树?

Redis 中的有序集合支持的核心操作主要有下面这几个:

  • 插入一个数据;
  • 删除一个数据;
  • 查找一个数据;
  • 按照区间查找数据(比如查找值在 [100, 356] 之间的数据);
  • 迭代输出有序序列。

其中,插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高。

参考资料

Java 控制语句

Java 控制语句大致可分为三大类:

  • 选择语句
    • if, else-if, else
    • switch
  • 循环语句
    • while
    • do…while
    • for
    • foreach
  • 中断语句
    • break
    • continue
    • return

选择语句

if 语句

if 语句会判断括号中的条件是否成立,如果成立则执行 if 语句中的代码块,否则跳过代码块继续执行。

语法

1
2
3
if(布尔表达式) {
//如果布尔表达式为true将执行的语句
}

示例

1
2
3
4
5
6
7
8
9
10
public class IfDemo {
public static void main(String args[]) {
int x = 10;
if (x < 20) {
System.out.print("这是 if 语句");
}
}
}
// output:
// 这是 if 语句

if…else 语句

if 语句后面可以跟 else 语句,当 if 语句的布尔表达式值为 false 时,else 语句块会被执行。

语法

1
2
3
4
5
if(布尔表达式) {
//如果布尔表达式的值为true
} else {
//如果布尔表达式的值为false
}

示例

1
2
3
4
5
6
7
8
9
10
11
12
public class IfElseDemo {
public static void main(String args[]) {
int x = 30;
if (x < 20) {
System.out.print("这是 if 语句");
} else {
System.out.print("这是 else 语句");
}
}
}
// output:
// 这是 else 语句

if…else if…else 语句

  • if 语句至多有 1 个 else 语句,else 语句在所有的 else if 语句之后。
  • If 语句可以有若干个 else if 语句,它们必须在 else 语句之前。
  • 一旦其中一个 else if 语句检测为 true,其他的 else if 以及 else 语句都将跳过执行。

语法

1
2
3
4
5
6
7
8
9
if (布尔表达式 1) {
//如果布尔表达式 1的值为true执行代码
} else if (布尔表达式 2) {
//如果布尔表达式 2的值为true执行代码
} else if (布尔表达式 3) {
//如果布尔表达式 3的值为true执行代码
} else {
//如果以上布尔表达式都不为true执行代码
}

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class IfElseifElseDemo {
public static void main(String args[]) {
int x = 3;

if (x == 1) {
System.out.print("Value of X is 1");
} else if (x == 2) {
System.out.print("Value of X is 2");
} else if (x == 3) {
System.out.print("Value of X is 3");
} else {
System.out.print("This is else statement");
}
}
}
// output:
// Value of X is 3

嵌套的 if…else 语句

使用嵌套的 if else 语句是合法的。也就是说你可以在另一个 if 或者 else if 语句中使用 if 或者 else if 语句。

语法

1
2
3
4
5
6
if (布尔表达式 1) {
////如果布尔表达式 1的值为true执行代码
if (布尔表达式 2) {
////如果布尔表达式 2的值为true执行代码
}
}

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class IfNestDemo {
public static void main(String args[]) {
int x = 30;
int y = 10;

if (x == 30) {
if (y == 10) {
System.out.print("X = 30 and Y = 10");
}
}
}
}
// output:
// X = 30 and Y = 10

switch 语句

switch 语句判断一个变量与一系列值中某个值是否相等,每个值称为一个分支。

switch 语句有如下规则:

  • switch 语句中的变量类型只能为 byteshortintchar 或者 String
  • switch 语句可以拥有多个 case 语句。每个 case 后面跟一个要比较的值和冒号。
  • case 语句中的值的数据类型必须与变量的数据类型相同,而且只能是常量或者字面常量。
  • 当变量的值与 case 语句的值相等时,那么 case 语句之后的语句开始执行,直到 break 语句出现才会跳出 switch 语句。
  • 当遇到 break 语句时,switch 语句终止。程序跳转到 switch 语句后面的语句执行。case 语句不必须要包含 break 语句。如果没有 break 语句出现,程序会继续执行下一条 case 语句,直到出现 break 语句。
  • switch 语句可以包含一个 default 分支,该分支必须是 switch 语句的最后一个分支。default 在没有 case 语句的值和变量值相等的时候执行。default 分支不需要 break 语句。

语法

1
2
3
4
5
6
7
8
9
10
11
12
switch(expression){
case value :
//语句
break; //可选
case value :
//语句
break; //可选
//你可以有任意数量的case语句
default : //可选
//语句
break; //可选,但一般建议加上
}

示例

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
public class SwitchDemo {
public static void main(String args[]) {
char grade = 'C';

switch (grade) {
case 'A':
System.out.println("Excellent!");
break;
case 'B':
case 'C':
System.out.println("Well done");
break;
case 'D':
System.out.println("You passed");
case 'F':
System.out.println("Better try again");
break;
default:
System.out.println("Invalid grade");
break;
}
System.out.println("Your grade is " + grade);
}
}
// output:
// Well done
// Your grade is C

循环语句

while 循环

只要布尔表达式为 truewhile 循环体会一直执行下去。

语法

1
2
3
while( 布尔表达式 ) {
//循环内容
}

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class WhileDemo {
public static void main(String args[]) {
int x = 10;
while (x < 20) {
System.out.print("value of x : " + x);
x++;
System.out.print("\n");
}
}
}
// output:
// value of x : 10
// value of x : 11
// value of x : 12
// value of x : 13
// value of x : 14
// value of x : 15
// value of x : 16
// value of x : 17
// value of x : 18
// value of x : 19

do while 循环

对于 while 语句而言,如果不满足条件,则不能进入循环。但有时候我们需要即使不满足条件,也至少执行一次。

do while 循环和 while 循环相似,不同的是,do while 循环至少会执行一次。

语法

1
2
3
do {
//代码语句
} while (布尔表达式);

布尔表达式在循环体的后面,所以语句块在检测布尔表达式之前已经执行了。 如果布尔表达式的值为 true,则语句块一直执行,直到布尔表达式的值为 false。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class DoWhileDemo {
public static void main(String args[]) {
int x = 10;

do {
System.out.print("value of x : " + x);
x++;
System.out.print("\n");
} while (x < 20);
}
}
// output:
// value of x:10
// value of x:11
// value of x:12
// value of x:13
// value of x:14
// value of x:15
// value of x:16
// value of x:17
// value of x:18
// value of x:19

for 循环

虽然所有循环结构都可以用 while 或者 do while 表示,但 Java 提供了另一种语句 —— for 循环,使一些循环结构变得更加简单。
for 循环执行的次数是在执行前就确定的。

语法

1
2
3
for (初始化; 布尔表达式; 更新) {
//代码语句
}
  • 最先执行初始化步骤。可以声明一种类型,但可初始化一个或多个循环控制变量,也可以是空语句。
  • 然后,检测布尔表达式的值。如果为 true,循环体被执行。如果为 false,循环终止,开始执行循环体后面的语句。
  • 执行一次循环后,更新循环控制变量。
  • 再次检测布尔表达式。循环执行上面的过程。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class ForDemo {
public static void main(String args[]) {
for (int x = 10; x < 20; x = x + 1) {
System.out.print("value of x : " + x);
System.out.print("\n");
}
}
}
// output:
// value of x : 10
// value of x : 11
// value of x : 12
// value of x : 13
// value of x : 14
// value of x : 15
// value of x : 16
// value of x : 17
// value of x : 18
// value of x : 19

foreach 循环

Java5 引入了一种主要用于数组的增强型 for 循环。

语法

1
2
3
for (声明语句 : 表达式) {
//代码句子
}

声明语句:声明新的局部变量,该变量的类型必须和数组元素的类型匹配。其作用域限定在循环语句块,其值与此时数组元素的值相等。

表达式:表达式是要访问的数组名,或者是返回值为数组的方法。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ForeachDemo {
public static void main(String args[]) {
int[] numbers = { 10, 20, 30, 40, 50 };

for (int x : numbers) {
System.out.print(x);
System.out.print(",");
}

System.out.print("\n");
String[] names = { "James", "Larry", "Tom", "Lacy" };

for (String name : names) {
System.out.print(name);
System.out.print(",");
}
}
}
// output:
// 10,20,30,40,50,
// James,Larry,Tom,Lacy,

中断语句

break 关键字

break 主要用在循环语句或者 switch 语句中,用来跳出整个语句块。

break 跳出最里层的循环,并且继续执行该循环下面的语句。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class BreakDemo {
public static void main(String args[]) {
int[] numbers = { 10, 20, 30, 40, 50 };

for (int x : numbers) {
if (x == 30) {
break;
}
System.out.print(x);
System.out.print("\n");
}

System.out.println("break 示例结束");
}
}
// output:
// 10
// 20
// break 示例结束

continue 关键字

continue 适用于任何循环控制结构中。作用是让程序立刻跳转到下一次循环的迭代。在 for 循环中,continue 语句使程序立即跳转到更新语句。在 while 或者 do while 循环中,程序立即跳转到布尔表达式的判断语句。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ContinueDemo {
public static void main(String args[]) {
int[] numbers = { 10, 20, 30, 40, 50 };

for (int x : numbers) {
if (x == 30) {
continue;
}
System.out.print(x);
System.out.print("\n");
}
}
}
// output:
// 10
// 20
// 40
// 50

return 关键字

跳出整个函数体,函数体后面的部分不再执行。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ReturnDemo {
public static void main(String args[]) {
int[] numbers = { 10, 20, 30, 40, 50 };

for (int x : numbers) {
if (x == 30) {
return;
}
System.out.print(x);
System.out.print("\n");
}

System.out.println("return 示例结束");
}
}
// output:
// 10
// 20

🔔 注意:请仔细体会一下 returnbreak 的区别。

最佳实践

  • 选择分支特别多的情况下,switch 语句优于 if...else if...else 语句。
  • switch 语句不要吝啬使用 default
  • switch 语句中的 default 要放在最后。
  • foreach 循环优先于传统的 for 循环
  • 不要循环遍历容器元素,然后删除特定元素。正确姿势应该是遍历容器的迭代器(Iterator),删除元素。

参考资料

深入理解 Java 泛型

什么是泛型

Java 泛型(generics)是 JDK 5 中引入的特性

为什么要引入泛型机制呢?

回答这个问题前,先让我们来看一个示例。

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
public class NoGenericsDemo {
public static void main(String[] args) {
List list = new ArrayList<>();
list.add("abc");
list.add(18);
list.add(new double[] {1.0, 2.0});
Object obj1 = list.get(0);
Object obj2 = list.get(1);
Object obj3 = list.get(2);
System.out.println("obj1 = [" + obj1 + "]");
System.out.println("obj2 = [" + obj2 + "]");
System.out.println("obj3 = [" + obj3 + "]");

int num1 = (int)list.get(0);
int num2 = (int)list.get(1);
int num3 = (int)list.get(2);
System.out.println("num1 = [" + num1 + "]");
System.out.println("num2 = [" + num2 + "]");
System.out.println("num3 = [" + num3 + "]");
}
}
// Output:
// obj1 = [abc]
// obj2 = [18]
// obj3 = [[D@47089e5f]
// Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer
// at io.github.dunwu.javacore.generics.NoGenericsDemo.main(NoGenericsDemo.java:23)

示例说明:

在上面的示例中,List 容器没有指定存储数据类型,这种情况下,可以向 List 添加任意类型数据,编译器不会做类型检查,而是默默的将所有数据都转为 Object

假设,最初我们希望向 List 存储的是整形数据,假设,某个家伙不小心存入了其他数据类型。当你试图从容器中取整形数据时,由于 List 当成 Object 类型来存储,你不得不使用类型强制转换。在运行时,才会发现 List 中数据不存储一致的问题,这就为程序运行带来了很大的风险(无形伤害最为致命)。

引入泛型机制,正是为了解决这种类型安全问题。“泛型”提供了编译时类型安全检测机制,该机制会在编译时检测到非法的类型

泛型具有以下优点

  • 编译时的强类型检查 - 泛型要求在声明时指定实际数据类型,Java 编译器在编译时会对泛型代码做强类型检查,并在代码违反类型安全时发出告警。早发现,早治理,把隐患扼杀于摇篮,在编译时发现并修复错误所付出的代价远比在运行时小。

  • 避免了类型转换

未使用泛型:

1
2
3
List list = new ArrayList();
list.add("hello");
String s = (String) list.get(0);

使用泛型:

1
2
3
List<String> list = new ArrayList<String>();
list.add("hello");
String s = list.get(0); // no cast
  • 泛型编程可以实现通用算法 - 通过使用泛型,程序员可以实现通用算法,这些算法可以处理不同类型的集合,可以自定义,并且类型安全且易于阅读。

泛型声明

“泛型类型”是被参数化的类或接口。

泛型类

泛型类的语法形式:

1
class name<T1, T2, ..., Tn> { /* ... */ }

泛型类的声明和非泛型类的声明类似,除了在类名后面添加了类型参数声明部分。由尖括号(<>)分隔的类型参数部分跟在类名后面。它指定类型参数(也称为类型变量)T1,T2,…和 Tn。

一般将泛型中的类名称为原型,而将 <> 指定的参数称为类型参数

  • 未应用泛型的类

在泛型出现之前,如果一个类想持有一个可以为任意类型的数据,只能使用 Object 做类型转换。示例如下:

1
2
3
4
5
6
7
8
9
10
11
public class Info {
private Object value;

public Object getValue() {
return value;
}

public void setValue(Object value) {
this.value = value;
}
}
  • 单类型参数的泛型类
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
public class Info<T> {
private T value;

public Info() { }

public Info(T value) {
this.value = value;
}

public T getValue() {
return value;
}

public void setValue(T value) {
this.value = value;
}

@Override
public String toString() {
return "Info{" + "value=" + value + '}';
}
}

public class GenericsClassDemo01 {
public static void main(String[] args) {
Info<Integer> info = new Info<>();
info.setValue(10);
System.out.println(info.getValue());

Info<String> info2 = new Info<>();
info2.setValue("xyz");
System.out.println(info2.getValue());
}
}
// Output:
// 10
// xyz

在上面的例子中,在初始化一个泛型类时,使用 <> 指定了内部具体类型,在编译时就会根据这个类型做强类型检查。

实际上,不使用 <> 指定内部具体类型,语法上也是支持的(不推荐这么做),如下所示:

1
2
3
4
5
6
7
public static void main(String[] args) {
Info info = new Info();
info.setValue(10);
System.out.println(info.getValue());
info.setValue("abc");
System.out.println(info.getValue());
}

示例说明:

上面的例子,不会产生编译错误,也能正常运行。但这样的调用就失去泛型类型的优势。

  • 多个类型参数的泛型类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class MyMap<K,V> {
private K key;
private V value;

public MyMap(K key, V value) {
this.key = key;
this.value = value;
}

@Override
public String toString() {
return "MyMap{" + "key=" + key + ", value=" + value + '}';
}
}

public class GenericsClassDemo02 {
public static void main(String[] args) {
MyMap<Integer, String> map = new MyMap<>(1, "one");
System.out.println(map);
}
}
// Output:
// MyMap{key=1, value=one}
  • 泛型类的类型嵌套
1
2
3
4
5
6
7
8
9
public class GenericsClassDemo03 {
public static void main(String[] args) {
Info<String> info = new Info("Hello");
MyMap<Integer, Info<String>> map = new MyMap<>(1, info);
System.out.println(map);
}
}
// Output:
// MyMap{key=1, value=Info{value=Hello}}

泛型接口

接口也可以声明泛型。

泛型接口语法形式:

1
2
3
public interface Content<T> {
T text();
}

泛型接口有两种实现方式:

  • 实现接口的子类明确声明泛型类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19


public class GenericsInterfaceDemo01 implements Content<Integer> {
private int text;

public GenericsInterfaceDemo01(int text) {
this.text = text;
}

@Override
public Integer text() { return text; }

public static void main(String[] args) {
GenericsInterfaceDemo01 demo = new GenericsInterfaceDemo01(10);
System.out.print(demo.text());
}
}
// Output:
// 10
  • 实现接口的子类不明确声明泛型类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class GenericsInterfaceDemo02<T> implements Content<T> {
private T text;

public GenericsInterfaceDemo02(T text) {
this.text = text;
}

@Override
public T text() { return text; }

public static void main(String[] args) {
GenericsInterfaceDemo02<String> gen = new GenericsInterfaceDemo02<>("ABC");
System.out.print(gen.text());
}
}
// Output:
// ABC

泛型方法

泛型方法是引入其自己的类型参数的方法。泛型方法可以是普通方法、静态方法以及构造方法。

泛型方法语法形式如下:

1
public <T> T func(T obj) {}

是否拥有泛型方法,与其所在的类是否是泛型没有关系。

泛型方法的语法包括一个类型参数列表,在尖括号内,它出现在方法的返回类型之前。对于静态泛型方法,类型参数部分必须出现在方法的返回类型之前。类型参数能被用来声明返回值类型,并且能作为泛型方法得到的实际类型参数的占位符。

使用泛型方法的时候,通常不必指明类型参数,因为编译器会为我们找出具体的类型,这称为“类型参数推断(type argument inference)”。类型推断只对赋值操作有效,其他时候并不起作用。如果将一个返回类型为 T 的泛型方法调用的结果作为参数,传递给另一个方法,这时编译器并不会执行推断。编译器会认为:调用泛型方法后,其返回值被赋给一个 Object 类型的变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class GenericsMethodDemo01 {
public static <T> void printClass(T obj) {
System.out.println(obj.getClass().toString());
}

public static void main(String[] args) {
printClass("abc");
printClass(10);
}
}
// Output:
// class java.lang.String
// class java.lang.Integer

泛型方法中也可以使用可变参数列表。示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class GenericVarargsMethodDemo {
public static <T> List<T> makeList(T... args) {
List<T> result = new ArrayList<T>();
Collections.addAll(result, args);
return result;
}

public static void main(String[] args) {
List<String> ls = makeList("A");
System.out.println(ls);
ls = makeList("A", "B", "C");
System.out.println(ls);
}
}
// Output:
// [A]
// [A, B, C]

泛型要点

类型擦除

Java 语言引入泛型是为了在编译时提供更严格的类型检查,并支持泛型编程。不同于 C++ 的模板机制,Java 泛型是使用“类型擦除”来实现的,使用泛型时,任何具体的类型信息都被擦除了

那么,类型擦除做了什么呢?它做了以下工作:

  • 把泛型中的所有类型参数替换为 Object,如果指定类型边界,则使用类型边界来替换。因此,生成的字节码仅包含普通的类,接口和方法。
  • 擦除出现的类型声明,即去掉 <> 的内容。比如 T get() 方法声明就变成了 Object get()List<String> 就变成了 List。如有必要,插入类型转换以保持类型安全。
  • 生成桥接方法以保留扩展泛型类型中的多态性。类型擦除确保不为参数化类型创建新类;因此,泛型不会产生运行时开销。

让我们来看一个示例:

1
2
3
4
5
6
7
8
9
10
11
public class GenericsErasureTypeDemo {
public static void main(String[] args) {
List<Object> list1 = new ArrayList<Object>();
List<String> list2 = new ArrayList<String>();
System.out.println(list1.getClass());
System.out.println(list2.getClass());
}
}
// Output:
// class java.util.ArrayList
// class java.util.ArrayList

示例说明:

上面的例子中,虽然指定了不同的类型参数,但是 list1 和 list2 的类信息却是一样的。

这是因为:使用泛型时,任何具体的类型信息都被擦除了。这意味着:ArrayList<Object>ArrayList<String> 在运行时,JVM 将它们视为同一类型。

Java 泛型的实现方式不太优雅,但这是因为泛型是在 JDK5 时引入的,为了兼容老代码,必须在设计上做一定的折中。

泛型和继承

泛型不能用于显式地引用运行时类型的操作之中(例如:转型、instanceof 操作和 new 表达式),因为所有关于参数的类型信息都丢失了。当你在编写泛型代码时,必须时刻提醒自己,你只是看起来好像拥有有关参数的类型信息而已。

正是由于泛型时基于类型擦除实现的,所以,泛型类型无法向上转型

向上转型是指用子类实例去初始化父类,这是面向对象中多态的重要表现。

img

Integer 继承了 ObjectArrayList 继承了 List;但是 List<Interger> 却并非继承了 List<Object>

这是因为,泛型类并没有自己独有的 Class 类对象。比如:并不存在 List<Object>.class 或是 List<Interger>.class,Java 编译器会将二者都视为 List.class

1
2
List<Integer> list = new ArrayList<>();
List<Object> list2 = list; // Erorr

类型边界

有时您可能希望限制可在参数化类型中用作类型参数的类型。“类型边界”可以对泛型的类型参数设置限制条件。例如,对数字进行操作的方法可能只想接受 Number 或其子类的实例。

要声明有界类型参数,请列出类型参数的名称,然后是 extends 关键字,后跟其限制类或接口。

类型边界的语法形式如下:

1
<T extends XXX>

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class GenericsExtendsDemo01 {
static <T extends Comparable<T>> T max(T x, T y, T z) {
T max = x; // 假设x是初始最大值
if (y.compareTo(max) > 0) {
max = y; //y 更大
}
if (z.compareTo(max) > 0) {
max = z; // 现在 z 更大
}
return max; // 返回最大对象
}

public static void main(String[] args) {
System.out.println(max(3, 4, 5));
System.out.println(max(6.6, 8.8, 7.7));
System.out.println(max("pear", "apple", "orange"));
}
}
// Output:
// 5
// 8.8
// pear

示例说明:

上面的示例声明了一个泛型方法,类型参数 T extends Comparable<T> 表明传入方法中的类型必须实现了 Comparable 接口。

类型边界可以设置多个,语法形式如下:

1
<T extends B1 & B2 & B3>

🔔 注意:extends 关键字后面的第一个类型参数可以是类或接口,其他类型参数只能是接口。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class GenericsExtendsDemo02 {
static class A { /* ... */ }
interface B { /* ... */ }
interface C { /* ... */ }
static class D1 <T extends A & B & C> { /* ... */ }
static class D2 <T extends B & A & C> { /* ... */ } // 编译报错
static class E extends A implements B, C { /* ... */ }

public static void main(String[] args) {
D1<E> demo1 = new D1<>();
System.out.println(demo1.getClass().toString());
D1<String> demo2 = new D1<>(); // 编译报错
}
}

类型通配符

“类型通配符”一般使用 ? 代替具体的类型参数。例如 List<?> 在逻辑上是 List<String>List<Integer> 等所有 List<具体类型实参> 的父类。

上界通配符

可以使用“上界通配符”来缩小类型参数的类型范围。

它的语法形式为:<? extends Number>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class GenericsUpperBoundedWildcardDemo {
public static double sumOfList(List<? extends Number> list) {
double s = 0.0;
for (Number n : list) {
s += n.doubleValue();
}
return s;
}

public static void main(String[] args) {
List<Integer> li = Arrays.asList(1, 2, 3);
System.out.println("sum = " + sumOfList(li));
}
}
// Output:
// sum = 6.0

下界通配符

“下界通配符”将未知类型限制为该类型的特定类型或超类类型

🔔 注意:上界通配符和下界通配符不能同时使用

它的语法形式为:<? super Number>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class GenericsLowerBoundedWildcardDemo {
public static void addNumbers(List<? super Integer> list) {
for (int i = 1; i <= 5; i++) {
list.add(i);
}
}

public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
addNumbers(list);
System.out.println(Arrays.deepToString(list.toArray()));
}
}
// Output:
// [1, 2, 3, 4, 5]

无界通配符

无界通配符有两种应用场景:

  • 可以使用 Object 类中提供的功能来实现的方法。
  • 使用不依赖于类型参数的泛型类中的方法。

语法形式:<?>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class GenericsUnboundedWildcardDemo {
public static void printList(List<?> list) {
for (Object elem : list) {
System.out.print(elem + " ");
}
System.out.println();
}

public static void main(String[] args) {
List<Integer> li = Arrays.asList(1, 2, 3);
List<String> ls = Arrays.asList("one", "two", "three");
printList(li);
printList(ls);
}
}
// Output:
// 1 2 3
// one two three

通配符和向上转型

前面,我们提到:泛型不能直接向上转型;但是,我们可以通过使用通配符来间接向上转型

1
2
3
4
5
6
7
8
9
public class GenericsWildcardDemo {
public static void main(String[] args) {
List<Integer> intList = new ArrayList<>();
List<Number> numList = intList; // Error

List<? extends Integer> intList2 = new ArrayList<>();
List<? extends Number> numList2 = intList2; // OK
}
}

扩展阅读:Oracle 泛型文档

泛型的约束

1
Pair<int, char> p = new Pair<>(8, 'a');  // 编译错误
1
2
3
4
public static <E> void append(List<E> list) {
E elem = new E(); // 编译错误
list.add(elem);
}
1
2
3
4
5
public class MobileDevice<T> {
private static T os; // error

// ...
}
1
2
3
4
5
public static <E> void rtti(List<E> list) {
if (list instanceof ArrayList<Integer>) { // 编译错误
// ...
}
}
1
2
List<Integer> li = new ArrayList<>();
List<Number> ln = (List<Number>) li; // 编译错误
1
List<Integer>[] arrayOfLists = new List<Integer>[2];  // 编译错误
1
2
3
4
5
// Extends Throwable indirectly
class MathException<T> extends Exception { /* ... */ } // 编译错误

// Extends Throwable directly
class QueueFullException<T> extends Throwable { /* ... */ // 编译错误
1
2
3
4
5
6
7
8
public static <T extends Exception, J> void execute(List<J> jobs) {
try {
for (J job : jobs)
// ...
} catch (T e) { // compile-time error
// ...
}
}
1
2
3
4
public class Example {
public void print(Set<String> strSet) { }
public void print(Set<Integer> intSet) { } // 编译错误
}

泛型最佳实践

泛型命名

Java 泛型有一些约定俗成的命名:

  • E - Element
  • K - Key
  • N - Number
  • T - Type
  • V - Value
  • SUV - 2nd, 3rd, 4th types

使用泛型的建议

  • 消除类型检查告警
  • List 优先于数组
  • 优先考虑使用泛型来提高代码通用性
  • 优先考虑泛型方法来限定泛型的范围
  • 利用有限制通配符来提升 API 的灵活性
  • 优先考虑类型安全的异构容器

参考资料

ShardingSphere 简介

简介

shardingsphere-jdbc 定位为轻量级 Java 框架,在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库,以 jar 包形式提供服务,无需额外部署和依赖,可理解为增强版的 JDBC 驱动,完全兼容 JDBC 和各种 ORM 框架。

  • 适用于任何基于 JDBC 的 ORM 框架,如:JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC。
  • 支持任何第三方的数据库连接池,如:DBCP, C3P0, BoneCP, Druid, HikariCP 等。
  • 支持任意实现 JDBC 规范的数据库,目前支持 MySQL,Oracle,SQLServer,PostgreSQL 以及任何遵循 SQL92 标准的数据库。

img

ShardingSphere 组件

ShardingSphere 是一套开源的分布式数据库中间件解决方案组成的生态圈,它由 Sharding-JDBC、Sharding-Proxy 和 Sharding-Sidecar(计划中)这 3 款相互独立的产品组成。 他们均提供标准化的数据分片、分布式事务和数据库治理功能,可适用于如 Java 同构、异构语言、云原生等各种多样化的应用场景。

img

ShardingSphere-JDBC

定位为轻量级 Java 框架,在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库,以 jar 包形式提供服务,无需额外部署和依赖,可理解为增强版的 JDBC 驱动,完全兼容 JDBC 和各种 ORM 框架。

  • 适用于任何基于 JDBC 的 ORM 框架,如:JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC。
  • 支持任何第三方的数据库连接池,如:DBCP, C3P0, BoneCP, Druid, HikariCP 等。
  • 支持任意实现 JDBC 规范的数据库,目前支持 MySQL,Oracle,SQLServer,PostgreSQL 以及任何遵循 SQL92 标准的数据库。

img

Sharding-Proxy

定位为透明化的数据库代理端,提供封装了数据库二进制协议的服务端版本,用于完成对异构语言的支持。 目前提供 MySQL 和 PostgreSQL 版本,它可以使用任何兼容 MySQL/PostgreSQL 协议的访问客户端(如:MySQL Command Client, MySQL Workbench, Navicat 等)操作数据,对 DBA 更加友好。

  • 向应用程序完全透明,可直接当做 MySQL/PostgreSQL 使用。
  • 适用于任何兼容 MySQL/PostgreSQL 协议的的客户端。

img

Sharding-Sidecar(TODO)

定位为 Kubernetes 的云原生数据库代理,以 Sidecar 的形式代理所有对数据库的访问。 通过无中心、零侵入的方案提供与数据库交互的的啮合层,即 Database Mesh,又可称数据库网格。

Database Mesh 的关注重点在于如何将分布式的数据访问应用与数据库有机串联起来,它更加关注的是交互,是将杂乱无章的应用与数据库之间的交互进行有效地梳理。 使用 Database Mesh,访问数据库的应用和数据库终将形成一个巨大的网格体系,应用和数据库只需在网格体系中对号入座即可,它们都是被啮合层所治理的对象。

img

Sharding-JDBC Sharding-Proxy Sharding-Sidecar
数据库 任意 MySQL MySQL
连接消耗数
异构语言 仅 Java 任意 任意
性能 损耗低 损耗略高 损耗低
无中心化
静态入口

混合架构

ShardingSphere-JDBC 采用无中心化架构,适用于 Java 开发的高性能的轻量级 OLTP 应用;ShardingSphere-Proxy 提供静态入口以及异构语言的支持,适用于 OLAP 应用以及对分片数据库进行管理和运维的场景。

Apache ShardingSphere 是多接入端共同组成的生态圈。 通过混合使用 ShardingSphere-JDBC 和 ShardingSphere-Proxy,并采用同一注册中心统一配置分片策略,能够灵活的搭建适用于各种场景的应用系统,使得架构师更加自由地调整适合与当前业务的最佳系统架构。

img

功能列表

数据分片

  • 分库 & 分表
  • 读写分离
  • 分片策略定制化
  • 无中心化分布式主键

分布式事务

  • 标准化事务接口
  • XA 强一致事务
  • 柔性事务

数据库治理

  • 分布式治理
  • 弹性伸缩
  • 可视化链路追踪
  • 数据加密

快速入门

引入 maven 依赖

1
2
3
4
5
<dependency>
<groupId>org.apache.shardingsphere</groupId>
<artifactId>shardingsphere-jdbc-core</artifactId>
<version>${latest.release.version}</version>
</dependency>

注意:请将 ${latest.release.version} 更改为实际的版本号。

规则配置

ShardingSphere-JDBC 可以通过 JavaYAMLSpring 命名空间Spring Boot Starter 这 4 种方式进行配置,开发者可根据场景选择适合的配置方式。 详情请参见配置手册

创建数据源

通过 ShardingSphereDataSourceFactory 工厂和规则配置对象获取 ShardingSphereDataSource。 该对象实现自 JDBC 的标准 DataSource 接口,可用于原生 JDBC 开发,或使用 JPA, MyBatis 等 ORM 类库。

1
DataSource dataSource = ShardingSphereDataSourceFactory.createDataSource(dataSourceMap, configurations, properties);

概念和功能

单一数据节点难于满足互联网的海量数据场景。

从性能方面来说,由于关系型数据库大多采用 B+ 树类型的索引,在数据量超过阈值的情况下,索引深度的增加也将使得磁盘访问的 IO 次数增加,进而导致查询性能的下降;同时,高并发访问请求也使得集中式数据库成为系统的最大瓶颈。

在传统的关系型数据库无法满足互联网场景需要的情况下,将数据存储至原生支持分布式的 NoSQL 的尝试越来越多。 但 NoSQL 对 SQL 的不兼容性以及生态圈的不完善,使得它们在与关系型数据库的博弈中始终无法完成致命一击,而关系型数据库的地位却依然不可撼动。

数据分片按照某个维度将存放在单一数据库中的数据分散地存放至多个数据库或表中以达到提升性能瓶颈以及可用性的效果。数据分片的有效手段是对关系型数据库进行分库和分表。分库和分表均可以有效的避免由数据量超过可承受阈值而产生的查询瓶颈。 除此之外,分库还能够用于有效的分散对数据库单点的访问量;分表虽然无法缓解数据库压力,但却能够提供尽量将分布式事务转化为本地事务的可能,一旦涉及到跨库的更新操作,分布式事务往往会使问题变得复杂。 使用多主多从的分片方式,可以有效的避免数据单点,从而提升数据架构的可用性。

通过分库和分表进行数据的拆分来使得各个表的数据量保持在阈值以下,以及对流量进行疏导应对高访问量,是应对高并发和海量数据系统的有效手段。 数据分片的拆分方式又分为垂直分片和水平分片。

垂直分片

按照业务拆分的方式称为垂直分片,又称为纵向拆分,它的核心理念是专库专用。 在拆分之前,一个数据库由多个数据表构成,每个表对应着不同的业务。而拆分之后,则是按照业务将表进行归类,分布到不同的数据库中,从而将压力分散至不同的数据库。 下图展示了根据业务需要,将用户表和订单表垂直分片到不同的数据库的方案。

垂直分片

垂直分片往往需要对架构和设计进行调整。通常来讲,是来不及应对互联网业务需求快速变化的;而且,它也并无法真正的解决单点瓶颈。 垂直拆分可以缓解数据量和访问量带来的问题,但无法根治。如果垂直拆分之后,表中的数据量依然超过单节点所能承载的阈值,则需要水平分片来进一步处理。

水平分片

水平分片又称为横向拆分。 相对于垂直分片,它不再将数据根据业务逻辑分类,而是通过某个字段(或某几个字段),根据某种规则将数据分散至多个库或表中,每个分片仅包含数据的一部分。 例如:根据主键分片,偶数主键的记录放入 0 库(或表),奇数主键的记录放入 1 库(或表),如下图所示。

水平分片

水平分片从理论上突破了单机数据量处理的瓶颈,并且扩展相对自由,是分库分表的标准解决方案。

数据分片带来的问题

  • 数据路由:需要知道数据需要从哪个具体的数据库的分表中获取。
  • SQL 不兼容:分表导致表名称的修改,或者分页、排序、聚合、分组等操作的不正确处理。
  • 跨库事务:合理采用分表,可以在降低单表数据量的情况下,尽量使用本地事务,善于使用同库不同表可有效避免分布式事务带来的麻烦。 在不能避免跨库事务的场景,有些业务仍然需要保持事务的一致性。 而基于 XA 的分布式事务由于在并发度高的场景中性能无法满足需要,并未被互联网巨头大规模使用,他们大多采用最终一致性的柔性事务代替强一致事务。

ShardingSphere 内核剖析

ShardingSphere 的 3 个产品的数据分片主要流程是完全一致的。 核心由 SQL 解析 => 执行器优化 => SQL 路由 => SQL 改写 => SQL 执行 => 结果归并的流程组成。

img

  • QL 解析:分为词法解析和语法解析。 先通过词法解析器将 SQL 拆分为一个个不可再分的单词。再使用语法解析器对 SQL 进行理解,并最终提炼出解析上下文。 解析上下文包括表、选择项、排序项、分组项、聚合函数、分页信息、查询条件以及可能需要修改的占位符的标记。
  • 执行器优化:合并和优化分片条件,如 OR 等。
  • SQL 路由:根据解析上下文匹配用户配置的分片策略,并生成路由路径。目前支持分片路由和广播路由。
  • SQL 改写:将 SQL 改写为在真实数据库中可以正确执行的语句。SQL 改写分为正确性改写和优化改写。
  • SQL 执行:通过多线程执行器异步执行。
  • 结果归并:将多个执行结果集归并以便于通过统一的 JDBC 接口输出。结果归并包括流式归并、内存归并和使用装饰模式的追加归并这几种方式。

解析引擎

抽象语法树

解析过程分为词法解析语法解析。 词法解析器用于将 SQL 拆解为不可再分的原子符号,称为 Token。并根据不同数据库方言所提供的字典,将其归类为关键字,表达式,字面量和操作符。 再使用语法解析器将 SQL 转换为抽象语法树。

例如,以下 SQL:

1
SELECT id, name FROM t_user WHERE status = 'ACTIVE' AND age > 18

解析之后的为抽象语法树见下图。

SQL抽象语法树

为了便于理解,抽象语法树中的关键字的 Token 用绿色表示,变量的 Token 用红色表示,灰色表示需要进一步拆分。

最后,通过对抽象语法树的遍历去提炼分片所需的上下文,并标记有可能需要改写的位置。 供分片使用的解析上下文包含查询选择项(Select Items)、表信息(Table)、分片条件(Sharding Condition)、自增主键信息(Auto increment Primary Key)、排序信息(Order By)、分组信息(Group By)以及分页信息(Limit、Rownum、Top)。 SQL 的一次解析过程是不可逆的,一个个 Token 按 SQL 原本的顺序依次进行解析,性能很高。 考虑到各种数据库 SQL 方言的异同,在解析模块提供了各类数据库的 SQL 方言字典。

SQL 解析引擎

SQL 解析作为分库分表类产品的核心,其性能和兼容性是最重要的衡量指标。 ShardingSphere 的 SQL 解析器经历了 3 代产品的更新迭代。

第一代 SQL 解析器为了追求性能与快速实现,在 1.4.x 之前的版本使用 Druid 作为 SQL 解析器。经实际测试,它的性能远超其它解析器。

第二代 SQL 解析器从 1.5.x 版本开始,ShardingSphere 采用完全自研的 SQL 解析引擎。 由于目的不同,ShardingSphere 并不需要将 SQL 转为一颗完全的抽象语法树,也无需通过访问器模式进行二次遍历。它采用对 SQL 半理解的方式,仅提炼数据分片需要关注的上下文,因此 SQL 解析的性能和兼容性得到了进一步的提高。

第三代 SQL 解析器则从 3.0.x 版本开始,ShardingSphere 尝试使用 ANTLR 作为 SQL 解析的引擎,并计划根据 DDL -> TCL -> DAL –> DCL -> DML –>DQL 这个顺序,依次替换原有的解析引擎,目前仍处于替换迭代中。 使用 ANTLR 的原因是希望 ShardingSphere 的解析引擎能够更好的对 SQL 进行兼容。对于复杂的表达式、递归、子查询等语句,虽然 ShardingSphere 的分片核心并不关注,但是会影响对于 SQL 理解的友好度。 经过实例测试,ANTLR 解析 SQL 的性能比自研的 SQL 解析引擎慢 3-10 倍左右。为了弥补这一差距,ShardingSphere 将使用 PreparedStatement 的 SQL 解析的语法树放入缓存。 因此建议采用 PreparedStatement 这种 SQL 预编译的方式提升性能。

第三代 SQL 解析引擎的整体结构划分如下图所示。

解析引擎结构

参考资料

MongoDB CRUD

::: info 概述

CRUD 由英文单词 Create, Read, Update, Delete 的首字母组成,即增删改查

本文通过介绍基本的 MongoDB CRUD 方法,向读者呈现如何访问 MongoDB 数据。

:::

阅读全文 »