这两天在leetcode写题的时候看到了一题自己实现strStr(),就是类似于String.indexOf()方法的功能。具体一点就是
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
我们平时遇到这种的时候都是一般都是直接调用indexOf()，但是人家要求自己实现。实现嘛也不难，很快就实现了，但是发现自己写的代码又臭又长，于是就想看看人家是怎么写的。废话不多说，正文开始。
源码分析
使用idea工具的可以ctrl+左键进入方法源码
第一层
首先我们来看点进去的源码
/**
* Returns the index within this string of the first occurrence of the
* specified substring.
*
* <p>The returned index is the smallest value <i>k</i> for which:
* <blockquote><pre>
* this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @return the index of the first occurrence of the specified substring,
* or {@code -1} if there is no such occurrence.
*/
public int indexOf(String str) {
return indexOf(str, 0);
}
首先光标在这一层的indexOf()方法上面，里面有一个参数str,上面有解释the substring to search for。意思说这就是我们indexOf()传进来的字符串，然后方法体内又调用了indexOf(),学过java都知道这是一个方法重载。由于里面没什么东西了，我们点进去这个重载的indexOf()看看。
第二层
/**
* Returns the index within this string of the first occurrence of the
* specified substring, starting at the specified index.
*
* <p>The returned index is the smallest value <i>k</i> for which:
* <blockquote><pre>
* <i>k</i> >= fromIndex {@code &&} this.startsWith(str, <i>k</i>)
* </pre></blockquote>
* If no such value of <i>k</i> exists, then {@code -1} is returned.
*
* @param str the substring to search for.
* @param fromIndex the index from which to start the search.
* @return the index of the first occurrence of the specified substring,
* starting at the specified index,
* or {@code -1} if there is no such occurrence.
*/
public int indexOf(String str, int fromIndex) {
return indexOf(value, 0, value.length,
str.value, 0, str.value.length, fromIndex);
}
点进来一看，这个indexOf(String str, int fromIndex)，有两个参数。看上面注释是说什么
@param str the substring to search for.
str是我们上面传进来的字符串
@param fromIndex the index from which to start the search.
这个fromIndex说的是从哪个下标开始进行搜索，我们回到上面那个indexOf(),参数是0，也就是我们默认就是从0开始查找这个字符串，合乎情理。但是如果我们想从另一个下标开始查找的话，可以自己传入一个fromIndex，那么它就会自己调用第二层的indexOf()。
然后我们看看里面这个方法重载，这个indexOf()多了很多的参数。我们先来简单分析一下再进入下一层。
首先是这个value,方法直接就调用了。说明这是String自带的参数。点进去看一下声明
/** The value is used for character storage. */
private final char value[];
可以发现这是一个字符串数组，这里我们可以大胆的猜测一下，我们new一个String对象的时候的那个字符串，变成了这个对象里面的字符数组参数，这样的话那么就一定有具体赋值的操作。我们在源码里面查找了一下，果然
/**
* Allocates a new {@code String} so that it represents the sequence of
* characters currently contained in the character array argument. The
* contents of the character array are copied; subsequent modification of
* the character array does not affect the newly created string.
*
* @param value
* The initial value of the string
*/
public String(char value[]) {
this.value = Arrays.copyOf(value, value.length);
}
String的有参构造方法将这个字符串，或者说字符数组，赋值给了String的value字符数组。这也是为了String其他的操作方便。
既然知道了value的来历，那么其他参数就可以很好的理解了。
value.length就是这个字符数组的长度，str.value就是str的这个字符串的字符数组，str.value.length该字符数组的长度。fromIndex参数解释过了，至于两个0，我们进下一层看看具体的介绍。
第三层
/**
* 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;
}
这一层代码量明显多了起来，而且里面也没有方法重载，应该就是最后一层了。首先我们来看看它的参数代表着一些什么。
- source
@param source the characters being searched.
翻译过来呢是正在被搜索的字符，我们在上一层传进来的参数，是要被搜索的字符串的字符数组，所以也就是这个意思。
- sourceOffset
@param sourceOffset offset of the source string.
offset我们可以理解为开端，翻译过来就是源字符串的开端。根据上面传过来的0，我们可以很容易的知道，这应该指的是源字符串最开始的下标。
- sourceCount
@param sourceCount count of the source string.
这里我们上面传过来的是字符数组的长度，所以这指的就是字符串的长度。
- target
@param target the characters being searched for.
target目标，也就是我们要搜索的字符串。
- targetOffset
@param targetOffset offset of the target string.
目标字符串的最开始的下标。
- targetCount
@param targetCount count of the target string.
目标字符串的长度。
- fromIndex
最开始的参数，在上面都有介绍。
知道了这些具体的参数，下面的实现代码我们就可以比较容易的阅读了。
首先呢是三个if判断
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
第一个if语句指的是如果我们的要搜索的的字符串的开始下标大于等于源字符串的长度的话，进入判定，下面是一个三目运算，如果目标字符串的长度等于0的话，返回的是源字符串的长度，否则返回-1。这样解释可能有点绕，我们举个例子就比较清楚了。
如果我们的最开始调用方法的时候是"hello".indexOf("he",5);，意思是从hello下标5开始查找he，如果有的话返回查找到的第一个字符下标。而最后一个o字符的下标是4，很明显是查不到的，所以我们需要返回什么呢？5大于等于hello的字符长度5，进入判定，he的长度不等于0，返回-1。但是我们如果查找的是空字符串的话那么返回的就是hello的长度5了。
第二个if语句指的是如果我们要查找的字符串的下标从小于0开始的话，将下标赋值为0。这个很好理解，我们数组下标是从0开始的，就算你再小于0，我们也只能从0开始。
第三个if语句，如果你的目标长度为0的话，也就是空字符串，返回的是你要开始查找的下标。这个也很好理解，代入第一个if语句的例子就可以明白。
接着看代码，下面定义了两个变量
char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
first是目标字符串的第一个字符
max是源字符串开始下标+（源字符串长度-目标字符串长度），具体干什么用我们结合下面来分析。
下面是一个for语句
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;
}
}
}
循环是从要开始查找的下标开始，到max结束。这里我们举一个例子就能明白为什么要这么做
还是"hello".indexOf("he",0);,不过这次我们从0开始。先计算可以得到max=3，也就是我们遍历的到第二个l就结束了。这下一下子就明白了，遍历到这后面就剩一个l了，明显小于我们要的目标字符串长度。所以就可以停止了，而不是要遍历到我们源字符串长度的尽头。这在两个字符串长度都比较大的时候，复杂度就会得到优化。
继续看下面
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
这个if语句就是一直在源字符串查找与我们目标字符串第一个字符相同的字符，如果找到，就停止。因为i会一直自增，如果没找到的话，就会到for的边界跳出for，最后返回-1。如果找到的话我们进入下面的代码
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;
}
}
如果查到的下标在max范围之内的话，我们定义j为下一个字符下标，end为查找完的目标字符串最后一个字符下标。
然后定义k为目标字符串第二个字符的下标，在j<end的同时如果源字符串在j下标的字符和目标字符串为k下标的字符相等的话，j和k就自增。如果没有就停止。
如果j能够成功的遍历到end的话，也就是在这个范围期间source[j]和target[k]都相等的话，我们就能够说i就是查找到该字符串的第一个下标。这里返回的是i - sourceOffset，其实就是i，因为我们知道sourceOffet就是0。
如果么有遍历到end，说明这个i开始的下标，长度为targetCount的字符串不是我们要查找的字符串，那么继续外层for循环开始查找i，直到退出for循环。
最后没有查找到话返回-1。
总结
对于源码的解析可能也有很多不足，如果有什么错误希望可以不吝赐教。篇幅很多地方都写的特别详细，可能懂得人就会觉得啰嗦。当然这更多是自己的阅读笔记，所以不要介意。
网友评论