检查空白字符有多难？

最近翻看一段源码时，我偶然发现了 Guava 里的这个方法。Guava 是 Google 出品的一个热门 Java 库。

从名字大概能猜到，这个方法用来判断给定字符是不是空白字符。可代码看起来远比一个简单的 c == ' ' 判断复杂得多。这勾起了我的好奇心，于是我顺着这条线索往下挖，想弄清楚这些复杂度究竟从何而来。如果你也好奇这段代码是怎么运作的，这篇文章就是为你写的。

空白字符到底是什么？

要审视一个判断字符是否为空白字符的函数，首先得定义清楚空白字符究竟是什么。SPACE (U+0020) 大概是最广为人知的空白字符，但它并不是唯一的一个。写过一段时间代码的人，多半还能再数出几个，比如不换行空格 NO-BREAK SPACE (U+00A0)、制表符 CHARACTER TABULATION (U+0009)、换行符 LINE FEED (U+000A)。

其实还有更多。Unicode 定义了 White_Space 属性，给出了 25 个字符的清单。下面就是这份清单，一字不差地照抄自 , ,,, , ,…, , , , , , , , , , , , , ,
,
, , ,　。

这些字符各有各的用途。比如 FIGURE SPACE (U+2007) 在表格里与一个数字等宽，而 THIN SPACE (U+2009) 和 HAIR SPACE (U+200A) 提供的间隙依次递减。NO-BREAK SPACE (U+00A0) 的宽度与普通空格相同，但在换行时会把前后的文本连在一起。

光看名字或字形，也未必能判断一个字符是否属于空白字符集合。比如 ZERO WIDTH SPACE (U+200B) 根本不是空白字符。尽管名字如此，它是一种格式字符，用来标示单词或换行的可能位置，却不产生可见的间隙。

这个集合里还有一些不那么显眼的成员。OGHAM SPACE MARK (U+1680) 实际上可以被渲染成一条可见的水平线。在带主干线的 Ogham 字体中，这个空格会在字母之间延续那条线（例如 ᚛ᚆᚓᚂᚂᚑ ᚒᚑᚏᚂᚇ᚜）；而在无主干的字体中，它就是空白的。所以，连“空白字符看起来必须是空的”这个假设也不总成立。

不同的运行时，不同的规则

只有大家对空白字符的定义达成共识，统一定义才有意义。可即便在同一个运行时里，不同的库对什么算空白也可能各执一词。

就拿前面提到的 NO-BREAK SPACE (U+00A0) 来说。它包含在 Unicode 的 White_Space 属性中，但 Java 明确把它排除在外，另外两个不换行空格也一样被排除。javadoc 倒是点明了，这个方法判断空白依据的是 Java 自己的规则，而不是我们前面看过的那个 Unicode 属性。

Character.isWhitespace(' ');      // true
Character.isWhitespace('\u00A0'); // false

那其他运行时呢？再看看两个更流行的运行时，Python 和 JavaScript，就会发现并不存在一份所有人都认可的权威字符清单。比如 Python 有一个方便的 str.isspace() 方法。和 Java 不同，它把 U+00A0 也算作空白字符。

那么 Python 是不是就遵循 Unicode 的 White_Space 属性呢？并不完全是。

"\u00A0".isspace()  # True
"\u0085".isspace()  # True
"\u001C".isspace()  # True
"\uFEFF".isspace()  # False

这里值得注意的是 FILE SEPARATOR (U+001C)。它是一个 ASCII 控制字符，最初用于分隔信息片段，而 Unicode 的 White_Space 属性并不包含它。所以 Python 认 29 个空白字符，而不是 Unicode 的 25 个。

JavaScript 又是另一套做法。它没有 Character.isWhitespace() 方法的对应物，但可以在正则表达式里用 \s 字符类：

/\s/.test("\u00A0");  // true
/\s/.test("\u0085");  // false
/\s/.test("\uFEFF");  // true

上面那个例外是 NEXT LINE (U+0085)。Unicode 明确把它列入 White_Space，Python 也接受它，但 JavaScript 不认。JavaScript 认的是 ZERO WIDTH NO-BREAK SPACE (U+FEFF)，而 Unicode 并不把它算进这个集合。

我没有再去看其他运行时，但直觉告诉我，不一致的地方不会只限于这三个。

没有什么是定死的

更麻烦的是，Unicode 并非一成不变，它一直在演进。这会影响空白的定义。例如 Unicode 6.3 把 MONGOLIAN VOWEL SEPARATOR (U+180E) 从空格分隔符重新归类为格式字符，去掉了它的 White_Space 属性。Unicode 的空白字符集合因此从 26 个变成了 25 个。对于追求向后兼容的运行时和库来说，这类变化是相当大的挑战，因为你总希望一门语言的标准库尽可能稳定。

快速检查空白

假设我们终于就想要检查的字符集合达成了一致，也就是当前 Unicode 的空白字符集合。最直白的实现方式是遍历字符列表，逐个检查是否有匹配项。这能行，但显然不是最高效的做法。

文章开头看到的那段 Guava 实现，做的就是实现一个完美哈希函数，保证对已知集合中的字符不会产生哈希冲突。

static final String TABLE = "\u2002...";

@Override
public boolean matches(char c) {
    int slot = (1682554634 * c) >>> 27;
    return TABLE.charAt(slot) == c;
}

上面的 TABLE 是一个 32 字符的字符串，本质上是一张哈希表，把每个索引（键）映射到一个字符（值）。它包含全部 25 个 Unicode 空白字符，其余位置用一些重复字符填满。

这里最有意思的是索引的计算。乘法 1682554634 * c 得到一个 32 位整数，>>> 27 再把它右移 27 位，取出最高的 5 位，一个落在 [0, 32) 范围内的数，正好用来查表。当然，可能的字符比表项多，所以最后还需要 == c 检查一下，确认查到的字符正是我们要找的那个。

下面看看这张表是怎么填充的。

神奇数字 1682554634 看上去确实很神奇，我也说不清它是怎么选出来的（如果你知道答案，欢迎分享）。但它并不是唯一可用的乘数，只要跑一遍简单的暴力搜索，就能找出所有合适的选项。

static final char[] ALL_CHARS = (
        "\u2002\u3000\r\u0085"
        + "\u200A\u2005\u2000"
        + "\u2029\u000B\u2008"
        + "\u2003\u205F\u1680"
        + "\u0009\u0020\u2006"
        + "\u2001\u202F\u00A0"
        + "\u000C\u2009\u2004"
        + "\u2028\n\u2007"
).toCharArray();

public static void main(String[] a) {
    var slots = new BitSet(32);
    outer:
    for (int mul = 1; mul != 0; mul++) {
        slots.clear();
        for (char c : ALL_CHARS) {
            int index = (mul * c) >>> 27;
            if (slots.get(index)) {
                continue outer;
            }
            slots.set(index);
        }
        System.out.println(mul);
    }
}

有意思的是，愿意深挖的人可以翻一翻 git 历史，看看 Guava 是怎么一步步走到这个实现的。它最初是一个更简单的匹配器，后来换成了 mod-79 版本，这个版本对 Unicode 字符集有一个有趣的观察，但缺点是要做一次除法运算，再往后才换成了完美哈希函数。

如果你对完美哈希的其他应用感兴趣，说来也巧，就在我写这篇文章的时候，Daniel Lemire 发了一篇博客，主题正好相同，里面举了用完美哈希检查 HTTP 方法的例子。

结语

第一次在 Guava 里看到这段检查空白字符的代码时，它勾起了我的好奇心，结果我因此学到了不少 Unicode 的知识，也见识了完美哈希函数一个有意思的用法，这种东西在实际代码里并不常见。

希望这篇文章也能让你学到点有趣的东西。如果你也遇到了什么勾起好奇心的事，不妨写篇博客分享出来。我确实觉得这类文章在 AI 优先的当下越来越少了，毕竟现在很少有人有理由去掀开一个像 isWhitespace 这样简单的函数的盖子看看里面。