求唯一 ID 的生成算法

V2EX = way to explore

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

已注册用户请登录

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

已知一个数据库自增长的INT字段是唯一的，要把这个ID用散列算法映射到一个更大的空间里（比如6位数字），而且对于连续的INT，散列生成的结果离散性要好，比如1=》721370；2=》894357；3=》198222，而不是1=》100000；2=》200000，3=》300000，而且能保证不发生碰撞

散列

int

43 条回复 • 2014-05-21 17:50:48 +08:00

a591826944

2014-05-20 13:24:23 +08:00

保证不发生碰撞？。。。怎么可能

tabris17

2014-05-20 13:27:33 +08:00

@a591826944 我从小空间映射到大空间，不发生碰撞是可以的吧

loading

2014-05-20 13:28:10 +08:00 via Android

uuid

tabris17

2014-05-20 13:30:03 +08:00

uuid如果用数字表示实在是太长了

loading

2014-05-20 13:33:27 +08:00 via Android

你这个id会有几个程序生成？如果是可控的，前面加个前缀不就好了？

jybox

2014-05-20 13:36:54 +08:00

@tabris17 在数据库里 uuid 可以存成二进制类型，通常也是可索引可比较的

tabris17

2014-05-20 13:38:57 +08:00

@jybox 因为要作为URL的一部分，太长的话生成的二维码就比较“花”了

tabris17

2014-05-20 13:39:45 +08:00

@loading 加前缀不够“离散”哎，至少要看上去比较随机

tabris17

2014-05-20 13:40:50 +08:00

这么说吧，就是为了防止别人从ID来判断当前的最大记录，或者通过ID来枚举所有信息

xhacker

2014-05-20 13:42:04 +08:00

https://github.com/dylang/shortid

tabris17

2014-05-20 13:45:02 +08:00

@xhacker 这个是用随机数生成的，会碰撞的吧

wdd2007

2014-05-20 13:49:33 +08:00

md5

kamal

2014-05-20 13:50:12 +08:00

关注一下，同样有这个需求

tabris17

2014-05-20 13:50:26 +08:00

@wdd2007 MD5没法保证不碰撞哪

akira

2014-05-20 13:55:25 +08:00

自增id后面加个随机数

tabris17

2014-05-20 13:56:06 +08:00

@akira 这个很容易就被发现规律了吧

wdd2007

2014-05-20 13:56:14 +08:00

@tabris17 你可以测试下，测试100亿内的，不会有碰撞的。

tabris17

2014-05-20 13:57:05 +08:00

或者把自增ID的每位数字打散后插入随机数字符串里？

tabris17

2014-05-20 13:57:56 +08:00

@wdd2007 主要是MD5还是有点太长了

crab

2014-05-20 13:58:45 +08:00

当ID超过5位数呢？

loading

2014-05-20 13:59:14 +08:00 via Android

#矫情

tabris17

2014-05-20 14:01:56 +08:00

@crab 超过5位数，可以映射到10位数的空间里，投射到的空间大小没限制，但是也别太大了，MD5摘要128位，用数字表示要几十位了

jakwings

2014-05-20 14:03:17 +08:00

@tabris17 那就尽量找 ACID 支持比较完美的数据库软件，同时适量地进行人工分散。完美主义害人不浅，现在客服都没用了么……

tabris17

2014-05-20 14:05:29 +08:00

最后决定随机数+碰撞处理，就这样吧

feikeq

2014-05-20 14:08:45 +08:00

你可以试试用时间戳....

tabris17

2014-05-20 14:10:17 +08:00

@feikeq 时间戳精确到秒，还是会碰撞

tabris17

2014-05-20 14:11:44 +08:00

@feikeq 时间戳+自增ID的个位数，应该不会碰撞了吧，除非一秒内插入10条以上的记录

guoruei

2014-05-20 14:14:50 +08:00

时间戳+自定义ID，再来个按队列处理，妥妥的。

ganxiyun

2014-05-20 14:16:10 +08:00

RC2 64bits输出

tabris17

2014-05-20 14:16:27 +08:00

@guoruei 这……还是处理碰撞的成本低一点

ritksm

2014-05-20 14:16:52 +08:00

http://www.hashids.org/

feikeq

2014-05-20 14:17:01 +08:00

@tabris17 你可以再加个毫秒，我就是这样做的。

tabris17

2014-05-20 14:19:44 +08:00

@feikeq 也对，如果只要求10年内不发生碰撞，还可以把时间戳前面最高几位去掉，还能再短点

aisk

2014-05-20 15:43:27 +08:00

skip32

lu18887

2014-05-20 16:02:51 +08:00

只有时间是唯一的！过了这一刻就不会再来了！所以，好好利用时间来避开碰撞。另外，随机的度不控制好就容易出现碰撞！每一个时间都是平行时空！

lu18887

2014-05-20 16:06:13 +08:00

时间+自增ID+不可逆算法

tabris17

2014-05-20 16:11:52 +08:00

@aisk 这个貌似好用，谢谢

clippit

2014-05-20 17:27:51 +08:00

数字长一点没关系，加到 URL 里可以把它转换成36进制（a-z0-9）甚至62进制（A-Za-z0-9），这样就短了

aisk

2014-05-20 17:49:56 +08:00

@tabris17 http://meizhi.im/ 现在数据库还是存的自增，显示出来的是skip32+base36，应该和你的需求一致

banxi1988

2014-05-21 09:34:46 +08:00

找一个在第一象限单调递增的函数。把现在人id看成X
Y=func(x)，这样的Y就是你要的新的id.

tabris17

2014-05-21 11:04:17 +08:00

@aisk 非常感谢

tabris17

2014-05-21 11:05:32 +08:00

@aisk 网站很棒，已收藏

hedaode

2014-05-21 17:50:48 +08:00

可以把id简单加密（对称）下，这样既能保证id无明显规律，又能保持唯一性。例如：
id=htonl(id);//颠倒字节顺序
id=id^0x3f91b217;//异或加密，密码自定义