Java 字符串查找性能对比：indexOf 与 KMP/BF 算法实测

背景与测试目标

在进行算法研究（如 KMP 算法）时，为了量化评估执行时间和性能表现，需要搭建基准测试环境。常见的做法是在内存中构造海量随机字符串，对比不同查找算法的效率。

测试原理与代码实现

本次测试主要围绕以下三个核心维度展开： 1. JDK 原生方法：直接调用 String.indexOf()。 2. BF 算法 (Brute Force)：经典的暴力匹配逻辑，包含回溯操作。 3. KMP 算法：利用 next 数组减少回溯次数的高效匹配方案。

完整的测试辅助类及核心逻辑代码如下：

package com.test.test.kmp;

import java.util.Random;

public class KMPTest {

	public static void main(String[] args) {
		test();
	}
	
	public static void test() {
		// 定义测试参数：主串长度800万，子串长度11，字符集类型4（实际代码为数字+大小写混合）
		int allLen = 8000000;
		int subLen = 11;
		int charLen = 4;
		String cl = buildString(charLen);
		int times = 50;
		// 执行匹配测试
		testMatch(allLen, subLen, cl, times);
	}
	
	public static void testMatch(int allLen, int subLen, String cl, int times){
		// 记录各项耗时累计
		int allBF = 0;
		int allString = 0;
		int allKMP = 0;
		int allGC = 0; // 垃圾回收带来的系统暂停时间
		int allbuild = 0; // 字符串构建耗时
		int alltoArray = 0; // toCharArray转换耗时
		
		long start = System.currentTimeMillis();
		System.out.println("--------------------------");
		
		for (int i = 0; i < times; i++) {
			// 1. 消耗测试：字符串构建
			long buildStart = System.currentTimeMillis();
			String sub = buildString(subLen, cl);
			String all = buildString(allLen, sub) +sub;
			long buildEnd = System.currentTimeMillis();
			allbuild += (buildEnd - buildStart);
			
			// 2. 消耗测试：转换为 char 数组
			long toArrayStart = System.currentTimeMillis();
			char[] allArray = all.toCharArray();
			char[] subArray = sub.toCharArray();
			long toArrayEnd = System.currentTimeMillis();
			alltoArray += (toArrayEnd - toArrayStart);
			
			// --- 执行 BF 算法 ---
			long startBF = System.currentTimeMillis();
			int indexBF = bfIndexOf(all, sub);
			long endBF = System.currentTimeMillis();
			int timeoutBF = (int)(endBF - startBF);
			allBF += timeoutBF;
			System.gc();
			allGC += (int)(System.currentTimeMillis() - endBF);
	
			// --- 执行 JDK indexOf 方法 ---
			long startString = System.currentTimeMillis();
			int indexString = stringIndexOf(all, sub);
			long endString = System.currentTimeMillis();
			int timeoutString = (int)(endString - startString);
			allString += timeoutString;
			System.gc();
			allGC += (int)(System.currentTimeMillis() - endString);
			
			// --- 执行 KMP 算法 ---
			long startKMP = System.currentTimeMillis();
			int indexKMP = KMP_Index(allArray, subArray);
			long endKMP = System.currentTimeMillis();
			int timeoutKMP = (int)(endKMP - startKMP);
			allKMP += timeoutKMP;
			System.gc();
			allGC += (int)(System.currentTimeMillis() - endKMP);
			
			// 结果校验
			if(indexBF == indexString && indexKMP == indexString){
				// 一致继续
			} else {
				throw new RuntimeException("对比出错.");
			}
			
			// 阶段性输出中间状态
			if(i % 20 == 10){
				printLog(i, allBF, allString, allKMP, allbuild, alltoArray, allGC, start);
			}
		}
		
		// 最终汇总输出
		printFinalLog(times, allBF, allString, allKMP, allbuild, alltoArray, allGC, start);
	}
	
	// 辅助打印方法（略）
	
	public static String buildString(int len, String sub){
		final int TYPE_NUMBER = 0;
		final int TYPE_LOWERCASE = 1;
		final int TYPE_UPPERCASE = 2;
		long seed = System.nanoTime();
		Random random = new Random(seed);
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < len; i++) {
			int type = random.nextInt(3);
			int cvalue = 0;
			if(TYPE_NUMBER == type){
				cvalue = '0' + random.nextInt(10);
			} else if(TYPE_LOWERCASE == type){
				cvalue = 'a' + random.nextInt(26);
			} else if(TYPE_UPPERCASE == type){
				cvalue = 'A' + random.nextInt(26);
			}
			char c = (char)cvalue;
			if(null != sub && sub.length() > 1){
				int index = random.nextInt(sub.length());
				c = sub.charAt(index);
			}
			builder.append(c);
		}
		return builder.toString();
	}
	
	public static int stringIndexOf(String all, String sub){
		if(null == all || null== sub) return -1;
		return all.indexOf(sub);
	}
	
	public static int bfIndexOf(String all, String sub){
		if(null == all || null== sub) return -1;
		int lenAll = all.length();
		int lenSub = sub.length();
		int i = 0;
		while (i < lenAll) {
			int j = 0;
			while (j < lenSub) {
				if(all.charAt(i) == sub.charAt(j)){
					i++;
					j++;
				} else {
					break;
				}
			}
			if(lenSub == j) return i - lenSub;
			else i = 1+i - j;
		}
		return -1;
	}
	
	public static int KMP_Index(char[] allArray, char[] subArray) { 
		int[] next = next(subArray); 
		int i = 0; 
		int j = 0; 
		while (i <= allArray.length - 1 && j <= subArray.length - 1) { 
			if (j == -1 || allArray[i] == subArray[j]) { 
				i++; 
				j++; 
			} else { 
				j = next[j]; 
			} 
		}
		if (j < subArray.length) return -1;
		else return i - subArray.length;
	}
	
	public static int[] next(char[] t) { 
		int[] next = new int[t.length]; 
		next[0] = -1; 
		int i = 0; 
		int j = -1; 
		while (i < t.length - 1) { 
			if (j == -1 || t[i] == t[j]) { 
				i++; 
				j++; 
				if (t[i] != t[j]) next[i] = j;
				else next[i] = next[j]; 
			} else { 
				j = next[j]; 
			} 
		}
		return next; 
	}
}

测试结果与分析

在设置主串长度为 800 万、子串长度为 11 的情况下，运行 50 次循环，获取的关键性能数据如下：

--------------------------
10次bfIndexOf= 94ms
10次stringIndexOf= 56ms
10次KMPIndexOf= 76ms
... 
50次bfIndexOf;总计耗时: 550ms
50次stringIndexOf;总计耗时: 335ms
50次KMPIndexOf;总计耗时: 450ms
...

• JDK 原生 indexOf 最快：平均耗时约 335ms。SUN/Oracle 在其标准库实现中进行了深度底层优化，往往比常规算法实现更加高效。
• KMP 算法位列第二：约为 450ms。尽管在理论复杂度上有优势，但由于引入了 next 数组计算及额外的索引操作，在某些短子串场景下可能并未展现出碾压优势。
• BF 算法相对最慢：约为 550ms。频繁的回溯操作导致了更多的 CPU 周期消耗。

额外发现：字符串构建的隐形成本

除了核心算法对比，测试代码中还暴露了一个重要的性能陷阱：StringBuilder 的数据准备耗时占据了总时间的绝大部分。

根据日志显示，在 50 次循环中：

• 字符串构建耗时 (allbuild)：高达 26,501ms。
• 核心算法总耗时 (BF/String/KMP)：仅占几百毫秒级别。

这意味着使用 StringBuilder 追加拼接 800 万个随机字符是一个非常昂贵的操作（换算约每秒 1600 万次 append）。在进行此类极大规模的微基准测试时，如果不单独剥离“数据准备”这一前置步骤，会导致测试结论失真。

改进建议

1. 数据预热**：如果必须测试这种规模的算法，建议先将生成的超大字符串写入本地文件，并在测试前读入内存，避免每次循环都重复创建对象。
2. 关注 GC 影响：如此大对象的频繁创建会触发 System.gc() 及堆内存压力，测试时应留意 Garbage Collection 造成的毫秒级卡顿。
3. 工具选择**：对于简单的统计场景，JDK 原生方法通常是最优解；仅在特定数据结构或受限环境下，才有必要手动实现 KMP。

以上就是Java中的字符串查找性能测试的详细分析内容，更多关于Java基础算法优化与性能调优的资料请关注本站其它相关文章！