12 位纯数字兑换码的生成算法，如何尽可能保证不重复？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2905 天前的主题，其中的信息可能已经有所发展或是发生改变。

在只有 PHP 和 mysql 的环境下，做一个简单的发券、核销程序。其中券的**兑换码必须为 12 位数字**，数据量不会超过千万。如何生成不重复且乱序的券码？

最糟糕的方案是纯随机，然后到表里查一遍是否重复，重复则重新生成；不重复则插入

一个自认为好点的方案是用户 id 加一位随机数加截取时间戳后 x 位
例如用户 ID 为 123 ，则是 3 位，加随机数 4 位。此时剩余 8 位则截取时间戳后 8 位补上。重复概率应该就很低了

在尽可能不遍历表的情况下，还有更难以重复的生成算法吗？求不吝赐教

重复

生成

截取

算法

34 条回复 • 2016-12-15 15:09:57 +08:00

xi_lin

2016-12-09 19:14:53 +08:00

安利一波大数异或
https://segmentfault.com/q/1010000002430143
https://segmentfault.com/q/1010000002428203

debiann

2016-12-09 19:42:33 +08:00

纯随机重复的概率比你想的方法更低。用时间戳等于缩小了取值范围，增加了重复概率。

haython

2016-12-09 19:48:33 +08:00

说一下我的做法，仅限于每种券只允许一个用户领一张，比如“双 11 满 100 减 20 ”，“双 11 满 100 减 20 ”这种券生成一个不重复券号，给每个用户的都一样，验证的时候直接去这个用户的所有券里找有没有这个券号就行。

am241

2016-12-09 19:48:49 +08:00 via Android

固定前缀+递增 id 拼接字符串后对称加密

SuperFashi

2016-12-09 19:49:25 +08:00 via Android

单纯随机是不可能做到不碰撞的，就像你不可能造出一个物理骰子使第二次扔的数一定不等于第一次扔的数。
下手点有三个，查重、提取和生成。
查重指的你第一个想法的优化，即缩短查重时间。可以利用散列表来做，用 mysql 做可持久化存储。
提取指的预先将千万个号码随机出来。随机方式可以为每次随机一个起始值和步长，保证步长不超过某个值不低于某个值使最后不会大于 1e12 。之后只需要每次从表中随机提取出来一个数就好。
生成指的并非随机，而是利用现有信息，例如你的最后一个想法。还可以做比如拼接一个字符串为姓名+时间+乱七八糟的什么，做个哈希生成一个 12 位数。只要哈希函数好，碰撞概率基本为 0 。

debiann

2016-12-09 19:53:15 +08:00

@haython +1

用各种奇技淫巧改造随机数，都是白费功夫，只会影响原本随机算法的随机性。

k9982874

2016-12-09 20:38:34 +08:00 via iPad

预先生成一个不重复的兑换码表， lpush 到 redis
每次从 redis lpop 取个兑换码

性能最佳，且绝对不重复

xurubin

2016-12-09 21:45:12 +08:00

@am241 +1

jsjscool

2016-12-10 00:34:57 +08:00

MySQL 的自增 ID 就能解决你说的唯一性问题，而且是百分百唯一。还不到千万的数据， MySQL 的 IO 损耗可以忽略。

Valyrian

2016-12-10 07:38:11 +08:00

找一个千万级的质数 p ，然后费马小定理，加一个一一对应的 hash ？

doubleflower

2016-12-10 08:39:40 +08:00

> 最糟糕的方案是纯随机，然后到表里查一遍是否重复，重复则重新生成；不重复则插入

这种方法是最好的。

dangyuluo

2016-12-10 08:52:30 +08:00

我记得有个商业提供随机数生成的网站，用的是 alpha 粒子？

Septembers

2016-12-10 09:24:54 +08:00

生成一个随机数然后 Hash (比如 SHA2) 然后截取 10 个字节
检查数据库是否历史发行过如果没有就发布有则重新生成

Septembers

2016-12-10 09:25:41 +08:00

上面说错啦是 5 个字节转换成 integer 即可

dremy

2016-12-10 09:59:52 +08:00 via Android

@doubleflower 为啥不试试 Bloom Filter ？最佳的时间、空间效率啊，况且千万数据量就更合适了，比数据库里一条一条查不知道快到哪里去了。

realpg

2016-12-10 10:46:34 +08:00

@haython 并不是所有的优惠券系统都是每个用户只能用一张或者只能用几张的

@mokeyjay
我做过字符形式的，后来因为字符存储比较占数据库空间（数据库几个字符串占空间都考虑了你自己衡量一下商城量级吧不能透露更多了），最后变成存储纯数字，显示是字符串的（自己写了个一对一的算法把数字翻译成字符串），最后本质也是纯数字的优惠券

变更过多种生成方案，然后进行综合执行速度、还有重码分析，最后得出的方案还是单纯的 rand(1000000000000,9999999999999)的综合开销最低，远低于其他几种方案综合开销，重复率其实很低

另外，你说的没一个先 select 冲突之类的，说明你对 mysql 运用还不够精

直接用 INSERT IGNORE INTO 一大批，然后记录实际插入量，比计划的少的就是重复的，再次进行插入即可。

记录实际插入量，单点 MYSQL 可以用 AFFECTED ROWS ，我们这边是分布式的后面数据架构比较乱， AFFECTED_ROWS 不太好用，所以使用的方法是每次插入生成一个 job 做一个批次号，然后去查询这个批次已经生成多少，缺的继续补足

powergx

2016-12-10 11:42:54 +08:00 via iPhone

lz 建一个 pool 放好 id ，随机抽不就好了

Xrong

2016-12-10 14:28:57 +08:00

如果量不大的情况下楼主说的：『最糟糕的方案是纯随机，然后到表里查一遍是否重复，重复则重新生成；不重复则插入』就是最快最好的方法了。

Miy4mori

2016-12-11 01:37:37 +08:00 via Android

@jsjscool 同意

txlty

2016-12-11 10:20:47 +08:00

以前用这个。虽然是自己乱拼凑的方法。但经测试， 1000 万条数据重复率为 0 。随机生成则有 20+个重复。
你自己对比测试一下。
function testnum(){
$arr = explode(' ',microtime());
$num = $arr[0]*10000000000 + $arr[1] - $arr[0]*1000000;
$num = str_pad($num,11,mt_rand(0,9));
$num = str_pad($num,12,mt_rand(0,9));
return $num;
}

fthvgb1

2016-12-11 14:26:55 +08:00

uniqid()不可以么?

lygmqkl

2016-12-12 00:14:00 +08:00

我也来个思路， 12 位分成 8+4 ， 8 位账号＋ 4 位密码，前 8 位可以按照一定规则直接递增，因为你要求 1000w 这个量级，然后用组合的方式来做验证。

从加密学角度出发，可以使用浮动的账号密码位置模式，比如 8+4 ， 4+4+4 根据一定的规则把数字拆开，具体还是位数太短， 1000w 量级， 16-20 位会比较方便一点。

其实上面也有很好的思路
1. 预先生成不重复的方 redis ，如果在生产环境我会这样做， 1000w 应该很快
2. 记录单据和所有者的关系，这样做一个 link 就可以了。

zhiweiv

2016-12-12 02:17:00 +08:00 via Android

有索引的话，数据库查重速度很快的。数据库是树形存储的，查询单个记录秒查的，不是瓶颈。

lslqtz

2016-12-12 12:15:20 +08:00

@jsjscool 自增 ID 不是随机的，有被爆破的可能性。

lslqtz

2016-12-12 12:17:42 +08:00

我觉得随机数 8 位，时间戳取 4 位不错。
如果重复就改用备用算法重新生成，就按照最糟糕的纯随机？
然后循环检查是否重复

zacard

2016-12-12 13:14:03 +08:00

先说下是否是分布式部署。。。
其实可以不用查库直接生成不重复的。。。
基本原理推荐查考：[twitter 的 id 生成]( https://github.com/twitter/snowflake)

mokeyjay

2016-12-12 14:18:21 +08:00

@xi_lin 鄙人愚钝……看不是很懂，但是这个兑换码要求**乱序**且**纯数字**，你回复的这个看起来似乎不那么贴近需求，谢谢
@debiann 主要是希望利用算法尽可能减少查询的次数，谢谢
@haython 这项目后期要允许单用户多个券的，所以没有采用你所说的这种方法，谢谢
@am241 请问有哪种对称加密算法加密后的结果是 12 位纯数字的？我暂时还没听说过，请指教，谢谢
@SuperFashi 沃日 dalao 亲自回复，萌新瑟瑟发抖……我暂时不清楚如何哈希出 12 位纯数字来， dalao 可以给个思路吗？谢谢
@k9982874 那个……没有 redis
@jsjscool 自增 ID 不是乱序的，很容易被他人猜出来，作为兑换码的话绝对不行
@Valyrian 愿闻其详，看不是很懂，谢谢
@realpg 刚毕业的萌新给 dalao 跪下了。看不是很懂你所说的“ INSERT IGNORE INTO 一大批”，因为这个项目里券是用户主动领取的，也就是服务端被动发券，每次一张，动态生成券码这样的
@txlty 感觉原理上和纯随机没有本质区别，稍后试一下重复率，谢谢
@fthvgb1 不行，需要 12 位纯数字
@lygmqkl 你这里所说的账号可以理解为用户的 id 吗？
@zacard 看不懂嘤嘤嘤……

感谢各位的关注及回复

realpg

2016-12-12 14:45:05 +08:00

@mokeyjay
主动领取模型，都没有集中插入的负载，那不是更简单
INSERT IGNORE INTO 一个随机码
返回 affected_rows 是 1 就成功了不是 1 再生成一个往里插

kaneg

2016-12-12 16:48:43 +08:00

我觉的楼主自己的方案在产品的生命周期中出现重复的概率可以说为 0 ，如果这系统不是准备用上几百年，就没必要将简单的问题搞这么复杂。

koihik

2016-12-12 18:16:08 +08:00

这不是可以用 RSA 来做吗.
12 位数字就是万亿级别,那就取一百万左右的质数 2 个:
p = 997207 , q = 997219
则 n = p * q = 994433767333
然后取尽可能小的 d = 107 ,则 e = 9293754887

然后设自增 id 为 a,则有和 a 一一对应的 b
b = (a ^ d) % n

这样可以保证 id 从(2-994433767333)都不会重复

(2-10)的 ID 对应的卡号如下:
2 = 899396353970
3 = 781336638737
4 = 874206977826
5 = 756065937681
6 = 515322322794
7 = 538347577421
8 = 17370581741
9 = 812852944487
10 = 643487003155

xi_lin

2016-12-12 19:52:55 +08:00

@mokeyjay 大数异或肯定是乱序的
纯数字只要拿字母转数字就行，最基本就是直接变成对应的字母序。。建个映射嘛

SuperFashi

2016-12-12 22:26:08 +08:00

@mokeyjay 以 PHP 为例：
hexdec(substr(md5("Hello"), 5, 10))

Balthild

2016-12-13 14:31:38 +08:00 via Android

@debiann 不對吧，拼接上時間戳是縮小了可能重複的區域，而不是縮小了取值範圍。

akira

2016-12-15 15:09:57 +08:00

最糟糕的方案里面，检查部分工作可以由数据库自己做 unique 完成。

或者先生成足够数量，然后 distinct 到目标表