V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tabris17
V2EX  ›  问与答

求唯一 ID 的生成算法

  •  1
     
  •   tabris17 · 2014-05-20 13:17:06 +08:00 · 10372 次点击
    这是一个创建于 3825 天前的主题,其中的信息可能已经有所发展或是发生改变。
    已知一个数据库自增长的INT字段是唯一的,要把这个ID用散列算法映射到一个更大的空间里(比如6位数字),而且对于连续的INT,散列生成的结果离散性要好,比如1=》721370;2=》894357;3=》198222,而不是1=》100000;2=》200000,3=》300000,而且能保证不发生碰撞
    43 条回复    2014-05-21 17:50:48 +08:00
    a591826944
        1
    a591826944  
       2014-05-20 13:24:23 +08:00
    保证不发生碰撞?。。。怎么可能
    tabris17
        2
    tabris17  
    OP
       2014-05-20 13:27:33 +08:00   ❤️ 1
    @a591826944 我从小空间映射到大空间,不发生碰撞是可以的吧
    loading
        3
    loading  
       2014-05-20 13:28:10 +08:00 via Android
    uuid
    tabris17
        4
    tabris17  
    OP
       2014-05-20 13:30:03 +08:00
    uuid如果用数字表示实在是太长了
    loading
        5
    loading  
       2014-05-20 13:33:27 +08:00 via Android
    你这个id会有几个程序生成?如果是可控的,前面加个前缀不就好了?
    jybox
        6
    jybox  
       2014-05-20 13:36:54 +08:00
    @tabris17 在数据库里 uuid 可以存成二进制类型,通常也是可索引可比较的
    tabris17
        7
    tabris17  
    OP
       2014-05-20 13:38:57 +08:00
    @jybox 因为要作为URL的一部分,太长的话生成的二维码就比较“花”了
    tabris17
        8
    tabris17  
    OP
       2014-05-20 13:39:45 +08:00
    @loading 加前缀不够“离散”哎,至少要看上去比较随机
    tabris17
        9
    tabris17  
    OP
       2014-05-20 13:40:50 +08:00
    这么说吧,就是为了防止别人从ID来判断当前的最大记录,或者通过ID来枚举所有信息
    xhacker
        10
    xhacker  
       2014-05-20 13:42:04 +08:00   ❤️ 1
    tabris17
        11
    tabris17  
    OP
       2014-05-20 13:45:02 +08:00
    @xhacker 这个是用随机数生成的,会碰撞的吧
    wdd2007
        12
    wdd2007  
       2014-05-20 13:49:33 +08:00
    md5
    kamal
        13
    kamal  
       2014-05-20 13:50:12 +08:00
    关注一下,同样有这个需求
    tabris17
        14
    tabris17  
    OP
       2014-05-20 13:50:26 +08:00
    @wdd2007 MD5没法保证不碰撞哪
    akira
        15
    akira  
       2014-05-20 13:55:25 +08:00
    自增id后面加个随机数
    tabris17
        16
    tabris17  
    OP
       2014-05-20 13:56:06 +08:00
    @akira 这个很容易就被发现规律了吧
    wdd2007
        17
    wdd2007  
       2014-05-20 13:56:14 +08:00
    @tabris17 你可以测试下,测试100亿内的,不会有碰撞的。
    tabris17
        18
    tabris17  
    OP
       2014-05-20 13:57:05 +08:00
    或者把自增ID的每位数字打散后插入随机数字符串里?
    tabris17
        19
    tabris17  
    OP
       2014-05-20 13:57:56 +08:00
    @wdd2007 主要是MD5还是有点太长了
    crab
        20
    crab  
       2014-05-20 13:58:45 +08:00
    当ID超过5位数呢?
    loading
        21
    loading  
       2014-05-20 13:59:14 +08:00 via Android
    #矫情
    tabris17
        22
    tabris17  
    OP
       2014-05-20 14:01:56 +08:00
    @crab 超过5位数,可以映射到10位数的空间里,投射到的空间大小没限制,但是也别太大了,MD5摘要128位,用数字表示要几十位了
    jakwings
        23
    jakwings  
       2014-05-20 14:03:17 +08:00
    @tabris17 那就尽量找 ACID 支持比较完美的数据库软件,同时适量地进行人工分散。完美主义害人不浅,现在客服都没用了么……
    tabris17
        24
    tabris17  
    OP
       2014-05-20 14:05:29 +08:00
    最后决定随机数+碰撞处理,就这样吧
    feikeq
        25
    feikeq  
       2014-05-20 14:08:45 +08:00
    你可以试试用时间戳....
    tabris17
        26
    tabris17  
    OP
       2014-05-20 14:10:17 +08:00
    @feikeq 时间戳精确到秒,还是会碰撞
    tabris17
        27
    tabris17  
    OP
       2014-05-20 14:11:44 +08:00
    @feikeq 时间戳+自增ID的个位数,应该不会碰撞了吧,除非一秒内插入10条以上的记录
    guoruei
        28
    guoruei  
       2014-05-20 14:14:50 +08:00
    时间戳+自定义ID,再来个按队列处理,妥妥的。
    ganxiyun
        29
    ganxiyun  
       2014-05-20 14:16:10 +08:00
    RC2 64bits输出
    tabris17
        30
    tabris17  
    OP
       2014-05-20 14:16:27 +08:00
    @guoruei 这……还是处理碰撞的成本低一点
    ritksm
        31
    ritksm  
       2014-05-20 14:16:52 +08:00   ❤️ 1
    feikeq
        32
    feikeq  
       2014-05-20 14:17:01 +08:00
    @tabris17 你可以再加个毫秒,我就是这样做的。
    tabris17
        33
    tabris17  
    OP
       2014-05-20 14:19:44 +08:00
    @feikeq 也对,如果只要求10年内不发生碰撞,还可以把时间戳前面最高几位去掉,还能再短点
    aisk
        34
    aisk  
       2014-05-20 15:43:27 +08:00   ❤️ 1
    skip32
    lu18887
        35
    lu18887  
       2014-05-20 16:02:51 +08:00
    只有时间是唯一的!过了这一刻就不会再来了!所以,好好利用时间来避开碰撞。另外,随机的度不控制好就容易出现碰撞!每一个时间都是平行时空!
    lu18887
        36
    lu18887  
       2014-05-20 16:06:13 +08:00
    时间+自增ID+不可逆算法
    tabris17
        37
    tabris17  
    OP
       2014-05-20 16:11:52 +08:00
    @aisk 这个貌似好用,谢谢
    clippit
        38
    clippit  
       2014-05-20 17:27:51 +08:00
    数字长一点没关系,加到 URL 里可以把它转换成36进制(a-z0-9)甚至62进制(A-Za-z0-9),这样就短了
    aisk
        39
    aisk  
       2014-05-20 17:49:56 +08:00
    @tabris17 http://meizhi.im/ 现在数据库还是存的自增,显示出来的是skip32+base36,应该和你的需求一致
    banxi1988
        40
    banxi1988  
       2014-05-21 09:34:46 +08:00
    找一个在第一象限单调递增的函数。把现在人id看成X
    Y=func(x),这样的Y就是你要的新的id.
    tabris17
        41
    tabris17  
    OP
       2014-05-21 11:04:17 +08:00
    @aisk 非常感谢
    tabris17
        42
    tabris17  
    OP
       2014-05-21 11:05:32 +08:00
    @aisk 网站很棒,已收藏
    hedaode
        43
    hedaode  
       2014-05-21 17:50:48 +08:00
    可以把id简单加密(对称)下,这样既能保证id无明显规律,又能保持唯一性。例如:
    id=htonl(id);//颠倒字节顺序
    id=id^0x3f91b217;//异或加密,密码自定义
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1205 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 18:12 · PVG 02:12 · LAX 10:12 · JFK 13:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.