java - 如何使用自定义字母有效地构建随机字符串？

Question

我有一个包含 c 个字符的字母表，我想用该字母表创建长度为 n 的随机 String。 p>

举个例子，假设字母表由字母 a-w(所以 c = 23)和生成的 String 组成s 的长度应为 n = 67。

生成这样的 String 的一种直观但又幼稚的方法可能如下所示:

String alpha = "abcdefghijklmnopqrstuvw";
int c = alpha.length();
int n = 67;

SecureRandom random = new SecureRandom();
StringBuilder sb = new StringBuilder();

for(int i = 0; i < n; i++) {
    int nextPosition = random.nextInt(c);
    sb.append(alpha.charAt(nextPosition));
}

System.out.println(sb.toString());

虽然这有效，但我感觉我浪费了太多的熵。在此示例中，我要求 RNG n = 67 次以获得另一个数字，而所有这些只是为了生成一个 String。

• 将 RNG 称为 a 会不会更有效(...熵节省) 次数少得多，可以更好地利用返回的 值(value)观？例如。使用方法仅调用一次 RNG nextBytes(byte[] bytes) 和一个足够大的 byte 数组 创建一个长度为 67 的 String？
• 但在后一种情况下，我不知道如何映射随机 byte 数组到所需的 String。如果一个角色有 一个字节的大小(或一个字节的倍数)，所以 n = 67 I 可以向 RNG 请求 67 个随机 byte 然后直接映射 从数组中的每个 byte 到一个字符。然而，对于大小为 c = 23 的字母表，每个字符只有五个字节，甚至没有使用所有五个字节 - 如果我们从上面枚举所有字符，那么第一个字符 'a' 的二进制值为 00000 而最后一个字符 'w' 的二进制值为 10110(它是我为 n 和 c 选择素数并非巧合，它在任何情况下都应该有效。

Answer 1

首先做一些数学运算:我们需要从 23 个字母的字母表中覆盖 67 个字符的最小字节数 n 是多少？将每个字节视为 256 个字母的字母表中的一个“字母”。然后

23⁶⁷ < 256ⁿ

或

n > 67 * ln(23)/ln(256)，计算结果为 37.8848，即 38 个字节。

您可以生成一个 38 字节的数组，从中构造 BigInteger，然后调用 divideAndRemainder(23) 67 次以获得单个字符索引和数组中的下一个数字迭代:

random.nextBytes(bytes);
BigInteger big = new BigInteger(bytes).abs();
BigInteger bigC = BigInteger.valueOf(c);
for (int i = 0 ; i != n ; i++) {
    BigInteger[] dr = big.divideAndRemainder(bigC);
    res[i] = alpha.charAt(dr[1].intValue());
    big = dr[0];
}
String result = new String(res);

Demo