共计 4947 个字符，预计需要花费 13 分钟才能阅读完成。
golang 源码探究 -strings
Contain()
func Contains(s, substr string) bool
Contains() 返回一个布尔值，若 substr 存在于 s 中，则返回 true，不存在则返回 false。
// Contains reports whether substr is within s
func Contains(s, substr string) bool {return Index(s, substr) >= 0
}Index()
我们再来看 Index(),
func Index(s, substr string) int
Index() 返回 substr 出现在原始 string s 中的 位置，如果 s 中 meiyousubstr，则返回 -1
// Index returns the index of the first instance of substr in s, or -1 if substr is not present in s.
func Index(s, substr string) int {n := len(substr) // 先获取 substr 的长度 赋给 n
switch {
case n == 0: // 如果 substr 的长度为 0，则返回 0，return 0
case n == 1:
return IndexByte(s, substr[0]) // 后面再看一下 IndexByte() 的源码
case n == len(s): // 如果 s 和 substr 长度相等，直接判断俩字符串是否一模一样
if substr == s {return 0}
return -1
case n > len(s): // 如果 substr 的长度大于 s 的长度，那肯定不存在了，返回 -1，说明 substr 不存在于 s 中
return -1
case n <= bytealg.MaxLen: // 后面得看 bytealg.MaxLen
// Use brute force when s and substr both are small
if len(s) <= bytealg.MaxBruteForce { // const 型：const MaxBruteForce = 64
return bytealg.IndexString(s, substr)
}
c0 := substr[0]
c1 := substr[1]
i := 0
t := len(s) - n + 1
fails := 0
for i < t {if s[i] != c0 {
// IndexByte is faster than bytealg.IndexString, so use it as long as
// we're not getting lots of false positives.
o := IndexByte(s[i:t], c0)
if o < 0 {return -1}
i += o
}
if s[i+1] == c1 && s[i:i+n] == substr {return i}
fails++
i++
// Switch to bytealg.IndexString when IndexByte produces too many false positives.
if fails > bytealg.Cutover(i) {r := bytealg.IndexString(s[i:], substr)
if r >= 0 {return r + i}
return -1
}
}
return -1
}
c0 := substr[0]
c1 := substr[1]
i := 0
t := len(s) - n + 1
fails := 0
for i < t {if s[i] != c0 {o := IndexByte(s[i:t], c0)
if o < 0 {return -1}
i += o
}
if s[i+1] == c1 && s[i:i+n] == substr {return i}
i++
fails++
if fails >= 4+i>>4 && i < t {
// See comment in ../bytes/bytes_generic.go.
j := indexRabinKarp(s[i:], substr)
if j < 0 {return -1}
return i + j
}
}
return -1
}internel/bytealg 中：
MaxLen is the maximum length of the string to be searched for (argument b) in Index.
main.go:5:2: use of internal package internal/bytealg not allowed想看一下 bytealg.Maxlen 等于多少，但是 go build 后报错，说 internal/bytealg 不允许用
在 internel 包搜了一下 MaxLen
如是，MaxLen 于 CPU 有关。
package bytealg
import "internal/cpu"
const MaxBruteForce = 64
func init() {
if cpu.X86.HasAVX2 {MaxLen = 63} else {MaxLen = 31}
}cpu.X86.HasAVS2 是个啥？来看一下 cpu.X86.HasAVX2
X86.HasAVX = isSet(ecx1, cpuid_AVX) && osSupportsAV看一下 isSet()
func isSet(hwc uint32, value uint32) bool {return hwc&value != 0}// cpuid is implemented in cpu_x86.s.
func cpuid(eaxArg, ecxArg uint32) (eax, ebx, ecx, edx uint32) _, _, ecx1, edx1 := cpuid(1, 0) osSupportsAVX := false
// For XGETBV, OSXSAVE bit is required and sufficient.
if X86.HasOSXSAVE {eax, _ := xgetbv()
// Check if XMM and YMM registers have OS support.
osSupportsAVX = isSet(eax, 1<<1) && isSet(eax, 1<<2)
}。。。涉及 cpu 硬件相关的了。。。。
回到 strings.Index(),go on
虽然 bytealg.MaxLen 不知道是多少，但是但是从 case 语句不难看出，bytealg.MaxLen 是一个可能要比 substr 的长度小的值，如果 substr 的确比 bytealg.MaxLen 小，则执行 case n <= bytealg.MaxLen，否则跳出 case。
直接看 case 几种情况都不满足的块
c0 := substr[0] // 获取 substr 的第一个字符
c1 := substr[1] // 第二个
i := 0
t := len(s) - n + 1 // t 是 s 的长度减 substr 的长度 + 1，，，啧啧啧
fails := 0
for i < t { // 进入循环
if s[i] != c0 {// 如果 substr 的头 不等于 s[i]
o := IndexByte(s[i:t], c0) // 直接将 substr 的头放在 s 的 slice 中判断
if o < 0 { // 不存在，直接返回 -1
return -1
}
// substr 的头存在于 s[i] 剩下的部分。那直接看 substr 的第二个字符存不存在于 s[i+o] 中，i += o
}
if s[i+1] == c1 && s[i:i+n] == substr {// 恩，如果 substr 的头等于 s[i] 直接看 substr 的第二个字符等不等于 s[i+1]
// 并且判断 s 的 slices[i:i+n] 和 substr 相等不，如果相等，那么 substr 就存在于 s 中了，位置是 i
return i
}
// 其他情况，i++，在 for 的判定条件下继续循环。失败次数 +1，i++
fails++
if fails >= 4+i>>4 && i < t { 如果失败次数大于等于 4+i 得到二进制数右移四位并且 i < t，// 得看一下 indexrabinKarp 是个啥？// 不难看出，这块是针对于失败次数比较多的时候执行的。// See comment in ../bytes/bytes_generic.go.
j := indexRabinKarp(s[i:], substr)
if j < 0 {return -1}
return i + j
}
}
// 如果循环执行完了，到这儿了，说明 substr 不存在于 s 中，返回 -1
return -1indexRabinKarp()
看一下 indexRabinKarp() 吧！
Rabin-Karp 是个啥？查了一下。
原来 rabinkarp 是一种字符串查找算法，看看吧！想必你已经知道 Rabin-Karp 了，直接跳到下一个目录吧。
Rabin-Karp Algorithm-WikiPedia
图解 Rabin-Karp 字符串查找算法
func indexRabinKarp(s, substr string) int {
// Rabin-Karp search
hashss, pow := hashStr(substr) // hashStr 是个啥？n := len(substr)
var h uint32
for i := 0; i < n; i++ { // 当 0 < i < n 时 循环，得到 h，执行下一块的 if 判断
h = h*primeRK + uint32(s[i])
}
if h == hashss && s[:n] == substr {
// 如果 判断 substr 是不是就是紧挨这 s 的头对齐的时候并且相等的，如果是，index = 0，返回 0
return 0
}
for i := n; i < len(s); { // 如果 substr 和 s 的头对齐之后不相等，则继续循环，判断下。从 i = n 开始判断
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
}hashStr
hashStr()
// 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]) // hash 是循环 len(sep) 次的 这串操作的 int32 型的数
// 假设 len(sep) = 4
//i = 0: hash = uint32(sep[0])
//i = 1: hash = uint32(sep[0])* primeRK + uint32(sep[1])
//...
}
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 {i 是 seq 的长度，执行一次循环体之后，i = i + i 右移一位 ( 二进制)，// 等于 i = i + floor(i/2)（十进制，）if i&1 != 0 {pow *= sq // 如果 i 就是 1 了 pow = pow * sq}
sq *= sq // i 不是 1，sq = sq*sq
}
// 假设 len(sep) = 4
// i = 4, sq = sq^2
// i = 2, sq = sq^4
// i = 1, pow = pow*sq = sq = sq^4
// 假设 len(sep) = 5
// i = 5, sq = sq^2，5 的二进制 101 >> 1 = 10
// i = 2, sq = sq^4
// i = 1, pow = sq = sq^4，还是 sq^len(sep)
return hash, pow 输入一个字符串，返回俩 unint 值
}Rabin-Karp 算法就是 为了避免挨个字符对文本 s 和 substr 进行比较，可以尝试一次性判断两者是否相等。因此，我们需要一个好的哈希函数（hash function）。通过哈希函数，可以算出代匹配字符串 substr 的哈希值，然后将它和文本中的 s 的切片 s[x：y] 的哈希值进行比较。
比如原字符串为：AABXYXABXZ
我的 substr 为：ABX
先算出 ABX 的 hash，然后按照 substr 的长度算 AAB 的 hash，比一下，再算 ABX 的 hash 比一下，再算 BXY 的 hash 比一下，再算 XYX 的 hash 比一下，如果目标字符串和原字符串的 hash 比的结果一致，还得再把目标字符串和原字符串的字符串值比一下，因为不好的 hash 函数可能会有 hash 冲突。