孟秀哲　杨栋毅

摘 要： 针对海量随机数碰撞率实时检测的需求，利用随机数的随机特性，结合文件系统路径编码的方式，提出了一种类似于平衡B叉树的平衡检索森林的结构与算法。该方法避免了平衡B叉树的编程复杂性，检测效率非常高，有效地解决了海量随机数碰撞率检测因耗时量过大而难以在工程上快速实现的问题。

关键词： 随机数； 海量随机数； 碰撞率检测； 路径编码； 平衡检索森林

中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2016）08-44-03

Abstract： For the demand of real-time detection of massive random number collision rate， by using the stochastic properties of the random number and the file system path coding， a method of balanced search forest similar to the balanced B search tree is proposed. This method avoids the programming complexity of the balanced B search tree， and the detection efficiency is very high. It can effectively solve the problem that the collision rate detection of massive random number is too much time consuming to be quickly realized in engineering.

Key words： random number； massive random number； collision rate detection； path coding； balanced search forest

0 引言

随机数对于系统仿真[1]、信息通讯[2]、计算机随机模拟[3]、随机局部搜索[4]、密码研究[5]、随机验证码、彩票博弈、实验设计和随机抽样等领域或方面都有着十分重要的作用。随机序列的随机性，主要体现在两个方面，一是这个序列的产生是无法确定的，而且是不可以复现的；二是这个序列具有统计特性，当序列足够长时，其中的0和1的个数趋于相等，即具有0、1的均匀性。前者可以用碰撞率来测度，后者可以用均匀性来测度。碰撞率就是读取或产生一系列的32位随机数，统计随机双字的重复次数，最理想的结果就是碰撞次数为0。

海量随机数的数据量非常大，常常是边产生边检验，这就需要维持一张表，不断登记检测过的随机数，统计键值重复的次数。随着检测过程的不断加长，这张记录表会越来越大。如果采用顺序查找，则编程简单，但效率低下，平均查找次数约为（N+1）/2[6]，N为表中记录数。如果采用二分查找，则需要对顺序表进行排序，开销可能超过二分查找所节省的时间。……