不丢脸出，个中的a、b、p的取值，便是是否能产出随机分布的数据根本所在。基本数论的知识见告我们，这个同余式的取值必定在[0,p-1]的范围内封闭，并且拥有最大为p的周期，或者是多个较小但互不重合的周期构成，当其周期为p时，其式就成为了0到p-1的一个离散排列。之以是这个看似大略的式子，能够成为随机数的天生方法，正是由于模数运算的良好特性，一来其在周期内绝不会涌现重复结果，二来其分布也相对均匀。可以将f(x)/p视为[0,1)范围内的均匀分布。
参数取值以是，我们的第一个问题，就一定是探索，在参数知足什么条件时，能将这个函数的周期尽可能的扩大，以更有效的利用其周期特性，挖掘这个式子产出的随机性。我们先从模数p开始，不论其他，光凭数学直觉就会让人下意识的想取一个大素数，以此轻易攫取优胜的分布特性和天然形成的宽周期。但是，我们要把稳到，伪随机数作为一个非常底层的方法，其存在本身便是为了效率的，取模操作虽然不算慢，但此时就会有一个更加优胜的模数跃入眼帘，那便是2^n——不但可以直接将取模操作退化为移位和与操作，也可以很轻松的理解随机数的取值范围。当然，这个周期比起素周期也更方便均分以转化为其他范围的随机函数。
当然，模数不是素数的情形下，就对a、b的取值有了更大的约束。为了取得一个满周期序列的天生方法，The Art of Computer Programming中论证了其充要条件，也是现在大部分线性同余产生器的布局依据：
• b与p互质
• c=a-1是p所有素因子的倍数
• 若p是4的倍数，c也是4的倍数
我们可以看到，这个中对加数b的约束实在非常小，于是在gcc中，就比较随意的选择了个12345，java中干脆是个小素数11。而对付a的取值，在已知我们取模数为2^n时，就非常随意马虎得知其约束条件：a-1是4的倍数。
实现时的考量现在我们满怀欢畅的得到一个满周期序列的天生方法，彷佛只须要按照某些特性去选一些精良的天生参数就可以跑起来成为一个经典库了。但事情还没有这么大略。刚才我们的选择还遗留了一个问题，我们每每不是直策应用一个全模数范围的随机，而是由大周期的随机数取模转化为一个更小的周期来随机——只要大范围的随机函数能担保概率均等，取模后自然也是一个均匀分布的函数：
——但是以上办法有一个天然的毛病，当我们的模数m与2的幂次干系时，其低位随机性并不是很好——低位周期的分布也会在这个小周期上呈现周期，形式化地说，便是：
也总是一个满周期序列，以是，无论怎么去改变参数分布，在模数非素的情形下，随机的分布都会呈现一个特殊均匀的形式，当我们想取得范围特殊小时，比如我们只须要0-1的整数，这个算法就会持续输出0、1、0、1、0、1、0、1。当然，它仍旧是满周期的，但是呈现出的结果完备违背了我们对付“随机”这件事的直觉，可预测性太强了。
这个时候，我们重新回顾一下，就会创造，我们想要的实在不是满周期的随机性，当周期非常小的时候，我们更期待的是超越本周期的随机性分布，比如，给0-1的随机安排一个00101110这样的周期序列，这个哀求在本周期的打算比较难达成的，但是既然这个小周期是由一个更大的周期序列摘取到的，我们就能够将大周期的随机性反响到小周期当中去。很多平台的实现当中，是舍弃这些随机性不强的低比特位，换为截取高位比特位作为结果序列，这样当然会导致该序列一些很好的数列特性消逝，但是从而也增强了其本身的随机性。
比如在java的实现中：
private final AtomicLong seed;private static final long multiplier = 0x5DEECE66DL;private static final long addend = 0xBL;private static final long mask = (1L << 48) - 1;protected int next(int bits) {long oldseed, nextseed;AtomicLong seed = this.seed;//这里有一把自旋锁，担保每次输出不相同do { oldseed = seed.get(); nextseed = (oldseed multiplier + addend) & mask; } while (!seed.compareAndSet(oldseed, nextseed));//这里截取的是高位比特值return (int)(nextseed >>> (48 - bits));}利用中的细节
实在到这里，随机数的天生问题我们基本上已经摸清楚了，既然我们知道了随机数的发生过程，实在就很随意马虎捉住重点，那便是随机数种子才是最为主要的，随机数只是一种天生过程，乃至说理解为一种可持续的hash办法也无不可。随机数的随机性完备来自于你随机数种子的随机性。以是在习气中，我们常常会利用当前毫秒韶光作为种子，而在java里的默认种子天生如下：
public Random() {this(seedUniquifier() ^ System.nanoTime());}private static long seedUniquifier() {// L'Ecuyer, \"大众Tables of Linear Congruential Generators of// Different Sizes and Good Lattice Structure\"大众, 1999for (;;) {long current = seedUniquifier.get();long next = current 181783497276652981L;if (seedUniquifier.compareAndSet(current, next))return next; }}private static final AtomicLong seedUniquifier= new AtomicLong(8682522807148012L);
可以看到，为了避免不传种子的情形涌现，java默认供应了一个种子，这里也有把自旋锁，加上随机数天生本身的那一把，可以看到随机数发生在多线程的情形是会导致竞争的（虽然损耗很低），以是在阿里巴巴开拓规约中会推举利用ThreadLocalRandom中的随机数来天生。如果你还记得上面的内容，还可以看出，这个种子本身也是个线性同余发生器发出的随机数，只不过分外一点，是b=0情形下的乘法发生器。这种发生器的周期必定无法满周期，但是对付天生“随机种子的因子”这种情形，够用。有点玄色诙谐的是，虽然这里堂而皇之的标明了这里的常数来源于Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure 这篇论文，但是实际上181783497276652981这个数并不存在于论文推举的表现最佳的因子中，看上去这里是一个Typo——数字开头少打了个1，但是实际上大家也知道了，一个“不那么完美”的分布实在也没那么有所谓。
随机数的天生事理并不繁芜，整体的实现也是非常简洁直白的，但这个中又包含了很多风雅的构思，终极达到了一种效率与结果的统一，技能的美感每每就分布在这些大略而不失落优雅的实现当中。当然，任何算法都有自己的适用范围，伪随机数在密码学意义上并不敷够安全，如果是对付随机性有着强需求的场景，我们应该利用其他的随机数天生方法。
关于公正的抽奖算法\"大众公正\"大众的维度提到抽奖，大家最先想到的，一定是，如何担保抽奖的公正性？而在开始这一部分前，笔者想先阐明一个不雅观点，公恰是多维度的，存在用户视角上的公正，客不雅观意义上的公正，算法上的公正等等多种意义上的公正。比如我们完备可以将一种名之为“抽奖”的东西概率设为100%，然后用库存限定抽中，这样所谓抽奖就退化为秒杀，在没有任何暗箱操作的情形下，我们可以说这是完备公正的，但是客不雅观上来说，也可以认为，对网较差、设备性能不佳或晚了一点参与的用户是相称不公正的。以是，反直觉的一点是，实在抽奖的算法也可以不那么公正，由于在任何一个拥有大量参与用户的活动中，用户的参与已经带来了大量的随机性上的因子，在没有提前看过参与用户的条件下，就算由一个值班同学一拍脑袋说本日是第4090位用户中奖，在某种程度上也是个相称公正的算法。以是，抽奖算法也是最随意马虎设计的算法——由于无论你产出的结果分布有多糟糕，也很难被“开盒”谩骂。实际上，在实践履历中，我们每每更要担保的是，结果的存在性和及时性，也便是说，无论你通过什么手段开出来奖，一定要在约定韶光内发到有效的用户手上——延迟与无效是工程上能表示出的最致命的问题。
真正该当看重的维度不过，除了公正性之外，抽奖实在还有很多其他维度的业务考量：1、抽奖机会限定，是只能单次参与？还是能一次性多注参与？还是能反复追加的多次参与？2、开奖机遇限定，是希望即时开奖？还是接管参与结束后定时开奖？3、奖品分布限定，是所有用户争夺唯一大奖？还是分一二三奖的奖品序列？还是瓜分红包或者积分的面额？大家有奖还是基本无奖？4、并发系统性能限定，同时来参与、来领奖的用户规模和qps如何？是否会影响演算韶光和接口延时？根据业务目标的不同，实际开拓中，紧张还是根据这些维度的特色实现特定的抽奖算法，以下列举几种常用的抽奖算法：
当抽奖的奖品粒度是个时
1）选中法在得知所有参与用户的情形下，我们可以每次直接天生1-n的随机数的办法，抽出中奖用户的编号。这种方法的毛病是有可能会造成碰撞，须要考虑如何剔除已经中过奖的用户。但是对付用户规模很大的活动来说，碰撞的概率极低，这种方法是最快速的。当然，我们上面也说过，这个方法无论利用的是若何天花乱坠的随机函数，并不比你拍脑袋写几个固天命字更高明，还不会碰着碰撞。闲鱼内的“百币夺宝”就采取的此方案，由于每个夺宝活动都是唯一的奖品，与用户约定了选中的号码规则，就可以方便快捷的找出中奖用户。
2）洗牌法洗牌法是对全体中奖名单进行一次shuffle，彻底乱序后留在特定位置的用户成为中奖用户。一样平常认为这种方法造成的I/O次数是最多的，但还是有很多手段可以进行优化的，比如分区处理。它也存在着最佳的运用处景，比如当一个活动大家都能中基本不同的奖品时。除此之外，它与选中法一样，履行的条件条件，也是必须得到全部的参与用户信息然后处理，对付实时想获知中奖信息或者想快速开奖的活动并不适用。
3）蓄池塘抽样法抽奖本身也可以视作一种抽样，那么蓄池塘抽样法便是一个非常适用的开奖法，它在参与人数未确定时就可以开始运作。我们掩护一个大小为奖品数量k的奖池，每个用户过来都有k/n的机会与奖池内一个中奖者进行交流，个中n为当前参与规模。可以证明，这样所有用户的中奖记录仍旧是均等的。抽样法实质上可以视作shuffle的一种优化，利用参与人数与中奖规模的差异，免去了一些无用的swap操作。但这个优化会带来两点不同，一来，活动时候掩护着中奖列表，可以让活动终止在任何时候并即刻开奖，无需等待至所有用户参与完毕后再演算开奖；二来，其容错性和鲁棒性会大大提升，很随意马虎并行化，在参与数量比较巨大的情形下，前后实行产生的概率变革非常眇小，而且中间任何一个用户操作出错，都不会对系统整体带来什么关键影响。闲鱼内的“回收抽锦鲤”就采取的此方案，对付各不相同的奖品列表，掩护大小为k的中奖者列表，终极留在列表内的便是中奖者。
瓜分类型的算法，比如瓜分现金红包或者积分，抽奖的粒度是分
4）瓜分红包算法最著名的自然是微信的瓜分红包算法，每个人瓜分的红包额度是这样打算的，先给每个人瓜分0.01元，然后加上rand(0~剩余均匀红包金额的两倍)，而末了一个人拿到剩余所有钱。这个算法可以担保大家瓜分的期望金额是相同的，但方差会越来越大，从而导致中最大奖的概率在各位置上是不同的。局限性在于，这个算法还是利用了一个先验信息，即参与人数n，须要发红包者预先选择好能领取的数量。其最大的上风是不须要等到所有参与信息都得到之后进行，可以实时开奖。但同时，最大的问题是由于强依赖了“红包剩余金额”这个信息，并发性会比较差，每每还是须要提前演算出结果，无法应对实时高并发的场景。闲鱼内的现金夺宝就采取了这种算法，但是由于参与规模特殊巨大，每每是将奖池与参与用户划分为多少批次再进行的开奖。
“不公正”但最好用的抽奖算法
5）概率法有时候我们希望用户能即时开出奖来，这个时候我们并不知道整场活动的全貌，只能靠一些先验的履历来决定当前用户的中奖概率，在发奖时实时由概率打算用户是否中奖，比如在奖池内提前规定A奖品中奖概率30%。但概率法并不公正。由于奖品数量有限，库存会花费光的缘故，对付固定中奖概率来说，后来的中奖概率是小于原来的中奖概率的，假设我们仅有一个奖品一个库存的话，每个人过来的中奖概率应该须要为
，才能担保用户无论什么时候参与概率都是相等的。可以看到，这个式子不但打算麻烦，会产生并发问题，居然还有规模限定。而有多个库存的情形下，情形将会更繁芜。实际场景中上我们还有很多其他成分的滋扰，特殊是业务本身的决策，比如我们并不肯望一开始就放出所有库存，中途才放出一点点库存。或者我们希望中奖库存是随着韶光过去均匀的花费掉的，这样我们就有更多的动机去调节这个本来就不公正的概率算法。以是说，概率法，是离客不雅观公正最远的算法。但是，我们一开始的谈论也解释，这部分的不公正只是存在于理论上，如果我们没有人为操控使特定人中奖，在任何用户都是黑盒的情形下，我们还是可以认为，这是公正的，由于用户没有机会判断得知，究竟这个活动的概率分布呈现什么样的情形，从而实现套利。用户只能通过一些履历化的谣言，比如“大额券总是在活动末期要冲量时才会放出”，或者“活动初期中奖概率更高”，来掌握参与机遇进行博弈。以是，这里的“不公正”打上了引号，事实是概率法由于其充分的运营空间和简明的规则，反而成为运用最广的抽奖办法。值得一提的是，概率法可以采取“概率保持”策略来应对部分奖品库存耗尽或者命中限中的情形，即该部分概率由其他奖品按概率比例再分配，也可以大略做到担保必中。
在工程实现上，以上的算法实在都可以在规模到一定程度时，进行分布式优化，将奖池和参与者分而治之；也完备可以在方法间相互结合，来达到想要的业务效果。
小结
