今天瀏覽了一下java里的String類,發(fā)現(xiàn)一個靜態(tài)方法有點(diǎn)意思磁奖,就是我們常用的indexOf(String str)的底層實(shí)現(xiàn)破加,先看下代碼調(diào)用鏈。
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內(nèi)的位置,若查找到max位置還找到押框,則返回-1岔绸;
- 若在source匹配到了target的第一個字符,那么在依次比較srouce和target后面的字符橡伞,一直到target的末尾盒揉;
- 如果target后面的字符與source都已經(jīng)匹配,則返回在source上匹配到的第一個字符的相對下標(biāo)兑徘,否則返回-1刚盈。
但是仔細(xì)讀代碼會發(fā)現(xiàn)一個問題,就是這里
int max = sourceOffset + (sourceCount - targetCount);
max的計算方式挂脑,max的作用是計算出最大的首字符匹配次數(shù)藕漱,取值范圍應(yīng)該是"max <= sourceCount"欲侮。
所以target字符串的長度是可以不用匹配的,故“sourceCount - targetCount”是沒問題的肋联。
關(guān)鍵的地方是這里加上了sourceOffset威蕉,sourceOffset是source字符串的起始匹配偏移量,即從source的哪個字符開始匹配橄仍。
所以韧涨,根據(jù)代碼里的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內(nèi)可以匹配到返回正確結(jié)果8(結(jié)果8是相對于sourceOffset的結(jié)果虑粥,如果轉(zhuǎn)換成source內(nèi)的位置則是13)。
但是如果target在source內(nèi)匹配不到宪哩,則會拋出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)
可見報出越界的下標(biāo)是14,這就是由于max = sourceOffset + (sourceCount - targetCount)引起,計算出的max值為:17锁孟。
所以彬祖,個人認(rèn)為max計算這里是個潛在的BUG,應(yīng)該改為 int max = sourceCount - targetCount;
不過這個方法是一個非public方法罗岖,只在String內(nèi)部調(diào)用涧至,同時也跟蹤了所有對該方法的調(diào)用鏈,都是傳入的默認(rèn)0,在使用時不會出現(xiàn)數(shù)組越界問題桑包。
不知這是開發(fā)者故意為之南蓬,還是其它我未知用意,歡迎大家交流討論Q屏恕W阜健!