tiny_id

tiny_id 已被 block-id 取代。 block-id 在分布式环境中的使用具有更好的属性，并且是可逆的。对于新用途，我建议使用 block-id 而不是 tiny_id。

tiny_id 是一个用于生成非顺序、紧密排列的短ID的 Rust 库。

大多数其他的短ID生成器只是将随机数字连接起来。由于 生日问题，这种方法容易发生冲突。例如，一个四位的字母代码在800个代码后大约有50%的冲突概率。

tiny_id 使用 线性同余生成器 生成代码，这些代码不会发生冲突，同时只保留一小部分恒定大小的状态。对于相同的四位字母代码，tiny_id 在所有456,976个可能的代码都生成之前，冲突概率为0%。

这些代码适用于需要短、可读的代码的场景，使得连续生成的两个代码与不连续生成的代码一样不可能相似。它不应在需要不可猜测的代码的情况下使用。它们也不能防止有人足够有动机进行 德国坦克问题 类型的分析。

随机短代码的示例，由 generate.rs 示例生成，展示了这些代码的序列看起来像什么

paul:~/tiny_id$ target/debug/examples/generate 36 4 10
9chl
yqpv
z1rk
c18m
1tc5
2t22
ftgv
4yih
5nag
ioa0

如何使用它

基本用法

use tiny_id::ShortCodeGenerator;

fn main() {
    // The length of generated codes
    let length: usize = 6;

    // Create a generator. The generator must be mutable, because each
    // code generated updates its state.
    let mut generator = ShortCodeGenerator::new_alphanumeric(length);

    // Generate the next short code, and update the internal generator state.
    let code = generator.next_string();
    assert_eq!(length, code.len());
}

字母表

用于构建短代码的字符集（或任意值）被称为 字母表。 tiny_id 有几个内置的字母表，或者您可以提供自己的。

如果您提供字母表而不是使用内置的字母表，该字母表必须不包含任何重复条目。库不会强制执行此要求，但违反此要求会导致冲突。

use tiny_id::ShortCodeGenerator;

fn main() {
    let length: usize = 6;

    // There are several built-in alphabets with convenience constructors.
    
    // Numeral digits (0-9), like "769458".
    ShortCodeGenerator::new_numeric(length);

    // Numeral digits and lowercase letters (a-z), like "l2sx2b".
    ShortCodeGenerator::new_lowercase_alphanumeric(length);

    // Numeral digits, lowercase, and uppercase letters, like "qAh6Gg".
    ShortCodeGenerator::new_alphanumeric(length);

    // Uppercase letters only, like "MEPQOD".
    ShortCodeGenerator::new_uppercase(length);

    // You can also provide an alphabet with any unicode characters.
    // I hope you don't use it for emoji, but you could:
    ShortCodeGenerator::with_alphabet(
        "😛🐵😎".chars().collect(),
        length
    );

    // The generator can also be used with non-char types, as long
    // as they implement Copy.
    let mut gen = ShortCodeGenerator::with_alphabet(
        vec![true, false],
        length
    );

    // next_string() is only implemented on ShortCodeGenerator<char>,
    // but gen is a ShortCodeGenerator<bool>, so we need to call
    // next_vec() instead, which returns a Vec<bool>.
    let result: Vec<bool> = gen.next_vec();
    assert_eq!(length, result.len());
}

耗尽策略

最终，所有短代码生成器都会达到一个点，即它们用完了给定长度的代码。当发生这种情况时，有以下三种选择来处理：

• 增加长度。这对应于 ExhaustionStrategy::IncreaseLength，这是默认值。
• 循环。这会从开始处重复代码的循环。每个循环中代码的顺序是相同的。对应于 ExhaustionStrategy::Cycle。
• 恐慌。在“快速失败”的精神下，当所有代码都已使用时，它会触发恐慌，对于预期之外耗尽的情况，其他程序假定不会发生。对应于 ExhaustionStrategy::Panic。

use tiny_id::{ShortCodeGenerator, ExhaustionStrategy};

fn main() {
    // Increase length (default).
    
    let mut gen = ShortCodeGenerator::new_uppercase(2);

    for _ in 0..(26*26) {
        let result = gen.next_vec();
        assert_eq!(2, result.len());
    }

    // We've exhausted all options, so our next code will be longer.
    let result = gen.next_vec();
    assert_eq!(3, result.len());

    // Cycle.
    
    let mut gen = ShortCodeGenerator::new_uppercase(2)
        .exhaustion_strategy(ExhaustionStrategy::Cycle);
    
    let first = gen.next_vec();

    for _ in 0..(26*26-1) {
        let result = gen.next_vec();
        assert_eq!(2, result.len())
    }

    // We've exhausted all options, so our next code will be a
    // repeat of the first.
    let result = gen.next_vec();
    assert_eq!(first, result);
}

工作原理

线性同余发生器（LCG）是一种简单、非加密的伪随机数生成器。

LCGs很有趣，因为它们在循环中生成数字，并且LCG的循环长度作为参数的函数已被广泛研究。特别是，人们已经很好地理解了如何创建一个生成1..m的数字且循环长度为m的LCG，即生成1..m的数字排列。这被称为Hull-Dobell定理。

对于大小为N的字母表和长度为L的ID，有N ^ L种可能的代码。我们可以通过将代码视为数字的base-N表示来在数字和这些代码之间相互转换。

结合这两个事实，我们的方法是

• 利用Hull-Dobell定理，构建一个LCG，使其可以以某种随机（类似）的顺序“访问”从1到N^L的所有数字。
• 使用基转换方法，将这些数字转换为短ID。

use tiny_id::{ShortCodeGenerator, ExhaustionStrategy};

fn main() {
    // This returns a vector of two short code generators.
    let mut generators: Vec<ShortCodeGenerator<_>> = ShortCodeGenerator::new_uppercase(5)
        .into_partitioned_generators(2);

    // Codes generated by the two generators will never overlap, because
    // they come from separate code spaces.
    assert_ne!(generators[0].next_string(), generators[1].next_string());
}