Programming

String

String 对象是 Java 语言中最重要的数据类型，往往在内存中占用最大。合理地使用 String，可以提升系统的整体性能。请先了解 String 类型。

显式使用 StringBuilder

String s1 = "ab" + "cd" + "ef";

// 字节码
// LDC "abcdef"

String s2 = "abc";
for(int i=0; i<1000; i++) {
    s2 = s2 + i;
}

// 反编译
String str = "abc";
for(int i=0; i<1000; i++) {
    str = (new StringBuilder(String.valueOf(str))).append(i).toString();
}

如上面代码，虽然编译器会优化，但是每次循环都创建一个 StringBuilder 对象，会降低性能，所以建议显式使用 StringBuilder 对象。

String.intern()

调用 intern() 方法后，堆内原有的 String 对象就没有引用了，可以被 GC。

String str1= "abc";
String str2= new String("abc");
String str3= str2.intern();
assertSame(str1==str2);
assertSame(str2==str3);
assertSame(str1==str3)

// false false true

要注意过度使用 intern 也会使常量池太大，遍历的时间复杂度增加。所以要根据需求权衡。

String.split

split 使用正则表达式，但正则的性能不稳定，使用不恰当会引起回溯问题，导致 CPU 居高不下。

若 indexOf 方法能够满足需求，尽量使用它。

split 有两种情况不会使用正则：

传入参数长度为 1，且不包含 .$|()[{^?*+\\；
传入参数长度为 2，第一个字符是 \，且第二个字符不是 ASCII 数字或字母。

正则表达式

正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的字符串，很多语言都实现了它。

正则表达式由四种元素组成，详见 PCRE 表达式全集：

普通字符：字母[a-zA-Z]、数字[0-9]、下划线[_]、标点等
标准字符：能够与多种普通字符匹配的简单表达式，如 \d（数字）、\w（包括下划线的单词字符）、\s（空白字符）等。
限定字符：用于表示数量，*、+、?、{n} 等。
定位字符：符合某种条件的位置，$、^ 等。

引擎

给定正则表达式后，程序对表达式语法分析，建立语法分析数，再根据这个分析树结合正则表达式引擎生成执行程序（又称状态机、状态自动机），用于匹配字符。

正则表达式引擎有两种：

DFA 自动机：Deterministic Final Automata，确定有限状态自动机，匹配时间复杂度 O(n)
NFA 自动机：Non deterministic Final Automaton，非确定有限状态自动机，匹配时间复杂度 O(ns)，s 为状态数；优点是支持功能更多，如捕获 group、环视、占有有限量词等，所以编程语言里面一般用 NFA 实现。

回溯问题

假设字符串为 ”abbc“，正则表达式为 "ab{1,3}c"，则匹配过程如下图：

NFA 自动机默认情况时贪婪模式，即匹配尽量多的内容，在第 2 步匹配到一个 b 后，会继续尽量匹配到 3 个 b。所以第 4 步，想要匹配第三个 b 时匹配不到，就会发送回溯，已经读取到 c 会被回退，指针重新指向第三个字符 b，然后再匹配 c。

贪婪模式（Greedy）

如果单独使用 +、?、*、{min,max}，则会尽量匹配多的内容。

懒惰模式（Reluctant）

NFA 会尽量匹配少的内容。通过增加 ? 开启。

独占模式（Possessive）

与贪婪模式一致，会尽量匹配多的内容，但是若匹配失败，不会回溯，直接匹配结束。通过增加 + 开启。

案例

public static void main(String[] args) {
    String text = "abbbc";
    String reg1 = "ab{1,3}bbc";
    String reg2 = "ab{1,3}?bbc";
    String reg3 = "ab{1,3}+bbc";
    System.out.println(String.format("文本: \"%s\"", text));
    System.out.println(String.format("贪婪模式: \"%s\"", reg1));
    System.out.println(String.format("懒惰模式: \"%s\"", reg2));
    System.out.println(String.format("独占模式: \"%s\"\n", reg3));
    print(text, reg1, reg2);
    Pattern p = Pattern.compile(reg3);
    Matcher matcher = p.matcher(text);
    System.out.println(String.format("\n独占模式匹配结果：%b", matcher.find()));
}

private static void print(String text, String regex1, String regex2) {
    System.out.println("regex1     regex2   percentage");
    Pattern p1 = Pattern.compile(regex1);
    Pattern p2 = Pattern.compile(regex2);
    for (int i = 0; i < 10; i++) {
        long t1 = cost(text, p1);
        long t2 = cost(text, p2);
        if (i >= 1) {
            System.out.println(String.format("%4d%10d%10.2f", t1, t2, t2 * 1.0 / t1));
        }
    }
}

private static long cost(String text, Pattern p) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++) {
        Matcher matcher = p.matcher(text);
        boolean b = matcher.find();
    }
    return System.currentTimeMillis() - start;
}

输出结果：

文本: "abbbc"
贪婪模式: "ab{1,3}bbc"
懒惰模式: "ab{1,3}?bbc"
独占模式: "ab{1,3}+bbc"

regex1     regex2   percentage
 873       561      0.64
 851       587      0.69
 876       624      0.71
 850       619      0.73
 857       615      0.72
 863       623      0.72
 865       624      0.72
 858       608      0.71
 853       611      0.72

独占模式匹配结果：false

优化

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

减少分支选择

"(x|y|z)" 会降低性能，可以做如下优化：

常用的放在前面，就可以较快被匹配到。
"(abcs|abef)" 改成 "ab(cd|ef)"。
"(x|y|z)" 可以改成调用三次 String.indexOf() 方法。

减少捕获组

正则表达式中，子表达式匹配的内容保存到以数组编号或显示命名的数组中，方便后面引用，叫做捕获组，一般 () 表示一个捕获组，捕获组可以嵌套。

可以用 (?:exp) 来表示不用捕获组。

减少捕获组可以提高性能。

List

List 主要有 ArrayList 和 LinkedList 两个实现类。`

初始化，ArrayList 最好指定容量，避免扩容复制。
新增元素，不考虑扩容时：
- 头部增加： LinkedList 效率较高，因为 ArrayList 需要移动大部分数据。
- 中间增加：差不多，因为 ArrayList 需要移动大约一半数据，LinkedList 找到中间位置需要遍历大约一半的数据。
- 尾部增加：ArrayList 效率较高，因为 LinkedList 的指针变换比较耗时。
删除元素：
- 头部删除：LinkedList 效率较高。
- 中间删除：差不多。
- 尾部删除：ArrayList 效率较高。
遍历元素：
- for(;;) 遍历：ArrayList 效率高，因为 LinkedList 每次都要找到位置。
- 迭代器遍历：差不多。

使用迭代器遍历时，若需要删除元素，应该使用 Iterator.remove()，而不是 List.remove()，原因详见迭代器（源码分析）。

Stream

Stream 是 Java 8 新增的 Api。

若循环次数较少，常规的迭代性能较好。
单核 CPU，常规迭代性能较好。
循环次数较多，多核 CPU，Stream 并行性能优势明显。

所以使用 Stream 未必可以使系统性能更佳，需要结合使用场景，合理地使用 Stream。

HashMap

HashMap 在 Java 1.8 中做了较大的优化。可根据场景合理设置初始容量和加载因子两个参数：

若查询较为频繁，可以减小加载因子。
若内存利用率需要较高，可以增大加载因子。

设计合理的 hashCode 方法，降低 hash 冲突。

若预知存储数据量，提前设置好初始容量（预知数据量 / 加载因子），可以减少 resize 操作。

I/O

Java 有普通 I/O 实现，这种实现需要把内核空间的内存与用户空间的内存相互复制，见 Unix IO 模型，而且是阻塞的。JDK 1.4 发布了 NIO（new I/O），优化了内存复制与阻塞问题。JDK 1.7 发布了 NIO2，从操作系统层面实现了异步 I/O。

NIO 有两个重要的组件 Channel 和 Buffer，可以使用它们优化读写。
NIO 还提供了 DirectBuffer，可以优化内存复制。
使用多路复用模型，即 Selector。

NIO

选择合适的网络 IO 模型，如 Selector 模式。
采用零拷贝技术，Linux 的 mmap可以创建一个用户空间和内和空间共享的内存块，epoll 就是使用了 mmap 减少了内存拷贝。在 Java 中则使用 DirectBuffer。
线程模型优化，如 Reactor 模型，Redis 就采用了此模型：
- 事件接收器 Acceptor。
- 事件分离器 Reactor
- 事件处理器 Handler。