业务需求

调用服务需要生成一个随机的、不重复的8位数以内的号码。

方案一：号码池

当看到需求时，首先想到的是采用号码池来实现。

实现方式

初始化阶段就先将所有的8位数以内的号码生成号，然后进行随机打乱存储起来（即号码池）。在需要生成随机号码时以此从号码池中取出即可。

存在的问题

虽然该方法很简答，也很容易实现。但是最大的问题就是耗内存或者存储。一个int占8个字节，也就是32bit，8位数也就是1亿个数需要多少内存呢？32*100000000bit 也就是400M。（别给我说现如今磁盘不值钱）。

方案二循环使用号码池

实现方式

该方案是针对方案一的变种。就是生成号码池后用一个变量记录号码池使用次数，然后将次数加入到随机数中间，可以作为最高位、最低位、或中间位，以达到减少号码池大小的目录。

存在的问题

当第一次循环使用完成后，第二次循环在理论上存在可猜测型，即理论上不再随机了。但前提是需要直到第一次生成的所有号码的生成记录（其实从实际角度来讲是可以认为是不可实现的）。

避免出现第一次循环和第二次循环出现看起来分层的现象（比如第一次生成的落在1-10000 第二次生成的落在20000-30000），我认为将循环次数作为中间位插入即可从一定程度上避免看起来分层。

方案三布隆过滤器

前两种方案都是事先生成好再使用，存在的问题就是耗内存和初始化的时候比较繁琐，好处就是用的时候生成效率高。
而采用布隆过滤器（有关布隆过滤器的讲解和实现请问度娘）则可有效的减少内存使用。并且无需事先初始化。

实现方式

随机生成一个数，然后用布隆过滤器来过滤，通过则表示未使用过，则为有效随机数，把该数返回，同时将该数加入布隆过滤器。如果未通过过滤，则表示该数已使用过，则分别多该数依次+1和减一再次进行过滤，直到找到一个未使用的数。

存在的问题

总所周知，布隆过滤器存在误判。而且像当前这种业务需求，随者加入的加入的数越多，误判率将更高，并且在未命中有效数字是会进行一次循环查找，最差情况下需要循环n次，进行n次比对。所以布隆过滤器综合效率其实不高。

方案四 bitmap

实现方式

bitmap也是用过滤的思想，一个int32位，用int数组存储，一位表示一个数，用0表示未使用，1表示已使用，这样的话就不会像布隆过滤器那样出现误判。而且存储时号码池的32分之一。

存在的问题

和布隆过滤器一样，需要进行循环查找，最差情况下需要循环n次，进行n次比对。

但是在分配初期，由于随机的分散性，出现命中连续片段的概率是极低的。所以对于产出随机数个数要求并不高的系统效率并不会太低。
可以通过其他辅助的方式将让性能稳定一些，譬如随机只是随int数组的下标，然后从int数组的bit位依次取出未使用的位置做i为随机数输出。

总结

其实从某种角度讲，我认为循环使用号码池应该是最优的方式（毕竟存储确实不值钱）。不过实际情况中还需要考虑宕机恢复之类的情况。最后，如果像兼顾内存和效率的情况下，其实可以参考GC的分代回收，对于号码分配前期，命中重复概率小，我们就可以采用布隆过滤器，中期使用布隆过滤器产生随机数的retry次数达到阈值，则用bitmap来替换布隆过滤器，降低误判率，后期bitmap的retry达到阈值，就用号码池来替换bitmap。