strings

strings包提供了一些常用的字符串操作忠藤，對(duì)于中文也是友好的

Index

// Index returns the index of the first instance of substr in s, or -1 if substr is not present in s.
// 從字符串s中找子串substr第一次出現(xiàn)的索引位置，如果沒有則返回-1
// 該方法用到了暴力匹配和RabinKarp算法
func Index(s, substr string) int {
    // 獲取子串長(zhǎng)度
    n := len(substr)
    switch {
    // 子串長(zhǎng)度是0玷坠，則返回0
    case n == 0:
        return 0
    // 子串長(zhǎng)度是1，則使用IndexByte進(jìn)行字節(jié)匹配即可
    // IndexByte是用匯編實(shí)現(xiàn)的刑顺，就是普通的暴力匹配解法
    case n == 1:
        return IndexByte(s, substr[0])
    // 子串長(zhǎng)度=匹配串長(zhǎng)度玻孟，直接比較兩個(gè)串
    case n == len(s):
        if substr == s {
            return 0
        }
        return -1
    // 子串長(zhǎng)度 > 匹配串長(zhǎng)度，不可能匹配到扑馁，返回-1
    case n > len(s):
        return -1
    // 如果子串小于某個(gè)限定值涯呻，這里是bytealg.MaxLen
    // 這里bytealg.MaxLen是根據(jù)實(shí)際機(jī)器硬件決定的凉驻，可能是63、31等值
    // 這里的意思就是如果子串長(zhǎng)度比較小复罐，就不使用RabinCarp算法
    case n <= bytealg.MaxLen:
        // Use brute force when s and substr both are small
        // 如果匹配串的長(zhǎng)度也比較小沿侈，就直接使用IndexString進(jìn)行暴力匹配
        // IndexString也是匯編實(shí)現(xiàn)的
        if len(s) <= bytealg.MaxBruteForce {
            return bytealg.IndexString(s, substr)
        }
        // 下面的操作的意思就是先按照子串的首個(gè)字節(jié)去尋找可能的匹配點(diǎn)
        // 然后再進(jìn)行全匹配，如果匹配點(diǎn)分布密集市栗，且匹配失敗的次數(shù)達(dá)到某個(gè)限定值
        // 就降級(jí)使用IndexString進(jìn)行暴力匹配
        c0 := substr[0]
        c1 := substr[1]
        i := 0
        t := len(s) - n + 1
        fails := 0
        for i < t {
            // 這里就是找到下一個(gè)可匹配點(diǎn)
            if s[i] != c0 {
                // IndexByte is faster than bytealg.IndexString, so use it as long as
                // we're not getting lots of false positives.
                // 這里這么做的原因就是用IndexByte來(lái)尋找可匹配點(diǎn)比IndexString更快
                o := IndexByte(s[i+1:t], c0)
                if o < 0 {
                    return -1
                }
                i += o + 1
            }
            // 如果全匹配缀拭，則返回對(duì)應(yīng)的位置
            if s[i+1] == c1 && s[i:i+n] == substr {
                return i
            }
            // 否則失敗次數(shù)+1
            fails++
            i++
            // Switch to bytealg.IndexString when IndexByte produces too many false positives.
            // 當(dāng)失敗次數(shù)達(dá)到某個(gè)限定值時(shí)，可以認(rèn)為通過(guò)上面的方式尋找到多個(gè)匹配點(diǎn)填帽，并且均失敗了
            // 那么匹配串的特征就是可能包含眾多的匹配點(diǎn)蛛淋，直接降級(jí)使用暴力匹配即可
            if fails > bytealg.Cutover(i) {
                r := bytealg.IndexString(s[i:], substr)
                if r >= 0 {
                    return r + i
                }
                return -1
            }
        }
        return -1
    }
    // 走到這里說(shuō)明子串的長(zhǎng)度不小
    // 依然先嘗試尋找匹配點(diǎn)的方式來(lái)暴力匹配
    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+1:t], c0)
            if o < 0 {
                return -1
            }
            i += o + 1
        }
        if s[i+1] == c1 && s[i:i+n] == substr {
            return i
        }
        i++
        fails++
        // 最后失敗次數(shù)超過(guò)限定值后，改使用RabinKarp算法
        if fails >= 4+i>>4 && i < t {
            // See comment in ../bytes/bytes.go.
            // RabinKarp算法篡腌，后面會(huì)詳述
            j := bytealg.IndexRabinKarp(s[i:], substr)
            if j < 0 {
                return -1
            }
            return i + j
        }
    }
    return -1
}

RabinKarp算法的核心思想有兩個(gè)
1. 通過(guò)某種方式來(lái)計(jì)算字符串的hash值褐荷，并且做比較，如果相等則再進(jìn)行字符比較嘹悼，這樣絕大部分的不匹配都會(huì)被hash值的比較過(guò)濾掉了
2. 在順序滑動(dòng)的窗口內(nèi)的子串的hash結(jié)果叛甫，可以通過(guò)上一個(gè)窗口內(nèi)的子串的hash結(jié)果計(jì)算得來(lái)，這樣每次計(jì)算hash值就可以減少很多計(jì)算量了

舉個(gè)栗子來(lái)看下go中的RabinKarp是如何計(jì)算hash的
s=123456789  substr=234  PrimeRK=16777619(這個(gè)值用來(lái)計(jì)算hash)
計(jì)算hash值的公式就是 (((s[0]*PrimePk + s[1])*PrimePk + s[2])*PrimePk + s[3])*PrimePk + ... + s[n]
也就是說(shuō)杨伙，對(duì)于窗口為n的子串s[:n]其监，其hash值就是 hash1 = s[0]*PrimePk^(n-1) + s[1]*PrimePk^(n-2) + ... + s[n-1]
當(dāng)窗口右滑一步時(shí)，窗口為n的子串s[1:n+1]限匣，其hash值就是 hash2 = s[1]*PrimePk^(n-1) + s[2]*PrimePk^(n-2) + ... + s[n] = hash1*PrimePk - s[0]*PrimePk^n + s[n] 這樣就清楚了hash2是怎么通過(guò)hash1計(jì)算得來(lái)的

這里還要說(shuō)一點(diǎn)抖苦，go實(shí)現(xiàn)的RabinKarp的PrimeRK就是16777619，有些人可能會(huì)比較疑惑米死，如果字符串比較長(zhǎng)锌历，按照PrimeRK的次方來(lái)乘，是否會(huì)溢出峦筒？這個(gè)答案是肯定的究西，就是會(huì)溢出，不過(guò)溢出也沒關(guān)系物喷，可以認(rèn)為是進(jìn)行了取余操作卤材，只要規(guī)則是一樣的，相同字符串計(jì)算出來(lái)的hash值肯定是相等的


// HashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
// 這就是計(jì)算字符串sep的hash值
// 注意這里會(huì)多余返回 PrimeRK^len(sep)脯丝，后面會(huì)有用的
func HashStr(sep string) (uint32, uint32) {
    hash := uint32(0)
    // 從sep[0]開始逐步計(jì)算疊加和乘以PrimeRK商膊，規(guī)則同上面說(shuō)的一樣的
    for i := 0; i < len(sep); i++ {
        hash = hash*PrimeRK + uint32(sep[i])
    }
    var pow, sq uint32 = 1, PrimeRK
    // 這里其實(shí)就是返回PrimeRK^len(sep)
    // 不過(guò)這里是通過(guò)位移操作來(lái)進(jìn)行的，主要是能減少一半的循環(huán)
    // 這里可能需要仔細(xì)想一想宠进，規(guī)則就是遇到0就翻倍PrimeRK的次方晕拆，也就是sq*sq
    // 為啥呢，因?yàn)榍驪rimeRK的次方數(shù)就同等于求len(sep)劳吠，這里len(sep)用二進(jìn)制表示
    // 如果是計(jì)算len(sep)啸澡，遇到0就乘以2，遇到1就疊加前面相乘的結(jié)果
    // 但這里是計(jì)算次方數(shù)泉蝌，所以遇到0就得sq*sq昆庇，也就是次方數(shù)*2末贾，遇到1就得*sq，也就是次方數(shù)相加
    for i := len(sep); i > 0; i >>= 1 {
        if i&1 != 0 {
            pow *= sq
        }
        sq *= sq
    }
    return hash, pow
}


// IndexRabinKarp uses the Rabin-Karp search algorithm to return the index of the
// first occurrence of substr in s, or -1 if not present.
// RabinKarp算法
func IndexRabinKarp(s, substr string) int {
    // Rabin-Karp search
    // 計(jì)算子串的hash和對(duì)應(yīng)的PrimeRK^len(substr)
    hashss, pow := HashStr(substr)
    n := len(substr)
    var h uint32
    // 計(jì)算s[:n]的hash并進(jìn)行比較
    for i := 0; i < n; i++ {
        h = h*PrimeRK + uint32(s[i])
    }
    // 如果剛好匹配整吆，則返回
    if h == hashss && s[:n] == substr {
        return 0
    }
    // 否則循環(huán)往后挪動(dòng)一位進(jìn)行匹配拱撵，即窗口右滑
    for i := n; i < len(s); {
        // 利用上面計(jì)算好的h，來(lái)計(jì)算后一個(gè)窗口的子串hash值表蝙，具體規(guī)則上面有描述拴测，這里實(shí)現(xià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
}

strings包的strings.go除了Index函數(shù)外還有很多其他的，實(shí)現(xiàn)都比較簡(jiǎn)單府蛇，這里不一一贅述了

Builder

strings.Builder提供了byte集索、[]byte、rune和string的拼接方法汇跨，并且能在容量不足的情況下自動(dòng)進(jìn)行擴(kuò)容

// A Builder is used to efficiently build a string using Write methods.
// It minimizes memory copying. The zero value is ready to use.
// Do not copy a non-zero Builder.
// 定義Builder結(jié)構(gòu)
// 一個(gè)byte切片和一個(gè)指向自己的指針
// 指向自己的指針主要用于防止復(fù)制
type Builder struct {
    addr *Builder // of receiver, to detect copies by value
    buf  []byte
}

// noescape hides a pointer from escape analysis.  noescape is
// the identity function but escape analysis doesn't think the
// output depends on the input. noescape is inlined and currently
// compiles down to zero instructions.
// USE CAREFULLY!
// This was copied from the runtime; see issues 23382 and 7921.
//go:nosplit
//go:nocheckptr
func noescape(p unsafe.Pointer) unsafe.Pointer {
    x := uintptr(p)
    return unsafe.Pointer(x ^ 0)
}

// 防止copy
func (b *Builder) copyCheck() {
    // 如果b.addr還未初始化
    if b.addr == nil {
        // This hack works around a failing of Go's escape analysis
        // that was causing b to escape and be heap allocated.
        // See issue 23382.
        // TODO: once issue 7921 is fixed, this should be reverted to
        // just "b.addr = b".
        // 這里同等于 b.addr=b务荆，就是將指向自己的指針賦值給addr
        // 這樣如果別的變量other復(fù)制了b的值，other.addr != &other
        // 這里noescape主要是為了解決逃逸分析失敗導(dǎo)致b逃逸并分配到堆上穷遂，具體后續(xù)專門有文章會(huì)講下go的內(nèi)存逃逸
        b.addr = (*Builder)(noescape(unsafe.Pointer(b)))
    } else if b.addr != b {
        // 如果發(fā)現(xiàn)是復(fù)制的函匕，直接panic
        panic("strings: illegal use of non-zero Builder copied by value")
    }
}

// String returns the accumulated string.
// 返回Builder拼接的字符串
func (b *Builder) String() string {
    return *(*string)(unsafe.Pointer(&b.buf))
}

// Len returns the number of accumulated bytes; b.Len() == len(b.String()).
// 同切片的len
func (b *Builder) Len() int { return len(b.buf) }

// Cap returns the capacity of the builder's underlying byte slice. It is the
// total space allocated for the string being built and includes any bytes
// already written.
// 同切片的cap
func (b *Builder) Cap() int { return cap(b.buf) }

// Reset resets the Builder to be empty.
// 重置復(fù)用，這里重置完就可以復(fù)制使用了塞颁，也可以直接繼續(xù)使用
func (b *Builder) Reset() {
    b.addr = nil
    b.buf = nil
}

// grow copies the buffer to a new, larger buffer so that there are at least n
// bytes of capacity beyond len(b.buf).
// 擴(kuò)容浦箱，擴(kuò)容到2*cap + n
func (b *Builder) grow(n int) {
    buf := make([]byte, len(b.buf), 2*cap(b.buf)+n)
    copy(buf, b.buf)
    b.buf = buf
}

// Grow grows b's capacity, if necessary, to guarantee space for
// another n bytes. After Grow(n), at least n bytes can be written to b
// without another allocation. If n is negative, Grow panics.
// 用戶可以自主擴(kuò)容
func (b *Builder) Grow(n int) {
    b.copyCheck()
    if n < 0 {
        panic("strings.Builder.Grow: negative count")
    }
    // 注意這里如果未使用空間 >= n吸耿，不會(huì)觸發(fā)擴(kuò)容
    if cap(b.buf)-len(b.buf) < n {
        b.grow(n)
    }
}

// Write appends the contents of p to b's buffer.
// Write always returns len(p), nil.
// 拼接[]byte
func (b *Builder) Write(p []byte) (int, error) {
    b.copyCheck()
    b.buf = append(b.buf, p...)
    return len(p), nil
}

// WriteByte appends the byte c to b's buffer.
// The returned error is always nil.
// 拼接byte
func (b *Builder) WriteByte(c byte) error {
    b.copyCheck()
    b.buf = append(b.buf, c)
    return nil
}

// WriteRune appends the UTF-8 encoding of Unicode code point r to b's buffer.
// It returns the length of r and a nil error.
// 拼接rune祠锣，支持將UTF-8編碼的Unicode碼點(diǎn)拼到Builder
func (b *Builder) WriteRune(r rune) (int, error) {
    b.copyCheck()
    // Compare as uint32 to correctly handle negative runes.
    // 如果r只占用一個(gè)字節(jié)，就按照byte來(lái)處理即可
    if uint32(r) < utf8.RuneSelf {
        b.buf = append(b.buf, byte(r))
        return 1, nil
    }
    l := len(b.buf)
    // 一個(gè)UTF-8編碼的Unicode字符最多占用4個(gè)字節(jié)
    // 如果容量不夠咽安，就擴(kuò)容
    if cap(b.buf)-l < utf8.UTFMax {
        b.grow(utf8.UTFMax)
    }
    // 將r追加到buf中并返回r最終占用了幾個(gè)字節(jié)
    n := utf8.EncodeRune(b.buf[l:l+utf8.UTFMax], r)
    // 重置buf區(qū)間
    b.buf = b.buf[:l+n]
    return n, nil
}

// WriteString appends the contents of s to b's buffer.
// It returns the length of s and a nil error.
// 拼接字符串
func (b *Builder) WriteString(s string) (int, error) {
    b.copyCheck()
    b.buf = append(b.buf, s...)
    return len(s), nil
}

Reader

strings.Reader對(duì)應(yīng)Builder提供了讀取的方法伴网，通過(guò)記錄已讀取的位移，結(jié)合切片來(lái)高效的操作妆棒，同時(shí)支持位移回退澡腾，自定義讀取位置等

// A Reader implements the io.Reader, io.ReaderAt, io.ByteReader, io.ByteScanner,
// io.RuneReader, io.RuneScanner, io.Seeker, and io.WriterTo interfaces by reading
// from a string.
// The zero value for Reader operates like a Reader of an empty string.
// 定義Reader結(jié)構(gòu)
type Reader struct {
    // 目標(biāo)字符串
    s        string
    // 當(dāng)前讀取起始索引
    i        int64 // current reading index
    // 前一個(gè)rune的起始索引
    prevRune int   // index of previous rune; or < 0
}

// Len returns the number of bytes of the unread portion of the
// string.
// 未讀取的字節(jié)數(shù)
func (r *Reader) Len() int {
    if r.i >= int64(len(r.s)) {
        return 0
    }
    return int(int64(len(r.s)) - r.i)
}

// Size returns the original length of the underlying string.
// Size is the number of bytes available for reading via ReadAt.
// The returned value is always the same and is not affected by calls
// to any other method.
// 目標(biāo)字符串字節(jié)數(shù)
func (r *Reader) Size() int64 { return int64(len(r.s)) }

// Read implements the io.Reader interface.
// 讀取到[]byte中
func (r *Reader) Read(b []byte) (n int, err error) {
    // 如果已經(jīng)讀完
    if r.i >= int64(len(r.s)) {
        return 0, io.EOF
    }
    // 因?yàn)樽x取的是byte，所以這里需要將prevRune置為-1糕珊，原因后面說(shuō)
    r.prevRune = -1
    // 讀取到b中
    n = copy(b, r.s[r.i:])
    // 更新下次讀取的起始索引
    r.i += int64(n)
    return
}

// ReadAt implements the io.ReaderAt interface.
// 從自定義起始位置讀取到[]byte中
func (r *Reader) ReadAt(b []byte, off int64) (n int, err error) {
    // cannot modify state - see io.ReaderAt
    // 自定義起始位置不合法
    if off < 0 {
        return 0, errors.New("strings.Reader.ReadAt: negative offset")
    }
    // 自定義起始位置已經(jīng)超出了s串的末尾
    if off >= int64(len(r.s)) {
        return 0, io.EOF
    }
    // 以off偏移作為起始位置讀取到b中
    n = copy(b, r.s[off:])
    // 如果讀取到的字節(jié)數(shù)小于len(b)动分，說(shuō)明讀到了s的末尾
    if n < len(b) {
        err = io.EOF
    }
    return
}

// ReadByte implements the io.ByteReader interface.
// 讀取一個(gè)字節(jié)
func (r *Reader) ReadByte() (byte, error) {
    // 同樣將prevRune置為-1
    // 這里只要不是讀取rune，都需要將prevRune置為-1
    r.prevRune = -1
    // 如果讀取到了s的末尾
    if r.i >= int64(len(r.s)) {
        return 0, io.EOF
    }
    // 讀取一個(gè)字節(jié)
    b := r.s[r.i]
    // 更新下次讀取的起始索引
    r.i++
    return b, nil
}

// UnreadByte implements the io.ByteScanner interface.
// 讀取起始索引回退一個(gè)字節(jié)
func (r *Reader) UnreadByte() error {
    // 如果還未讀取或者重置了红选，此時(shí)讀取起始索引為s的第一個(gè)字符澜公，無(wú)法再向前回退
    if r.i <= 0 {
        return errors.New("strings.Reader.UnreadByte: at beginning of string")
    }
    // 同上
    r.prevRune = -1
    // 回退
    r.i--
    return nil
}

// ReadRune implements the io.RuneReader interface.
// 讀取一個(gè)utf-8編碼的unicode字符，即rune
func (r *Reader) ReadRune() (ch rune, size int, err error) {
    // 已經(jīng)讀到了末尾
    if r.i >= int64(len(r.s)) {
        r.prevRune = -1
        return 0, 0, io.EOF
    }
    // 將當(dāng)前讀取索引標(biāo)記為前一個(gè)rune的起始索引(因?yàn)閺脑撍饕帉⒁x取一個(gè)rune喇肋，讀取之后該rune就是prevRune)
    r.prevRune = int(r.i)
    // 如果rune占用一個(gè)字節(jié)
    if c := r.s[r.i]; c < utf8.RuneSelf {
        r.i++
        return rune(c), 1, nil
    }
    // 否則動(dòng)態(tài)獲取一個(gè)rune坟乾，可能占用2迹辐、3、4個(gè)字節(jié)甚侣，并返回最終rune占用的字節(jié)數(shù)
    ch, size = utf8.DecodeRuneInString(r.s[r.i:])
    // 更新下次讀取的起始索引(即跳過(guò)這個(gè)rune)
    r.i += int64(size)
    return
}

// UnreadRune implements the io.RuneScanner interface.
// 往前回退一個(gè)rune
func (r *Reader) UnreadRune() error {
    // 如果還未讀取或已重置明吩，無(wú)法回退
    if r.i <= 0 {
        return errors.New("strings.Reader.UnreadRune: at beginning of string")
    }
    // 如果prevRune < 0，即上一次讀取的不是rune殷费，也無(wú)法回退
    // 這就是為啥上面讀取非rune的時(shí)候都需要將prevRune置為-1
    // 注意0是合法的索引位置印荔，所以只能用負(fù)數(shù)來(lái)標(biāo)識(shí)無(wú)
    if r.prevRune < 0 {
        return errors.New("strings.Reader.UnreadRune: previous operation was not ReadRune")
    }
    // 回退
    r.i = int64(r.prevRune)
    // 回退完之后prevRune又置為-1
    // 這里可以看到prevRune只能標(biāo)記前一次讀取的rune，所以只能回退一次详羡，這個(gè)跟UnreadByte是不一樣的
    r.prevRune = -1
    return nil
}

// Seek implements the io.Seeker interface.
// 實(shí)現(xiàn)接口方法io.Seeker
// 根據(jù)指定條件更改讀取索引躏鱼，offset是相對(duì)的位移，可正可負(fù)
func (r *Reader) Seek(offset int64, whence int) (int64, error) {
    // 同上
    r.prevRune = -1
    var abs int64
    switch whence {
    // 從頭開始找
    case io.SeekStart:
        abs = offset
    // 從當(dāng)前位置開始找
    case io.SeekCurrent:
        abs = r.i + offset
    // 從末尾開始找
    case io.SeekEnd:
        abs = int64(len(r.s)) + offset
    default:
        // 都不是則報(bào)錯(cuò)
        return 0, errors.New("strings.Reader.Seek: invalid whence")
    }
    // 非法索引
    if abs < 0 {
        return 0, errors.New("strings.Reader.Seek: negative position")
    }
    // 更新讀取索引
    r.i = abs
    return abs, nil
}

// WriteTo implements the io.WriterTo interface.
// 實(shí)現(xiàn)接口方法io.WriterTo
// 以當(dāng)前讀取索引為起始殷绍，將剩余的字符串寫入到w中
func (r *Reader) WriteTo(w io.Writer) (n int64, err error) {
    // 同上
    r.prevRune = -1
    // 已經(jīng)到末尾了
    if r.i >= int64(len(r.s)) {
        return 0, nil
    }
    // 獲取剩余的子串
    s := r.s[r.i:]
    // 寫入到w
    m, err := io.WriteString(w, s)
    // 寫入的字節(jié)數(shù)量非法
    if m > len(s) {
        panic("strings.Reader.WriteTo: invalid WriteString count")
    }
    // 更新讀取索引
    r.i += int64(m)
    n = int64(m)
    // 檢測(cè)子串是否全部寫入到w中
    if m != len(s) && err == nil {
        err = io.ErrShortWrite
    }
    return
}

// Reset resets the Reader to be reading from s.
// 重置Reader
func (r *Reader) Reset(s string) { *r = Reader{s, 0, -1} }

// NewReader returns a new Reader reading from s.
// It is similar to bytes.NewBufferString but more efficient and read-only.
// 根據(jù)字符串s新建一個(gè)Reader染苛，并返回其指針
func NewReader(s string) *Reader { return &Reader{s, 0, -1} }

總結(jié)

strings.Builder和strings.Reader都不是并發(fā)安全的，注意小心使用主到，同時(shí)strings.Builder不允許值復(fù)制茶行，這樣能避免多個(gè)Builder的buf切片共用同一個(gè)底層數(shù)組，造成讀寫沖突登钥，不過(guò)雖然不能進(jìn)行值復(fù)制畔师，指針卻可以，所以并發(fā)的問題還是會(huì)存在牧牢，使用的時(shí)候千萬(wàn)要小心