随机生成唯一的字符串序列的一些算法

随机生成唯一的字符串显然是一个十分重要的功能，比如为对象分配 ID 或者生成某种索引。现在我们考虑一些可能的算法。

随机选择

如果我们对于字符串的唯一性并不是严格要求的，即我们只期望生成的字符串出现重复的可能性足够小，我们可以使用字符池随机选择的方法生成字符串。

字符池即待选字符（例如全体英文字母和数字），我们从中放回地选择 n 个字符作为字符串。这样我们生成一个重复的概率为：

$$ P(重复) = \frac{已生成的字符串个数}{字符池大小^{字符串长度}} $$

如果我们选择小写字母和数字组成的 16 字符的字符串，该算法生成重复的字符串的概率为：

$$ P(重复) = \frac{k}{36^{16}} < 2 \times 10^{-25} (k = 1) $$

其中 \(k\) 为已生成的字符串个数。

当数字太大或者太小的时候人容易失去对其的把握。所以为了方便比较，双色球中一等奖的概率为 \( \frac{1}{17721088} > 1 \times 10^{-7} \). 现在我们开始生成字符串，当 \(k\) 达到 \(10^9\) 的数量级时生成出重复的字符串的概率和双色球中一等奖的概率处在同一数量级。这对于一些小的索引，比如用户 ID 等已经够用——除非你真的幸运，能在开始的几百个生成中撞到一次重复。

混合随机选择

当然，如果我们希望进一步降低重复的可能，可以使用混合随机选择。

我们取当前的时间戳并映射到字符池（当然，我们的字符池里已经有数字了，所以可以直接使用数字表示，或者也可以自行设计一个单射的映射），然后再进行随机选择，将两个结果拼接到一起就可以得到一个重复率无限接近于 0 的方案，因为时间是单向连续运行的，对吧？我们暂时不考虑在时间不连续和存在回环的情况。如果我们需要毫秒级甚至微秒级的生成，我们只需要把时间戳的颗粒度调整得更小就可以满足需求。

当然，这样就失去了一些随机性了，但对于对象索引而言已经够用。

洗牌算法

但是就算概率再小，还是有可能撞到的。如果我们需要确保生成是绝对不会重复的（而且又希望不包含显而易见的规律的），可以考虑用洗牌算法。

首先，我们按某种已知不重复的方法生成一个序列，比如从 aaa..aa, aaa..ab 这样一点一点生成一个枚举序列；然后使用 Fisher-Yates 洗牌算法就可以将这个序列随机打乱，从而得到一个随机序列。之后我们只需要依次取出序列中的字符串就可以了。

Fisher-Yates 的洗牌算法十分简单，我们记列表的最后一个元素的下标为 i. 随机选择一个数 j 有 0 <= j <= i, 然后将这两个下标对应的元素交换位置，完成后将 i 的值减一并重复这一过程，直到整个列表被这样处理完成。

这样需要保存整个随机序列。如果我们要生成 36 字符 16 位的随机字符串的所有值，则会产生数量级在 \( 10^{24} \) 字节的数据。我们为了能够把握这个数据量还是需要进行比较一下，目前单体容量最大的商用存储介质是 LTO-8 磁带，可存储 30TB 的数据（即容量在 \( 10^{13} \) 字节的数量级）。我们需要用 \( 10^9 \) 盒磁带才能提供 \( 10^{24} \) 字节级别的存储。顺便一提，一盒 LTO-8 磁带的大小是 10cm 见方，2cm 厚。一个房间的高度按 2.5m 计算，那么 \( 10^9 \) 盒磁带密集堆放的话可以填满 \( 10^5 \) 平米的空间，考虑到一个典型的住宅大概 100 平米，一栋这样的住宅楼可以有 25 层，每层可以有 5 户，那么这些磁带大概可以堆满 10 栋这样的楼。对了，现在全球数据中心存储的数据总量在 \( 10^{21} \) 字节 (1000EB) 这么多，所以如果要托数据中心存储这些数据的话，可能还需要再建 1000 个全球数据中心。

这画风怎么拐到 XKCD 上了，我们回到字符串生成上。

唯一映射

如果我们自己不能给出一个满意的随机生成的算法，可否借助具有唯一性的映射来生成唯一随机字符串呢？这样我们可以将自然数（含零，下文如无特殊说明均含零）数列映射到字符串上，得到唯一随机序列。

一个最简单的唯一映射是 id. 不过显然它是不随机的。其实它也不需要是真随机，只要保证即使有人得到了生成的字符串序列，也无法预测下一个字符串会是什么就足够了。那么我们可以利用加密算法来生成不重复的序列。注意：这里说的加密算法是实打实的加密算法，不是散列算法，后者是不具有可逆性的。

比如我们取自然数数列，对每一个数进行 DES 加密，那么结果必然是唯一的，因为加密结果必然可逆而自然数数列中没有重复项，且加密时需要的密钥在不公开的情况下很难通过密文推导，所以生成的结果是无法被预测的，满足条件。当然得到的结果可能并不一样长，可以通过补零等方式填充到相同长度。

真的无法存下么？

我们已经知道了整个生成空间，以及在进行打乱之后，生成序列就确定下来了。那么能否通过一种算法将这个序列压缩起来，或者使用一个计算方法可以在多项式时间内计算出序列中的任意一项呢？这个问题我目前还没有能力解出，先记在这里以便日后讨论。