image

本文源地址：http://www.fullstackyang.com/...发魄，轉發(fā)請注明該地址或簡書地址妒貌，謝謝！

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

一、關于源碼中的彩蛋

CharMatcher類中羔砾，開頭部分有一張寵物小精靈“小火龍”的字符畫负间，就像本文的封面圖一樣偶妖，一開始不解為何要放一只“小火龍”在這里，后來看到其英文名Charmander才明白過來政溃。好吧趾访，諧音梗……略冷董虱。

二扼鞋、類的結構和關系

下圖是CharMatcher的類關系圖，圖中藍色的是abstract類愤诱，紅色的是final類

image

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

public abstract boolean matches(char c);

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

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

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

public CharMatcher negate() // 取反

public CharMatcher and(CharMatcher other) // 與

public CharMatcher or(CharMatcher other) // 或

...

如上圖所示影涉，CharMatcher類有很多的子類，一部分是直接繼承于父類规伐，一部分是繼承于FastMatcher蟹倾，另外還有繼承于Negated和RangeMatcher。子類通過實現(xiàn)matches方法或重寫其他父類的方法猖闪，從而提供了各種不同的具體操作鲜棠，如Is（判斷是否為某一個字符），Digit（判斷是否為數(shù)字字符）培慌，Ascii（判斷是否為ASCII字符）等豁陆。
再來說說其中一個比較重要的子類——FastMatcher，它和CharMatcher的主要區(qū)別在于吵护，F(xiàn)astMatcher取消了父類中相對復雜的precomputed方法盒音，其注釋寫道，這個方法可以得到一個處理速度更快的實例馅而，但是執(zhí)行該方法本身需要花費一定時間祥诽，所以只有在需要頻繁調(diào)用的情況下，這樣做才比較劃算瓮恭。
至于這個方法的奧秘在于雄坪，它使用BitSet作為存儲字符的數(shù)據(jù)結構，然后遍歷所有的字符（Character.MIN_VALUE~Character.MAX_VALUE）屯蹦，根據(jù)matches方法放入這個BitSet中维哈，最后根據(jù)這個BitSet中1的數(shù)量生成其他類型的CharMatcher實例绳姨，包括None，Is阔挠，IsEither飘庄，SmallCharMatcher（一個單獨的子類）以及BitSetMatcher，這樣就避免了頻繁調(diào)用過程中谒亦，（特別是復雜組合的情況）執(zhí)行不必要實例化操作竭宰，而是直接歸約到某一個類的實例上。
而上述那5個類正是繼承于FasterMatcher（或NamedFasterMatcher）份招。

三切揭、設計模式

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

• 靜態(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)工廠方法的好處，這點在《Effective Java》一書中有詳細的介紹

• 單例模式

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

private static final class Ascii extends NamedFastMatcher {

    static final Ascii INSTANCE = new Ascii();

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

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

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

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

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

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

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

四衅疙、算法分析

• collapseFrom方法，如代碼注釋所示鸳慈，把一個字符串中匹配到的(連續(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();
} 

事實上，CharMatcher里面的算法基本上都和這個差不多程度走芋。

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

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

static final class Whitespace extends NamedFastMatcher {

    static final String TABLE =
        "\u2002\u3000\r\u0085\u200A\u2005\u2000\u3000"
            + "\u2029\u000B\u3000\u2008\u2003\u205F\u3000\u1680"
            + "\u0009\u0020\u2006\u2001\u202F\u00A0\u000C\u2009"
            + "\u3000\u2004\u3000\u3000\u2028\n\u2007\u3000";
    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;
    }
}

這個算法本身很簡單帝簇，即TABLE字符串中是否存在同樣的字符c，巧妙的是它的定位方式靠益。
先說明Integer.numberOfLeadingZeros這個方法返回的是該int變量二進制開頭部分連續(xù)的零的個數(shù)丧肴。TABLE的長度為32，故SHIFT的值為27胧后，也就是說芋浮，通過字符c和某一個乘子的乘積（超出int范圍之后取低32位）向右移動27位得到的數(shù)值，即為TABLE的下標索引壳快，例如字符'\u2002'其值為8194纸巷，它和1682554634的乘積再右移27位得到0，而TABLE第0個字符就是'\u2002'眶痰，則判定相等瘤旨，字符'\u3000'的值為12288，應用相同算法得到26竖伯，TABLE第26個字符也是'\u3000'存哲，同樣判定相等。由此可以看出黔夭，1682554634這個魔數(shù)和TABLE是刻意設計成這樣的宏胯。但是源碼中沒有解釋如何生成，在GitHub上倒是也有人這么問過本姥，Guava owner回復說道：他們確實有一個生成器肩袍，但是由于一些依賴的原因，并沒有開源出來婚惫。其實如果不考慮性能氛赐，我們可以用最簡單的暴力法生成乘子和TABLE，代碼如下：

    @Test
    public void test() {
        // 去掉table中重復的字符
        String WHITE = "\u2002\r\u0085\u200A\u2005\u2000"
                + "\u2029\u000B\u2008\u2003\u205F\u1680"
                + "\u0009\u0020\u2006\u2001\u202F\u00A0\u000C\u2009"
                + "\u2004\u2028\n\u2007\u3000";

        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);//先用最后一個字符填充整個table
            boolean conflict = false;
            for (char c : chars) {
                int index = (i * c) >>> shift;
                //如果當前字符為填充字符先舷，則覆蓋填充字符艰管，否則跳過
                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的結果。當然蒋川，反推過程比較簡單粗暴牲芋，一定有更優(yōu)雅更高效的實現(xiàn)方式。不過這里想要表達的是，它本身是一個簡單的查找算法缸浦，通常的復雜度為O(logn)夕冲，這里巧妙通過映射函數(shù)，將字符映射為字符串下標索引裂逐，使得時間復雜度為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)時同樣也做了pos++的操作鸽照，本質(zhì)上還是O(n)的時間復雜度螺捐，算法思想是char數(shù)組的位移操作，每次匹配到一個字符時矮燎，spread就自增定血，其他情況則每個數(shù)組元素向前移動，具體來說诞外，spread的作用相當于對匹配到的字符進行計數(shù)澜沟，匹配到1個元素，pos指向的元素及其之后的元素向前移動1步以覆蓋掉上一輪命中的字符峡谊，匹配到2個元素茫虽，pos執(zhí)行的元素及其之后的元素向前移動2步，以覆蓋上一次移動留下的空位和上一輪命中的字符既们，依次類推濒析。最終利用String的構造函數(shù)（第二個參數(shù)是offset，即初始的偏移位置啥纸，第三個參數(shù)count号杏，即所需長度）返回正確的字符串。
做個對比斯棒，我們以Apache commons lang3中的StringUtils作為比較對象盾致，其對應的實現(xiàn)基于Matcher(java.util.regex)的replaceAll方法，亦即將匹配的字符替換為空字符串荣暮，整個遍歷的過程中重復調(diào)用了find()方法庭惜，該方法查找當前字符串中匹配的字符，它每次都需要從頭進行搜索穗酥，因此時間復雜度為O(n^2)护赊，這樣就比較費時了惠遏。

五、其他

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

• 數(shù)字字符

private static final String ZEROES =
        "0\u0660\u06f0\u07c0\u0966\u09e6\u0a66\u0ae6\u0b66\u0be6\u0c66\u0ce6\u0d66\u0de6"
            + "\u0e50\u0ed0\u0f20\u1040\u1090\u17e0\u1810\u1946\u19d0\u1a80\u1a90\u1b50\u1bb0"
            + "\u1c40\u1c50\ua620\ua8d0\ua900\ua9d0\ua9f0\uaa50\uabf0\uff10";

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

• 空白字符

static final String TABLE =
        "\u2002\u3000\r\u0085\u200A\u2005\u2000\u3000"
            + "\u2029\u000B\u3000\u2008\u2003\u205F\u3000\u1680"
            + "\u0009\u0020\u2006\u2001\u202F\u00A0\u000C\u2009"
            + "\u3000\u2004\u3000\u3000\u2028\n\u2007\u3000";

• 不可見字符

private static final String RANGE_STARTS =
        "\u0000\u007f\u00ad\u0600\u061c\u06dd\u070f\u08e2\u1680\u180e\u2000\u2028\u205f\u2066"
            + "\u3000\ud800\ufeff\ufff9";
private static final String RANGE_ENDS = // inclusive ends
        "\u0020\u00a0\u00ad\u0605\u061c\u06dd\u070f\u08e2\u1680\u180e\u200f\u202f\u2064\u206f"
            + "\u3000\uf8ff\ufeff\ufffb";

• 單字節(jié)長度字符

"\u0000\u05be\u05d0\u05f3\u0600\u0750\u0e00\u1e00\u2100\ufb50\ufe70\uff61"
"\u04f9\u05be\u05ea\u05f4\u06ff\u077f\u0e7f\u20af\u213a\ufdff\ufeff\uffdc"

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