唯一随机数映射算法

业务数据表中，主键id往往被设置为自增，且在一些接口中会对外透出，因此外部可以直接拿到代表业务量的主键id，从中估计出业务规模。因此需要设计一套随机数生成算法，将主键id映射为随机数，使得外部无法从中窥探出业务规模

随机数生成算法需要具备如下特性：

• 唯一性。原数可映射成唯一的随机数，不能存在碰撞
  • 原数往往对应一个医生主键id、问诊单号、处方单号、病历单号等，都是有实际的业务含义且独立的，因此映射后的随机数不能存在碰撞
• 随机性。映射后的随机数不能轻易看出生成规则
• 高效性。算法不能过于复杂，消耗过多系统资源
• 可逆性。算法最好可逆，通过随机数反推回原数

下面以主键id在6位数范围内为例

确定映射后的六位数范围

999999的二进制： 1111 0100 0010 0011 1111
so映射后的二进制一定要比 1111 0100 0010 0100 0000小，否则就映射到7位数了

唯一随机数生成方案

种子异或+二进制的乱序移位

异或的优点

• 异或可将原数唯一映射成另一个数。唯一性是指，不同时存在a和a’，满足a^b=c，a’^b=c
• 异或是可逆的。即，a^b=c，知道b和异或结果c，可以反推出a=b^c。利用这一点可以实现算法可逆，通过随机数反推回原数

异或的缺点

• 种子相同，异或后的结果相同，因此只做异或运算还是容易被逆的，随机性不够
• 种子选取不慎，异或后的结果可能远大于原数
  • 在这个需求中，可能一个6位数异或得到一个7位数甚至更大，是完全有可能的。7位数截取6位，很容易造成随机数碰撞

对于缺点1，增加异或随机性的解法是；

• 多次异或，每次异或使用的种子不同
• 异或前，对原数的二进制做乱序移位，增加原数随机性
  • 需要保证乱序移位后，不超过一个预设的极大值。对于要生成随机6位数，就要保证异或后的随机数不超过999999

对于缺点2，需要通过分析推理出适合的种子集合，使得集合中的每个种子都能保证原数异或后在一个极大值范围内，对于要生成随机6位数，就要保证异或后的随机数不超过999999

确定异或种子和可乱序移位的位置

这里就要具体问题具体分析了

因为我们要生成6位随机数，所以999999是映射后的极大值，对它的二进制1111 0100 0010 0011 1111（共二十位）做如下推算

• 高四位全1，所以对高四位做移位操作不会改变原数范围
• 高四位全1，所以在高四位不全是1时，低十六位的范围必然是完整的全集。如果种子异或后高四位改变，必然存在原数高四位非全1，映射后全1的场景，而原数低16位是全集，种子异或后必然存在比999999的低16位0100 0010 0011 1111大的情况，所以推得种子高四位不能改变原数高四位，因此种子高四位只能全0
• 因为种子高四位全0，不改变原数高四位，所以在原数高四位是1111时，原数的高514位与种子的高514位异或后不能超过999999的高514位0100 0010 00。换句话说，0000 0000 000100 0010 00与种子的高514位xxxx xxxx xx异或后，最大只能为0100 0010 00。由此推得，种子的514位只能是全0。推送过程可以从高位到低位用反证法，过程不详述
• 低6位全1，所以对低6位做移位操作不会改变原数范围
• 低6位全1，所以种子的低6位对原数低6位异或运算后，不会导致生成的随机数超过999999，因此种子的低6位可任意

• 原数高4位和低6位可做乱序移位操作，共（4321）（65432*1）= 17280种选择
• 种子低6位可取任意的0或1，高14位全0，因此种子的个数为22222*2=64种选择

因此，基于不同的移位操作和不同的种子，一共可衍生出17280*64=1105920种唯一6位随机数映射结果集。如果对生成的随机数再使用该算法递归一次，就会生成1105920的二次方种随机数映射结果集，因此该算法可以实现完全无碰撞的六位唯一随机数，且每种随机数生成方式有三个可选变量来定制属于自己的一套随机化方案：

• 选择不同的种子
• 不同的乱序移位方式
• 不同的递归次数

如果我想实现7位、8位甚至更高的唯一随机数，这套算法通用吗？答案是肯定的，因为算法的核心就是要确定两点：

• 种子集，需要保证异或后的结果不超过位数的极大值（6位是999999，七位是9999999，以此类推…）
• 原数的二进制中，哪些位置可做乱序移位操作

这两点，可以借鉴我上述对于6位随机数的推演过程，不难得到其他位的随机数生成算法，这里我给出一般规律：

• 如果想异或后不超过极大值a，种子可任意0或1的位数需要与a的低位连续为1的位数严格对应，其余位必须全为0
• a的高位和低位连续1的位数，可做乱序移位操作来增加原数随机性，因为这不会改变原数的范围

算法流程图

基于唯一随机数的扩展能力

唯一随机码

如果能设计一套算法，保证六位唯一随机数可以唯一映射到一个固定位数的唯一随机码，既然我们已经实现了唯一随机数算法，那么就自然可以组合成唯一随机码的生成算法

数字转字符最常见的就是Base64算法，将二进制转成长串字符串，核心是维护一个字符集数组，将分隔后的每个二进制转为十进制，作为数组下标，得到映射的字符

因此，我们的随机数映射随机码可以借鉴Base64算法的思路，维护一个字符集数组，包含所有随机码的字符。问题的关键是如何处理六位数才能得到一组唯一映射的数组下标

假设字符集数组的长度为n，可以用六位数对n不断做取模运算：先取模，再做除运算去除小数，不断重复，直到六位数除尽。这么做的效果等同于将六位数转换成一个n进制数。对于两个不同的数，转换成的n进制数一定不同，且n进制数的每一位，必然在字符集数组的下标范围内（0~n-1）。因此，不同的数，一定能映射成不同的字符串

但这也带来一个问题，转换后的n进制数位数不同造成字符串长度不同。以32进制为例，像0~31，转为32进制的数与十进制相同，因此只能映射一个字符，如果是最大的六位数999999，可以映射四个字符

所以，当映射后字符串长度小于随机码的位数时，需要在映射后的字符串后面继续补充字符。补全需要的字符可以从字符集数组中随机取，因为不同的数映射的字符串已经不会相同了，所以补全需要的字符随机取是不会产生碰撞的

当然，这种数字映射唯一字符串的算法如果是可逆的，就可以反推出原数，适配更多的业务场景。不难发现，上述这种进制转换算法本身就是可逆的，不过如果存在随机补全的字符，就不可逆了。因此可以用一种取巧的办法，设置一个不在字符集里的哨兵字符，如果需要补位，先补哨兵字符。

以哨兵字符作为分界，左边的字符串就是类Base64算法映射的结果，转换为n进制数后，做逆运算（n进制数转为十进制数）即可反推出原数

因此，随机码生成策略可以总结为

将原数转为字符集长度n对应的n进制数，将它的每一位作为下标映射到字符集数组，得到映射后的字符串。如果长度不够，先补哨兵，再从字符集中随机取字符来补充到指定长度