摘要：子類通過實(shí)現(xiàn)方法或重寫其他父類的方法，從而提供了各種不同的具體操作，如判斷是否為某一個(gè)字符，判斷是否為數(shù)字字符，判斷是否為字符等。

本文源地址：http://www.fullstackyang.com/...，轉(zhuǎn)發(fā)請注明該地址或segmentfault地址，謝謝！

最近遇到了一些字符匹配的需求，進(jìn)而仔細(xì)地看了CharMatcher的源碼，發(fā)現(xiàn)還是有點(diǎn)東西值得回味，例如它為我們提供了如何在多種字符類型場景下提高靈活性從而滿足不同匹配需求的優(yōu)秀示范。下面就對CharMatcher類的結(jié)構(gòu)，設(shè)計(jì)模式，以及幾個(gè)算法做一些粗淺的分析。

CharMatcher類中，開頭部分有一張寵物小精靈“小火龍”的字符畫，就像本文的封面圖一樣，一開始不解為何要放一只“小火龍”在這里，后來看到其英文名Charmander才明白過來。好吧，諧音?！岳?。

下圖是CharMatcher的類關(guān)系圖，圖中藍(lán)色的是abstract類，紅色的是final類

首先CharMatcher修飾為abstract，其中只有一個(gè)abstract方法matches，即判斷給定字符是否匹配，以及一些其他的常用操作（它們的功能從方法名可以得知，這里就不一一介紹了，下文會選其中的一些做分析），此外還有三個(gè)用于組合的方法：negate、or、and。

public abstract boolean matches(char c);

public int indexIn(CharSequence sequence) // 查找匹配字符首次出現(xiàn)的索引位置

public int countIn(CharSequence sequence) // 對匹配的字符計(jì)數(shù)

public String retainFrom(CharSequence sequence) // 抽取匹配的字符

public CharMatcher negate() // 取反

public CharMatcher and(CharMatcher other) // 與

public CharMatcher or(CharMatcher other) // 或

...

如上圖所示，CharMatcher類有很多的子類，一部分是直接繼承于父類，一部分是繼承于FastMatcher，另外還有繼承于Negated和RangeMatcher。子類通過實(shí)現(xiàn)matches方法或重寫其他父類的方法，從而提供了各種不同的具體操作，如Is（判斷是否為某一個(gè)字符），Digit（判斷是否為數(shù)字字符），Ascii（判斷是否為ASCII字符）等。
再來說說其中一個(gè)比較重要的子類——FastMatcher，它和CharMatcher的主要區(qū)別在于，F(xiàn)astMatcher取消了父類中相對復(fù)雜的precomputed方法，其注釋寫道，這個(gè)方法可以得到一個(gè)處理速度更快的實(shí)例，但是執(zhí)行該方法本身需要花費(fèi)一定時(shí)間，所以只有在需要頻繁調(diào)用的情況下，這樣做才比較劃算。
至于這個(gè)方法的奧秘在于，它使用BitSet作為存儲字符的數(shù)據(jù)結(jié)構(gòu)，然后遍歷所有的字符（Character.MIN_VALUE~Character.MAX_VALUE），根據(jù)matches方法放入這個(gè)BitSet中，最后根據(jù)這個(gè)BitSet中1的數(shù)量生成其他類型的CharMatcher實(shí)例，包括None，Is，IsEither，SmallCharMatcher（一個(gè)多帶帶的子類）以及BitSetMatcher，這樣就避免了頻繁調(diào)用過程中，（特別是復(fù)雜組合的情況）執(zhí)行不必要實(shí)例化操作，而是直接歸約到某一個(gè)類的實(shí)例上。
而上述那5個(gè)類正是繼承于FasterMatcher（或NamedFasterMatcher）。

上一節(jié)說到CharMatcher提供很多子類，為了較好地管理和使用這些類，CharMatcher對外提供了基于內(nèi)部類的靜態(tài)工廠方法或者單例模式來獲得某個(gè)實(shí)例，舉例來說：

靜態(tài)工廠方法

public static CharMatcher is(final char match) {
    return new Is(match);
}

private static final class Is extends FastMatcher {
    
    private final char match;

    Is(char match) {
      this.match = match;
    }
    ...
  }

使用靜態(tài)工廠方法的好處，這點(diǎn)在《Effective Java》一書中有詳細(xì)的介紹

單例模式

public static CharMatcher ascii() {
    return Ascii.INSTANCE;
}

private static final class Ascii extends NamedFastMatcher {

    static final Ascii INSTANCE = new Ascii();

    Ascii() {
      super("CharMatcher.ascii()");
    }
    ...
}

這樣我們就可以很方便地獲得一個(gè)實(shí)例，并對相應(yīng)的字符類型做處理，比如抽取字符串中所有的數(shù)字

CharMatcher.inRange("0", "9").retainFrom("abc12d34ef");
// 當(dāng)然也可以用Digit類，不過最近的版本已經(jīng)被標(biāo)記為Deprecated
// 區(qū)別在于Digit類處理了字符0到9的各種unicode碼，不過大多數(shù)情況還是處理ASCII數(shù)字，所以建議使用inRange
CharMatcher.digit().retainFrom("abc12d34ef")；
// 1234

當(dāng)然也可以通過negate/or/and產(chǎn)生一些復(fù)雜的組合:

CharMatcher.inRange("0","9").or(CharMatcher.is("d")).retainFrom("abc12d34ef");
// 12d34

另外還有一個(gè)ForPredicate的子類，它接收Predicate對象作為參數(shù)，然后用Predicate的apply方法來實(shí)現(xiàn)matches方法，這樣就用lamda表達(dá)式創(chuàng)建一些實(shí)例了，例如：

CharMatcher.inRange("0", "9").or(CharMatcher.is("d"))
                .or(CharMatcher.forPredicate(c -> c <= "b" || c > "e")).retainFrom("abc12d34ef");
// ab12d34f

collapseFrom方法，如代碼注釋所示，把一個(gè)字符串中匹配到的(連續(xù))部分替換為給定的字符，

//CharMatcher.anyOf("eko").collapseFrom("bookkeeper", "-") returns "b-p-r"
public String collapseFrom(CharSequence sequence, char replacement) {
    // This implementation avoids unnecessary allocation.
    int len = sequence.length();
    for (int i = 0; i < len; i++) {
      char c = sequence.charAt(i);
      if (matches(c)) {
        if (c == replacement && (i == len - 1 || !matches(sequence.charAt(i + 1)))) {
          // a no-op replacement
          i++;
        } else {
          StringBuilder builder = new StringBuilder(len).append(sequence, 0, i).append(replacement);
          return finishCollapseFrom(sequence, i + 1, len, replacement, builder, true);
        }
      }
    }
    // no replacement needed
    return sequence.toString();
}
  
private String finishCollapseFrom(
      CharSequence sequence,
      int start,
      int end,
      char replacement,
      StringBuilder builder,
      boolean inMatchingGroup) {
    for (int i = start; i < end; i++) {
      char c = sequence.charAt(i);
      if (matches(c)) {
        if (!inMatchingGroup) {
          builder.append(replacement);
          inMatchingGroup = true;
        }
      } else {
        builder.append(c);
        inMatchingGroup = false;
      }
    }
    return builder.toString();
} 

事實(shí)上，CharMatcher里面的算法基本上都和這個(gè)差不多程度。

正如注釋部分所述，這個(gè)算法沒有分配不必要的空間。遍歷過程中當(dāng)發(fā)現(xiàn)當(dāng)前字符滿足匹配條件，這時(shí)再做一次判斷，如果當(dāng)前字符本身就是所需要替換的字符replacement，那么這種情況是不需要進(jìn)行替換操作（感覺可以直接用一個(gè)if(c != replacement)換掉else，并不需要i++的操作），否則將i之前的字符拼上replacement形成一個(gè)“半成品”傳入finishCollapseFrom，在該方法中利用了一個(gè)布爾值inMatchingGroup來控制是否需要拼接replacement，當(dāng)發(fā)現(xiàn)滿足匹配條件時(shí)，再檢查inMatchingGroup是否為false，它表示上一輪拼接的不是replacement，以保證返回的結(jié)果中不會出現(xiàn)兩個(gè)以上連續(xù)的replacement。

Whitespace.matches 即判斷該字符是否為空白字符，包括空格，換行等

static final class Whitespace extends NamedFastMatcher {

    static final String TABLE =
        "u2002u3000
u0085u200Au2005u2000u3000"
            + "u2029u000Bu3000u2008u2003u205Fu3000u1680"
            + "u0009u0020u2006u2001u202Fu00A0u000Cu2009"
            + "u3000u2004u3000u3000u2028
u2007u3000";
    static final int MULTIPLIER = 1682554634;
    static final int SHIFT = Integer.numberOfLeadingZeros(TABLE.length() - 1);

    static final Whitespace INSTANCE = new Whitespace();

    @Override
    public boolean matches(char c) {
      return TABLE.charAt((MULTIPLIER * c) >>> SHIFT) == c;
    }
}

這個(gè)算法本身很簡單，即TABLE字符串中是否存在同樣的字符c，巧妙的是它的定位方式。
先說明Integer.numberOfLeadingZeros這個(gè)方法返回的是該int變量二進(jìn)制開頭部分連續(xù)的零的個(gè)數(shù)。TABLE的長度為32，故SHIFT的值為27，也就是說，通過字符c和某一個(gè)乘子的乘積（超出int范圍之后取低32位）向右移動27位得到的數(shù)值，即為TABLE的下標(biāo)索引，例如字符"u2002"其值為8194，它和1682554634的乘積再右移27位得到0，而TABLE第0個(gè)字符就是"u2002"，則判定相等，字符"u3000"的值為12288，應(yīng)用相同算法得到26，TABLE第26個(gè)字符也是"u3000"，同樣判定相等。由此可以看出，1682554634這個(gè)魔數(shù)和TABLE是刻意設(shè)計(jì)成這樣的。但是源碼中沒有解釋如何生成，在GitHub上倒是也有人這么問過，Guava owner回復(fù)說道：他們確實(shí)有一個(gè)生成器，但是由于一些依賴的原因，并沒有開源出來。其實(shí)如果不考慮性能，我們可以用最簡單的暴力法生成乘子和TABLE，代碼如下：

    @Test
    public void test() {
        // 去掉table中重復(fù)的字符
        String WHITE = "u2002
u0085u200Au2005u2000"
                + "u2029u000Bu2008u2003u205Fu1680"
                + "u0009u0020u2006u2001u202Fu00A0u000Cu2009"
                + "u2004u2028
u2007u3000";

        char[] chars = WHITE.toCharArray();
        char filler = chars[chars.length - 1];
        char[] table = new char[32];

        int shift = Integer.numberOfLeadingZeros(WHITE.length());

        for (int i = 0; i <= Integer.MAX_VALUE; i++) {
            Arrays.fill(table, filler);//先用最后一個(gè)字符填充整個(gè)table
            boolean conflict = false;
            for (char c : chars) {
                int index = (i * c) >>> shift;
                //如果當(dāng)前字符為填充字符，則覆蓋填充字符，否則跳過
                if (table[index] != filler) { 
                    conflict = true;
                    continue;
                }
                table[index] = c;
            }
            if (conflict)
                continue;
            System.out.println("MULTIPLIER: " + i);
            System.out.println("TABLE:" + new String(table));
        }
    }

上面可以得到多種MULTIPLIER和TABLE的結(jié)果。當(dāng)然，反推過程比較簡單粗暴，一定有更優(yōu)雅更高效的實(shí)現(xiàn)方式。不過這里想要表達(dá)的是，它本身是一個(gè)簡單的查找算法，通常的復(fù)雜度為O(logn)，這里巧妙通過映射函數(shù)，將字符映射為字符串下標(biāo)索引，使得時(shí)間復(fù)雜度為O(1)，不得不佩服Guava開發(fā)者們追求極致的精神。

removeFrom方法，即在給定字符串中，刪除其匹配的部分

// CharMatcher.is("a").removeFrom("bazaar") returns "bzr"
public String removeFrom(CharSequence sequence) {
    String string = sequence.toString();
    int pos = indexIn(string);
    if (pos == -1) {
      return string;
    }

    char[] chars = string.toCharArray();
    int spread = 1;

    // This unusual loop comes from extensive benchmarking
    OUT:
    while (true) {
      pos++;
      while (true) {
        if (pos == chars.length) {
          break OUT;
        }
        if (matches(chars[pos])) {
          break;
        }
        chars[pos - spread] = chars[pos];
        pos++;
      }
      spread++;
    }
    return new String(chars, 0, pos - spread);
  }

比較詭異的是，它使用了兩層while循環(huán)，以及break [lable]的語法（這種用法并不多見，可以理解為goto語句的改良形式，可以方便地跳出多層循環(huán)）,不過在內(nèi)層循環(huán)時(shí)同樣也做了pos++的操作，本質(zhì)上還是O(n)的時(shí)間復(fù)雜度，算法思想是char數(shù)組的位移操作，每次匹配到一個(gè)字符時(shí)，spread就自增，其他情況則每個(gè)數(shù)組元素向前移動，具體來說，spread的作用相當(dāng)于對匹配到的字符進(jìn)行計(jì)數(shù)，匹配到1個(gè)元素，pos指向的元素及其之后的元素向前移動1步以覆蓋掉上一輪命中的字符，匹配到2個(gè)元素，pos執(zhí)行的元素及其之后的元素向前移動2步，以覆蓋上一次移動留下的空位和上一輪命中的字符，依次類推。最終利用String的構(gòu)造函數(shù)（第二個(gè)參數(shù)是offset，即初始的偏移位置，第三個(gè)參數(shù)count，即所需長度）返回正確的字符串。
做個(gè)對比，我們以Apache commons lang3中的StringUtils作為比較對象，其對應(yīng)的實(shí)現(xiàn)基于Matcher(java.util.regex)的replaceAll方法，亦即將匹配的字符替換為空字符串，整個(gè)遍歷的過程中重復(fù)調(diào)用了find()方法，該方法查找當(dāng)前字符串中匹配的字符，它每次都需要從頭進(jìn)行搜索，因此時(shí)間復(fù)雜度為O(n^2)，這樣就比較費(fèi)時(shí)了。

在CharMatcher羅列多種字符的不同Unicode碼，如果你在其他的工作場景下需要用的這些unicode，可以參考一下CharMatcher。

數(shù)字字符

private static final String ZEROES =
        "0u0660u06f0u07c0u0966u09e6u0a66u0ae6u0b66u0be6u0c66u0ce6u0d66u0de6"
            + "u0e50u0ed0u0f20u1040u1090u17e0u1810u1946u19d0u1a80u1a90u1b50u1bb0"
            + "u1c40u1c50ua620ua8d0ua900ua9d0ua9f0uaa50uabf0uff10";

如果要獲得其他數(shù)字的unicode，就直接對應(yīng)加上對應(yīng)的數(shù)值

空白字符

static final String TABLE =
        "u2002u3000
u0085u200Au2005u2000u3000"
            + "u2029u000Bu3000u2008u2003u205Fu3000u1680"
            + "u0009u0020u2006u2001u202Fu00A0u000Cu2009"
            + "u3000u2004u3000u3000u2028
u2007u3000";

不可見字符

private static final String RANGE_STARTS =
        "u0000u007fu00adu0600u061cu06ddu070fu08e2u1680u180eu2000u2028u205fu2066"
            + "u3000ud800ufeffufff9";
private static final String RANGE_ENDS = // inclusive ends
        "u0020u00a0u00adu0605u061cu06ddu070fu08e2u1680u180eu200fu202fu2064u206f"
            + "u3000uf8ffufeffufffb";

單字節(jié)長度字符

"u0000u05beu05d0u05f3u0600u0750u0e00u1e00u2100ufb50ufe70uff61"
"u04f9u05beu05eau05f4u06ffu077fu0e7fu20afu213aufdffufeffuffdc"

中文字符就是雙字節(jié)長度