Java 字符串查找性能大比拼：String.indexOf vs KMP vs BF 算法實測分析

測試背景

在研究 KMP 算法時，對比 JDK 原生 String.indexOf()、暴力匹配（BF）、KMP 三種字符串查找算法的實際性能表現。

測試代碼核心邏輯

public class StringSearchBenchmark {
    // 測試參數
    private static final int TEXT_LENGTH = 8_000_000;  // 主串 800 萬字符
    private static final int PATTERN_LENGTH = 11;       // 模式串 11 字符
    private static final int CHAR_SET_SIZE = 4;         // 字符集大小 (A-Z, a-z, 0-9)
    private static final int ITERATIONS = 50;           // 重複 50 次取平均
    
    // 三種算法
    // 1. JDK 原生
    int indexString = text.indexOf(pattern);
    
    // 2. 暴力匹配 BF (Brute Force)
    int indexBF = bfIndexOf(text, pattern);
    
    // 3. KMP 算法
    int indexKMP = kmpIndexOf(text.toCharArray(), pattern.toCharArray());

實測結果 (50 次迭代)

深度分析：為什麼 JDK 原生最快？

1. 原生優化：String.indexOf() 內部使用 indexOfSupplementary() / indexOfLatin1()，針對 Latin1/UTF-16 編碼專門優化
2. 雙向掃描：現代 JDK 實現包含 Sunday/Boyer-Moore 等啟發式優化，實際接近 O(n/m) 平均複雜度
3. JIT 編譯：熱點代碼編譯為機器碼，內聯優化，消除方法調用開銷
4. 數據局部性：連續內存訪問，CPU 緩存友好

KMP 算法 Java 實現要點

// next 數組構建 (失敗函數)
public static int[] buildNext(char[] pattern) {
    int[] next = new int[pattern.length];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < pattern.length - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++; j++;
            next[i] = (pattern[i] != pattern[j]) ? j : next[j];
        } else {
            j = next[j];
        }
    }
    return next;
}

// KMP 匹配
public static int kmpSearch(char[] text, char[] pattern) {
    int[] next = buildNext(pattern);
    int i = 0, j = 0;
    while (i < text.length && j < pattern.length) {
        if (j == -1 || text[i] == pattern[j]) {
            i++; j++;
        } else {
            j = next[j];
        }
    }
    return (j == pattern.length) ? i - j : -1;
}

BF 算法優化版

public static int bfSearch(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text.charAt(i + j) == pattern.charAt(j)) j++;
        if (j == m) return i;
    }
    return -1;
}

性能優化建議

測試代碼優化提示

• 預熱 JVM：正式測試前運行 10k+ 迭代觸發 JIT 編譯
• 隔離 GC 干擾：-Xms4g -Xmx4g 固定堆，或使用 JMH 基準測試框架
• 統計分布：運行 100+ 次取中位數/百分位，而非平均值
• 固定種子：new Random(42) 保證數據可復現

結論：日常開發直接用 String.indexOf()，它是經過三十年優化的工業級實現。手寫 KMP/BF 僅用於面試、教學或極特殊場景（如流式匹配、嵌入式無標準庫環境）。