java - 独特的字符串 ID 生成算法

Question

我正在阅读一个开源项目 aventrix/jnanoid ，我无法理解代码中的 mask 和 step

public static String randomNanoId(final Random random, final char[] alphabet, final int size) {

    if (random == null) {
        throw new IllegalArgumentException("random cannot be null.");
    }

    if (alphabet == null) {
        throw new IllegalArgumentException("alphabet cannot be null.");
    }

    if (alphabet.length == 0 || alphabet.length >= 256) {
        throw new IllegalArgumentException("alphabet must contain between 1 and 255 symbols.");
    }

    if (size <= 0) {
        throw new IllegalArgumentException("size must be greater than zero.");
    }

    final int mask = (2 << (int) Math.floor(Math.log(alphabet.length - 1) / Math.log(2))) - 1;
    final int step = (int) Math.ceil(1.6 * mask * size / alphabet.length);

    final StringBuilder idBuilder = new StringBuilder();

    while (true) {

        final byte[] bytes = new byte[step];
        random.nextBytes(bytes);

        for (int i = 0; i < step; i++) {

            final int alphabetIndex = bytes[i] & mask;

            if (alphabetIndex < alphabet.length) {
                idBuilder.append(alphabet[alphabetIndex]);
                if (idBuilder.length() == size) {
                    return idBuilder.toString();
                }
            }

        }

    }

}

Answer 1

在循环中，我们尝试在每次循环迭代中选择字母表中的随机成员(字母)。请注意，这可能在给定的循环迭代中失败，因为我们可以获得大于字母表长度的索引。我们通过创建随机字节数组来选择字母。然后，我们使用每个随机字节的足够位来确保我们可以选择字母表中的任何字母。因此，如果我们的字母表有两个字符，一位就足够了，因为它可以有值 0 或 1。如果我们的字母表有 9 个字符，我们需要 4 位，因为 3 位只能表示 8 个值 (0-7)。这就是面具的本质。我们屏蔽掉随机字节的底部四位，并将它们用作字母表的索引。因此，如果我们的随机字节是 11000110，我们在示例中使用底部四位 (0110) 作为 9 个字符的字母表。 0110 是十进制的 6，因此我们选择字符数组中索引 6 处的字母。现在您可以看到它是如何失败的。如果我们的随机字节是 01001101，那么我们会屏蔽 1101，它是十进制的 13，超出了 9 个字母字母表的末尾。如前所述，设置掩码的代码确保它足够长以使用此算法覆盖整个字母表，但它不能防止它太长。

我不得不说步骤对我来说有点随意。如果你看一下循环步骤，就是我们试图获取长度大小的随机字符串的字节数。我们已经看到，单个循环迭代可能无法选择字母，因此步长需要大于大小。多长时间取决于掩码相对于我们的字母长度有多大，因此乘以 mask/alphabet.length 是有意义的。尽管如此，我们仍然无法选择足够的随机字母，因此我们增加了一个看起来像是任意因子 1.6 的值。当然，我们仍然可能会失败(我们所有的随机字节都可能指向字母表末尾之外的字母)，这就是为什么我们在那里有 while(true) :如果它确实失败了，我们会再试一次。