共计 3553 个字符，预计需要花费 9 分钟才能阅读完成。
今天浏览了一下 java 里的 String 类，发现一个静态方法有点意思，就是我们常用的 indexOf(String str) 的底层实现，先看下代码调用链。
public int indexOf(String str) {
return indexOf(str, 0);
}
public int indexOf(String str, int fromIndex) {
return indexOf(value, 0, value.length,
str.value, 0, str.value.length, fromIndex);
}
static int indexOf(char[] source, int sourceOffset, int sourceCount,
String target, int fromIndex) {
return indexOf(source, sourceOffset, sourceCount,
target.value, 0, target.value.length,
fromIndex);
}
/**
* Code shared by String and StringBuffer to do searches. The
* source is the character array being searched, and the target
* is the string being searched for.
*
* @param source the characters being searched.
* @param sourceOffset offset of the source string.
* @param sourceCount count of the source string.
* @param target the characters being searched for.
* @param targetOffset offset of the target string.
* @param targetCount count of the target string.
* @param fromIndex the index to begin searching from.
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
int max = sourceOffset + (sourceCount – targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount – 1;
for (int k = targetOffset + 1; j < end && source[j]
== target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i – sourceOffset;
}
}
}
return -1;
}
底层的字符串匹配的逻辑比较简单，就是普通的匹配模式：
查找首字符，匹配 target 的第一个字符在 source 内的位置，若查找到 max 位置还找到，则返回 -1；
若在 source 匹配到了 target 的第一个字符，那么在依次比较 srouce 和 target 后面的字符，一直到 target 的末尾；
如果 target 后面的字符与 source 都已经匹配，则返回在 source 上匹配到的第一个字符的相对下标，否则返回 -1。
但是仔细读代码会发现一个问题，就是这里
int max = sourceOffset + (sourceCount – targetCount);
max 的计算方式，max 的作用是计算出最大的首字符匹配次数，取值范围应该是 ”max <= sourceCount”。所以 target 字符串的长度是可以不用匹配的，故“sourceCount – targetCount”是没问题的。关键的地方是这里加上了 sourceOffset，sourceOffset 是 source 字符串的起始匹配偏移量，即从 source 的哪个字符开始匹配。所以，根据代码里的 max 计算方式，最终计算出来的 max 值是会有可能大于 sourceCount。看下测试代码：
package string;
/**
* string test
*/
public class StringTest {
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
int max = sourceOffset + (sourceCount – targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount – 1;
for (int k = targetOffset + 1; j < end && source[j]
== target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i – sourceOffset;
}
}
}
return -1;
}
public static void main(String[] args) {
String source = “abcdefghigklmn”;
String target = “n”;
int sourceOffset = 5;
int targetOffset = 0;
int index = indexOf(source.toCharArray(), sourceOffset, source.length(), target.toCharArray(), targetOffset, target.length(), 0);
System.out.println(index);
}
}
如果 target 在 source 内可以匹配到返回正确结果 8（结果 8 是相对于 sourceOffset 的结果，如果转换成 source 内的位置则是 13）。但是如果 target 在 source 内匹配不到，则会抛出 java.lang.ArrayIndexOutOfBoundsException 异常，如下：
Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: 14
at string.StringTest.indexOf(StringTest.java:27)
at string.StringTest.main(StringTest.java:52)
可见报出越界的下标是 14, 这就是由于 max = sourceOffset + (sourceCount – targetCount) 引起，计算出的 max 值为：17。
所以，个人认为 max 计算这里是个潜在的 BUG，应该改为 int max = sourceCount – targetCount;
不过这个方法是一个非 public 方法，只在 String 内部调用，同时也跟踪了所有对该方法的调用链，都是传入的默认 0, 在使用时不会出现数组越界问题。不知这是开发者故意为之，还是其它我未知用意，欢迎大家交流讨论！！！
