Golang伪随机字符串（大量重复）

Question

我正在尝试生成 5 个字符的随机字符串。我尝试过的每个实现都会在非常小的样本量（10k-40k）后生成重复项。虽然我知道以编程方式不可能生成真正的随机字符串，但我很惊讶地看到重复项以如此高的频率出现。

我尝试了几种实现（及其变体）但没有运气。每个最多在约 40k 字符串后生成一个重复项。鉴于由 [A-Z a-z] 组成的 5 字符字符串中有 380,204,032 个唯一组合，我希望能够在遇到重复之前生成更多的字符串。

经过搜索后，我发现了一些很好的资源，它们是我实现的基础

• Go中如何生成固定长度的随机字符串？

• https://www.datagenx.net/2022/10/random-number-genearion-with-cryptorand.html

第二个链接特别引起了我的注意，因为作者提到使用

"crypto/rand"

包可以更好地避免重复。然而，在遇到重复之前我能够生成多少字符串似乎没有什么区别。

我尝试过的其他变体

• 在每个字符（而不是每个字符串）之后调用

  rand.NewSource

• 使用多个

  rand.NewSource

  并使用第一个的输出作为第二个、第三个等的种子。

任何人都可以深入了解为什么这些随机字符串不那么随机，以及我可以采取一些步骤在遇到重复之前生成至少 1M 字符串吗？

我知道我可以使用第三方库，但我想避免这种情况。

func Test_RandomString(t *testing.T) {

    tests := map[string]struct {
        Length       int
        UniuqeValues int
    }{
        "5 x 1,000,000": {
            Length:       5,
            UniuqeValues: 1_000_000,
        },
    }

    for name, test := range tests {
        t.Run(name, func(t *testing.T) {
            actual := utils.RandomString(test.Length)
            assert.Equal(t, test.Length, len(actual))

            values := make(map[string]struct{})
            for count := 0; count < test.UniuqeValues; count++ {
                value := utils.RandomString(test.Length)

                _, found := values[value]
                if found {
                    t.Fatalf("duplicate value found after %v: %v", count, value)
                }

                values[value] = struct{}{}
            }

        })
    }
}

func RandomString_CryptoRand(length int) string {

    const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    var randomStr []byte = make([]byte, length)

    for i := 0; i < length; i++ {

        idx, _ := rand.Int(rand.Reader, big.NewInt(int64(len(letters))))
        randomStr[i] = letters[idx.Int64()]
    }
    return string(randomStr)
}

func RandomString_MathRand(length int) string {
    var src = rand.NewSource(time.Now().UnixNano())
    const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    sb := strings.Builder{}
    sb.Grow(length)

    for idx := 0; idx < length; idx++ {
        sb.WriteByte(letterBytes[int64(src.Int63())%int64(len(letterBytes))])
    }

    return sb.String()
}

Answer 1

无需复杂的数学，即使没有二项式分布：比方说，您从 380,204,032 个样本中抽取了 20,000 个样本，但还没有任何双精度数。对于下一次抽奖，您中双倍的机会是 20,000/380,204,032 = 0.0001052067

从那时起，双倍的机会会不断增加，但我们可以说，事实并非如此。对于接下来的 20,000 次抽奖，我们将在每次抽奖中添加此机会，最终得出 20000/380204032 * 20000 = 1.05，即 > 1。

因此，即使不考虑在前 20,000 次抽奖中获得双倍的机会，并且不考虑获得双倍的机会的不断增加，我们也应该预期在前 40,000 次抽奖中会获得双倍。

你的问题是你的期望，而不是最好的 Go 函数或包。

如何生成必要的更多随机字符串，然后删除双打？ （也许可以在这里看到代码：https://github.com/lehnert-b/spd）