String.java源码解析之理解indexOf函数

2016-12-25 本文已影响195人 Android那些事儿

文章摘要
1、indexOf(String str,int fromIndex).
这里容易造成一个误解，认为[结果返回位置]要从fromIndex开始算起。
对于作为参数传入的fromIndex，只是用来标示[源字符串]开始查找的起始位置，不对返回Index产生影响。
2、【规则一】当开始查找位置大于等于源字符串长度时，如果[查找字符串]为空，则:返回字符串的长度，否则返回-1.
3、【规则三】如果[查找字符串]为空，则返回fromIndex。
4、源码解析indexOf执行过程，及其亮点。

一、indexOf函数简介
indexOf是String.java中的一个方法，用于返回[目标字符串]在[源字符串]中的位置。

1、indexOf：返回特定子字符串第一次在源字符串中的位置。如果源字符中不存在目标字符，则返回-1。

2、JDK 源码 API 介绍：

    /**
     * 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);
    }

    /**
     * Returns the index within this string of the first occurrence of the
     * specified substring, starting at the specified index.
     * @param   str         the substring to search for.
     * @param   fromIndex   the index from which to start the search.
     */
    public int indexOf(String str, int fromIndex) {
        return indexOf(value, offset, count,
                       str.value, str.offset, str.count, fromIndex);
    }

二、indexOf函数使用说明
indexOf存在多个重载函数，例如：

int indexOf(String str)
int indexOf(String str,int fromIndex).

无论indexOf函数的重载有多少，返回位置都是相对于字符串开头而言的。

1、indexOf(String str)
返回str第一次出现在字符串中的位置

String s = "12345#aaa#bbb#67890";
//字符串长度：19
System.out.println("字符串长度："+s.length());

//‘#’第一次出现的位置
int n = s.indexOf("#");
//第一次出现的#字符的位置：5
System.out.println("第一次出现的#字符的位置："+n);

2、indexOf(String str,int fromIndex)
从fromIndex开始搜索，返回str第一次出现在字符串中的位置

String s = "12345#aaa#bbb#67890";
//‘#’第一次出现的位置
int n = s.indexOf("#");//n = 5
int k = s.indexOf("#",n+1);
//第二次出现的#字符的位置：9
System.out.println("第二次出现的#字符的位置："+k);

这里容易造成一个误解，认为[结果返回位置]要从fromIndex开始算起。
对于作为参数传入的fromIndex，只是用来标示[源字符串]开始查找的起始位置，不对返回Index产生影响。

三、indexOf使用规则
1、【规则一】当开始查找位置大于等于源字符串长度时，如果[查找字符串]为空，则:返回字符串的长度，否则返回-1.

s = "12345#aaa#bbb#67890";
int m = s.indexOf("#",20);
//查找字符串为空，返回index：-1
System.out.println("查找字符串为空，返回index："+m);

int l = s.indexOf("",20);
//查找字符串为空，返回index：19
System.out.println("查找字符串为空，返回index："+l);

2、【规则二】如果fromIndex 小于 0，则从 0开始查找。
对于查找“#”首次出现的位置，fromIndex 传入0和负数，逻辑相同。

s = "12345#aaa#bbb#67890";
int a = s.indexOf("#",0);
int b = s.indexOf("#",-2);
//fromIndex = 0 或者 fromIndex < 0,结果一致。a = 5,b = 5
System.out.println("fromIndex = 0 或者 fromIndex < 0,结果一致。a = " + a
        + ",b = "+b);

3、【规则三】如果[查找字符串]为空，则返回fromIndex。

s = "12345#aaa#bbb#67890";
int c = s.indexOf("",5);
//查找字符串为空，则返回fromIndex。返回：：5
System.out.println("查找字符串为空，则返回fromIndex。返回：："+c);

4、【规则四】如果未匹配到目标字符串，返回位置，否则：返回-1。

四、源码解析indexOf方法：
亮点：
1、匹配首个目标字符。for循环中，嵌套while循环，从源字符串中，找到匹配目标字符的位置。
2、小范围匹配目标字符串。for循环中，嵌套for循环，在[目标字符串]长度范围内，遍历匹配，如果全部匹配，则方法return 结束。

3、函数解析
indexOf的函数算法，以字符串source=“ABCABCDEFGABCABC”，从中找到target=“CDEFG”字符串，初始查找位置=0。执行过程大体可以分为如下几个步骤（5、6是其中的亮点之一）：

1、遍历source字符串。
2、如果开始查找位置大于等于 source字符串的长度，则：target字符串为空，返回字符串的长度，否则返回-1；。
此处：初始查找位置为0，不符合红色标记的条件。
3、如果开始查找位置小于0，则开始查找位置等于0.
此处：初始查找位置为0，不符合红色标记的条件。
4、查找字符串长度为0，则返回初始查找位置，此位置大于等于0.
此处：初始查找字符串target长度为5，不符合红色标记条件。
5、根据target字符串第一个字符，定位source字符串，第一个匹配source的位置。

for (int i = sourceOffset + fromIndex; i <= max; i++) {
    if (source[i] != first) { 
        while (++i <= max && source[i] != first);
    }
}

此处：通过遍历source字符串，内部增加一个while循环，在source字符串中，找到target第一个字符‘C’，赋值给i。

6、匹配搜索的字符串是连续的，故而，根据target计算出来目标字符串长度‘end’，从5中的‘i’开始匹配，如果能够顺利匹配到end则，搜索结束并返回。

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;
 }

此处：字符‘C’之后，无法继续匹配剩余字符串，故而匹配失败。

7、如果匹配失败，则继续 5、6步骤，直至source字符串遍历结束。

4、原码实现及其注释

   static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
        //1、当开始查找位置 大于等于 源字符串长度时，如果[查找字符串]为空，则:
        //返回字符串的长度，否则返回-1.
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        //2、如果fromIndex 小于 0，则从 0开始查找。
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        //3、如果[查找字符串]为空，则返回fromIndex
        if (targetCount == 0) {
            return fromIndex;
        }
        //4、开始查找，从[查找字符串]中得到第一个字符，标记为first
        char first  = target[targetOffset];
        //4.1、计算[源字符串最大长度]
        int max = sourceOffset + (sourceCount - targetCount);
        //4.2、遍历查找
        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            //4.2.1、从[源字符串]中，查找到第一个匹配到[目标字符串]first的位置
            //for循环中，增加while循环
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }
            //4.2.2、如果在[源字符串]中，找到首个[目标字符串]，
            //则匹配是否等于[目标字符串]
            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                //4.2.2.1、得到下一个要匹配的位置，标记为j
                int j = i + 1;
                //4.2.2.2、得到其余[目标字符串]的长度，标记为end
                int end = j + targetCount - 1;
                //4.2.2.3、遍历，其余[目标字符串]，从k开始，
                //如果j不越界（小于end，表示：其余[目标字符串]的范围），
                //同时[源字符串]==[目标字符串]，则
                //自增，继续查找匹配。j++、k++
                for (int k = targetOffset + 1; j < end && source[j] ==
                         target[k]; j++, k++);
                //4.2.2.4、如果j与end相等，则表示：
                //源字符串中匹配到目标字符串，匹配结束，返回i。
                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        //其余情况，返回-1.
        return -1;
    }

String.java源码解析之理解indexOf函数

猜你喜欢

热点阅读