Golang的strings.go源码解析

前言

strings包是我们经常在处理字符串的时候要用的，这次我们来看看它其中的一些方法具体是如何实现的。我就找到其中常用的几个方法，然后针对其中比较难的部分还有应用到一些特别算法的部分进行分析。

ToUpper

先来看个简单的ToUpper，将所有字符转换成大写。这个如果让我们自己实现也没有什么难度，就是遍历每个字符转换成大写就可以。

// ToUpper returns a copy of the string s with all Unicode letters mapped to their upper case.
func ToUpper(s string) string {
    isASCII, hasLower := true, false
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= utf8.RuneSelf {
            isASCII = false
            break
        }
        hasLower = hasLower || (c >= 'a' && c <= 'z')
    }

    if isASCII { // optimize for ASCII-only strings.
        if !hasLower {
            return s
        }
        b := make([]byte, len(s))
        for i := 0; i < len(s); i++ {
            c := s[i]
            if c >= 'a' && c <= 'z' {
                c -= 'a' - 'A'
            }
            b[i] = c
        }
        return string(b)
    }
    return Map(unicode.ToUpper, s)
}

可以看到，源码中考虑的比较周全，判断了一下字符集的问题。

小技巧

c -= 'a' - 'A'
我们可以看到，这个转换大写的技巧，学习一下。如果转换成小写，只要改成+就可以了。

Replace

然后看一个稍微复杂一些的，Replace，这个函数的目标是替换s中old的字符，替换前n个，如果n为负数则全部替换。作为实现也其实不难，就是找到对应字符替换就可以。

// Replace returns a copy of the string s with the first n
// non-overlapping instances of old replaced by new.
// If old is empty, it matches at the beginning of the string
// and after each UTF-8 sequence, yielding up to k+1 replacements
// for a k-rune string.
// If n < 0, there is no limit on the number of replacements.
func Replace(s, old, new string, n int) string {
    if old == new || n == 0 {
        return s // avoid allocation
    }

    // Compute number of replacements.
    if m := Count(s, old); m == 0 {
        return s // avoid allocation
    } else if n < 0 || m < n {
        n = m
    }

    // Apply replacements to buffer.
    t := make([]byte, len(s)+n*(len(new)-len(old)))
    w := 0
    start := 0
    for i := 0; i < n; i++ {
        j := start
        if len(old) == 0 {
            if i > 0 {
                _, wid := utf8.DecodeRuneInString(s[start:])
                j += wid
            }
        } else {
            j += Index(s[start:], old)
        }
        w += copy(t[w:], s[start:j])
        w += copy(t[w:], new)
        start = j + len(old)
    }
    w += copy(t[w:], s[start:])
    return string(t[0:w])
}

其实核心就是下面三句
w += copy(t[w:], s[start:j])
w += copy(t[w:], new)
start = j + len(old)
利用一个start去标记从旧字符串的那个位置开始复制，到目标字符处，然后复制需要替换的字符进去就可以了，最后移动start为了下一次准备就可以了。

小技巧

t := make([]byte, len(s)+n*(len(new)-len(old)))
这个在源码中很是常见，告诉我们一个道理，在创建slice的时候，尽可能的去指定好你需要的长度来避免扩容。

Index

好了，热身差不多了，来看我们这次的重头戏，index。我们经常需要确定一个字符串是否存在于另一个字符串内，并且要知道它的位置，所以需要index方法。
其实说到底就是字符串匹配嘛。

自己思考

一般看源码我都习惯先自己想想怎么去实现，这个方法对于我来说很熟悉，在java中其实很暴力，就是两层for搞定，先找到第一个一样的字符，然后匹配剩下的。然后我也知道，字符串匹配在算法中有著名的KMP算法，但是理解难度很大。不知道golang会怎么实现，于是我看到了一个新的算法RabinKarp（我之前不了解）

源码

func indexRabinKarp(s, substr string) int {
    // Rabin-Karp search
    hashss, pow := hashStr(substr)
    n := len(substr)
    var h uint32
    for i := 0; i < n; i++ {
        h = h*primeRK + uint32(s[i])
    }
    if h == hashss && s[:n] == substr {
        return 0
    }
    for i := n; i < len(s); {
        h *= primeRK
        h += uint32(s[i])
        h -= pow * uint32(s[i-n])
        i++
        if h == hashss && s[i-n:i] == substr {
            return i - n
        }
    }
    return -1

}

你先自己尝试看看是否能看出什么门道？

猜测

是不是乍看之下这个方法很复杂，各种操作眼花缭乱，如果你是第一次看源码可能是这样的，看多了你应该有和我一样的直觉和经验（反正我是有感觉）
我看源码的第二个步骤就是大致看一眼，然后在不看任何文章解析的情况下猜测它的实现。
在我看完上面之后留个我三个重点

hashss, pow := hashStr(substr)h += uint32(s[i])h -= pow * uint32(s[i-n])if h == hashss && s[i-n:i] == substr {

它获取了对应的hash值，这个算法和hash有关
它对哈希值进行了增减操作
它比较哈希值和字符串从而确定位置

到这里，我已经有了一个大概的思路，这个算法应该是通过哈希值快速确定子串是否可能存在，在哈希值相同的情况下再去比较真实的字符是否一致，同时在计算哈希值的时候采用特殊的机制来实现了增加就可以完成哈希的改变。其实如果你有相同的想法，恭喜你，已经八九不离十了。

分析

我们举个实际的例子来说明上面的事情
原本的字符串为："ABCDE"，子串为"BCD"
首先计算出"BCD"的hash为100（举个例子）
然后循环原本的字符串
取出"ABC"计算hash为200 != 100所以一定不是
取出字符D
原来的hash加D减去A计算hash为100 == 100（这里注意，不是重新计算，而是在原有的基础上进行的计算）
最后还是要比较一遍是否正确，因为hash一致不一定原值一致。

假设待匹配字符串的长度为M，目标字符串的长度为N，那么一共比较N-M+1就可以了

hash

那么其实你应该注意到了，最神奇的就是这个hash值，为什么可以这样操作，如果是md5这种必须重新计算，是不可能完成这样的操作的。

// primeRK is the prime base used in Rabin-Karp algorithm.
const primeRK = 16777619

// hashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func hashStr(sep string) (uint32, uint32) {
    hash := uint32(0)
    for i := 0; i < len(sep); i++ {
        hash = hash*primeRK + uint32(sep[i])
    }
    var pow, sq uint32 = 1, primeRK
    for i := len(sep); i > 0; i >>= 1 {
        if i&1 != 0 {
            pow *= sq
        }
        sq *= sq
    }
    return hash, pow
}

这个就是hash算法，其实它每次完成的就是 *primeRK 加上新的字符，那么pow是什么呢？加减究竟是如何完成的呢？我举个例子你就明白了。

还是刚才的ABCDE和BCD，我们用q表示常数primeRK
那么BCD的hash计算出来应该是B * q^2 + C * q + D
而ABC的hash应该是A * q^2 + B * q + C
那当D来的时候如何操作的呢？回看一下indexRabinKarp就明白了。
[A * q^2 + B * q + C] * q + D - A * pow
= A * q^3 - A * pow + B * q^2 + C * q + D
明白了吧，这个pow其实就是计算hash值时的最高指数，通过每次减去常数的最高指数项就能完成之前的操作。

聪明。不由得佩服能想出这样算法的人~

其他一些方法

看完最复杂的index实现，再说说几个由它引申出来的方法。

genSplit

其实就是分组字符串，通过某些子串去分割成一个个部分，其实实现就是每次Index找到位置然后进行存储到新的地方就可以了。

for i < n {
    m := Index(s, sep)
    if m < 0 {
        break
    }
    a[i] = s[:m+sepSave]
    s = s[m+len(sep):]
    i++
}

countGeneric

计数，统计字符串中子串出现的数目，也是通过index完成，统计一下而已

for {
    i := Index(s, substr)
    if i == -1 {
        return n
    }
    n++
    s = s[i+len(substr):]
}

总结

其实很多源码中的实现不复杂，多看看，不仅能熟练使用api还能学到一些骚操作，何乐而不为呢？不得不佩服一些牛逼的算法实现，真的厉害~