如何高效地产生一个随机字符串？这是一个简单的问题，但是简单的问题也有极致的做法。这个问题是StackOverflow上的一个问题，How to generate a random string of a fixed length in Go?

1. 最通用的方案

最普通的方案就是随机产生每个字符，所以整个字符串也是随机的，这样的好处是可以控制要使用的字符。

func init() {
    rand.Seed(time.Now().UnixNano())
}

var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandStringRunes(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letterRunes[rand.Intn(len(letterRunes))]
    }
    return string(b)
}

2. 字节替换rune

如果需求是只使用英语字母字符（包括大小写），那么我们可以使用byte来替换rune，因为UTF-8编码中的英语字母和byte是一一对应的。

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func RandStringBytes(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Intn(len(letterBytes))]
    }
    return string(b)
}

3. 使用余数

在2中，我们使用的rand.Intn来随机选择一个字段，rand.Intn会调用Rand.Intn，而Rand.Intn会调用Rand.Int32n，它会比直接调用rand.Int63慢，后者会产生一个63bit的随机整数。

我们可以直接使用rand.Int63，然后除以len(letterBytes)的余数来选择字符：

func RandStringBytesRmndr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
    }
    return string(b)
}

这个实现明显会比上面的解决方案快，但是有一个小小的瑕疵，那就是字符被选择的概率并不是完全一样。但是这个差别是非常非常的小（字符的数量52远远小于1<<63-1），只是理论上会有差别，实践中可以忽略不计。

4. 掩码

通过前面的方案，我们可以看到我们并不需要太多的bit来决定字符的平均分布，事实上我们只需要随机整数的后几个bit就可以选择字母。对于52个英语字母（大小写）来说，只需要6个bit就可以实现均匀分布（52=110100b），所以我们可以使用rand.Int63后6个bit来实现，我们只接受后六位在0..len(letterBytes)-1的随机数，所以不在这个范围，可以直接丢弃。通过掩码就可以得到一个整数的后6个bit。

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

const (
    letterIdxBits = 6 // 6 bits to represent a letter index
    letterIdxMask = 1 << letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
)

func RandStringBytesMask(n int) string {
    b := make([]byte, n)
    for i := 0; i < n; {
        if idx := int(rand.Int63() & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i++
        }
    }
    return string(b)
}

5. 掩码加强版

上面有个不好的地方，会产生大量的丢弃的case，造成重选和浪费。rand.Int63回产生63bit的随机数，如果我们把它分成6份，那么一次就可以产生10个6bit的随机数，这样就减少了浪费。

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

const (
    letterIdxBits = 6 // 6 bits to represent a letter index
    letterIdxMask = 1 << letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax = 63 / letterIdxBits // # of letter indices fitting in 63 bits
)

func RandStringByesMaksImpr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdxMsk letters!
    for i, cache, remain := n-1, rand.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = rand.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }
    return string(b)
}

6. Source

上面的代码的确好，没有太多可以改进的地方，即使可以提升，也得花费很大的复杂度。

我们可以从另外一个方面进行优化，那就是提高随机数的产生（source）。

crypto/rand包提供了Read(b []byte)的方法，它可以随机生成我们所需bit的字节，但是因为处于安全方面的设计和检查，它的随机数产生比较慢。

我们再转回math/rand，rand.Rand使用rand.Source来产生随机bit。rand.Source是一个接口，提供了Int63() int64，正是我们所需要的。

所以我们可以直接使用rand.Source，而不是全局提供或者共享的随机源。

var src = rand.NewSource(time.Now().UnixNano())

func RandStringBytesMaskImprSrc(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx :=int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }
    return string(b)
}

需要注意的是，这里我们不需要去初始化math/rand包里的全局Rand，因为我们没有用到这个，并且rand.Source已经初始化好了。

还有一点就是，math/rand包中的默认source是多线程安全的，而通过rand.NewSource()获取的source不是多线程安全的。

### 7. 使用strings.Builder

前面所有的解决方案都是通过将一个slice转换成string返回的。这种转换方式会对slice的内容进行复制，因为string的值是不可变的。

为了避免这个复制，我们可以使用srings.Builder。strings.Builder在内部维护了一个[]byte，当工作结束的时候，通过Builder.String()函数返回一个string，而在内部避免了多余的复制。

func RandStringBytesMaskImprSrcSB(n int) string {
    sb := strins.Builder{}
    sb.Grow(n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, reamin := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            sb.WriteByte(letterBytes[idx])
            i--
        }
        cache >>= letterIdxBits
        remain--
    }
    return sb.String()
}

注意，新建一个strings.Builder之后，要调用Builder.Grow()函数，保证具有足够的空间，防止多余的复制。

8. Benchmark

最后通过测试来看看各种实现的性能：

package main

import (
    "math/rand"
    "testing"
    "strings"
    "time"
)

// Implementations

func init() {
    rand.Seed(time.Now().UnixNano())
}

var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandStringRunes(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letterRunes[rand.Intn(len(letterRunes))]
    }
    return string(b)
}

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

const (
    letterIdxBits = 6 // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax = 63 / letterIdxBits // # of letter indices fitting in 63 bits
)

func RandStringBytes(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Intn(len(letterBytes))]
    }
    return string(b)
}

func RandStringBytesRmndr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Int63()%int64(len(letterBytes))]
    }
    return string(b)
}

func RandStringBytesMask(n int) string {
    b := make([]byte, n)
    for i := 0; i < n; {
        if idx := int(rand.Int63() & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i++
        }
    }
    return string(b)
}

func RandStringBytesMaskImpr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdxMax letters!
    for i, cache, remain := n-1, rand.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = rand.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }
    return string(b)
}

var src = rand.NewSource(time.Now().UnixNano())

func RandStringBytesMaskImprSrc(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }
    return string(b)
}

func RandStringBytesMaskImprSrcSB(n int) string {
    sb := strings.Builder{}
    sb.Grow(n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            sb.WriteByte(letterBytes[idx])
            i--
        }
        cache >>= letterIdxBits
        remain--
    }
    return sb.String()
}

// Benchmark functions

const n = 16

func BenchmarkRunes(b *testing.B) {
    for i := 0; i < b.N; i++ {
        RandStringRunes(n)
    }
}

func BenchmarkBytes(b *testing.B) {
    for i := 0; i < b.N; i++ {
        RandStringBytes(n)
    }
}

func BenchmarkBytesRmndr(b *testing.B) {
    for i := 0; i < b.N; i++ {
        RandStringBytesRmndr(n)
    }
}

func BenchmarkBytesMask(b *testing.B) {
    for i := 0; i < b.N; i++ {
        RandStringBytesMask(n)
    }
}

func BenchmarkBytesMaskImpr(b *testing.B) {
    for i := 0; i < b.N; i++ {
        RandStringBytesMaskImpr(n)
    }
}

func BenchmarkBytesMaskImprSrc(b *testing.B) {
    for i := 0; i < b.N; i++ {
        RandStringBytesMaskImprSrc(n)
    }
}

func BenchmarkBytesMaskImprSrcSB(b *testing.B) {
    for i := 0; i < b.N; i++ {
        RandStringBytesMaskImprSrcSB(n)
    }
}

测试结果：

BenchmarkRunes-8 2000000 773 ns/op 96 B/op 2 allocs/op
BenchmarkBytes-8 2000000 615 ns/op 32 B/op 2 allocs/op
BenchmarkBytesRmndr-8 3000000 430 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMask-8 3000000 560 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMaskImpr-8 10000000 174 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMaskImprSrc-8 10000000 138 ns/op 32 B/op 2 allocs/op
BenchmarkBytesMaskImprSrcSB-8 10000000 193 ns/op 16 B/op 1 allocs/op