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

有没有什么生成随机不重复的唯一 ID 且足够短的好办法?

  •  
  •   kaiki · 2020-10-16 00:46:30 +08:00 · 9308 次点击
    这是一个创建于 1259 天前的主题,其中的信息可能已经有所发展或是发生改变。
    B 站的 bv 号那种就感觉可以,但是太长,我想生成只有几位的数字+大小写字母组合的随机字符表作为 ID,但是怕万一随机出以前出过的 ID
    67 条回复    2020-10-18 02:15:31 +08:00
    lxk11153
        1
    lxk11153  
       2020-10-16 00:57:57 +08:00   ❤️ 1
    搞一个 mysql 拿来自增 ID 不就好了
    opengps
        2
    opengps  
       2020-10-16 01:08:15 +08:00 via Android
    足够短跟容量是有直接制约的。首先得估算出最小的容量,然后研究下组成,然后计算出最小多长。

    我当初设计过一款唯一访问 key,思路你参考下:
    key 的参与构造字符,我用的是数字 10,大写字母 26,小写字母 26,虽然还可以用一部分单位符号但我没选,这样我的 key 只要 8 位字符就是 62 的 8 次方,就远远超过了 imei 的 15 纯数字位组合,而且还留下了巨大的空间,至于去重,我是每次随机生成完都检查一下是否已存在实现的,如果你对查重有性能要求的话需要重点改造下这个地方
    lpts007
        3
    lpts007  
       2020-10-16 01:19:51 +08:00
    @opengps 62^8 < 10^15
    ziseyinzi
        4
    ziseyinzi  
       2020-10-16 01:41:41 +08:00 via Android
    kaiki
        5
    kaiki  
    OP
       2020-10-16 01:57:45 +08:00
    @lxk11153 主要是想无规律,不可逆,如果位数都能保持一致就最好了
    meinjoy
        6
    meinjoy  
       2020-10-16 02:22:37 +08:00 via iPhone
    我得方法是截取 uuid,随机一个起始位置比如 2,想要 5 位的 id,就 uuid.substring(2,7)就行了
    kaiki
        7
    kaiki  
    OP
       2020-10-16 02:26:10 +08:00
    @meinjoy 和随机生成没什么区别,我打算随机生成几位数字大小写字母然后写入一个表中,绑定一个对应的数字 ID,查询的时候随机 ID 返回数字 ID,写入的时候查询随机 ID 是否存在,存在就重来一次生成过程。
    这样随机的 ID 就和数字 ID 没有任何规律可循了。
    594duck
        8
    594duck  
       2020-10-16 06:04:37 +08:00 via iPhone
    数据足够多的时候又要来问怎么查得快
    black11black
        10
    black11black  
       2020-10-16 06:50:53 +08:00 via Android
    我倒是很好奇,用 hash 确实是保证基本不重复了,冲撞了的情况该怎么办呢?
    Perry
        11
    Perry  
       2020-10-16 06:57:44 +08:00 via iPhone
    @black11black 先了解冲撞的概率有多少再谈需要不需要考虑这种情况
    lazydog
        12
    lazydog  
       2020-10-16 07:02:34 +08:00 via Android
    github 上应该一搜一大把吧,你可以搜搜看 unique id
    black11black
        13
    black11black  
       2020-10-16 07:03:51 +08:00 via Android
    @Perry 很有趣的回答,难道系统的设计者可以这么思考问题:因为冲撞是极小概率发生事件,所以不需要考虑?
    Cooky
        14
    Cooky  
       2020-10-16 07:09:52 +08:00 via Android
    预先生成检测重复,用的时候再取
    z7356995
        15
    z7356995  
       2020-10-16 07:11:21 +08:00 via Android
    数字 id 后端加密加盐一下,使用前再解密,应该比在表中查快一点
    opengps
        16
    opengps  
       2020-10-16 07:17:35 +08:00 via Android
    @lpts007 嗯,imei 用途中,有些位数不是数学里的所有数值都用的上,我是从实用角度足够用了,说的不严谨
    avenger
        17
    avenger  
       2020-10-16 07:19:03 +08:00 via iPhone
    Snowflake 了解一下
    AndyAO
        18
    AndyAO  
       2020-10-16 07:19:53 +08:00
    让我想起来了微软的全局标识符 GUID
    iConnect
        19
    iConnect  
       2020-10-16 07:28:03 +08:00 via Android   ❤️ 2
    要短,要快,还要随机,满足三个条件,最简单就是随机预生成放号码池。
    Perry
        20
    Perry  
       2020-10-16 07:56:52 +08:00 via iPhone
    @black11black 这不是很正常的一个 tradeoff ? GUID 也有极小概率能被碰撞,依据你的逻辑一个普通应用还要去做好这样的碰撞情况?
    0bit
        21
    0bit  
       2020-10-16 07:57:34 +08:00
    用 uuid v4 生成,然后转成 short uuid
    yuzo555
        22
    yuzo555  
       2020-10-16 08:06:32 +08:00
    楼主要求短,那么 hash 算法肯定重复概率高。
    又想要短,又想要无规律,只能用楼主自己在 #7 提出来的方案了。
    black11black
        23
    black11black  
       2020-10-16 08:11:39 +08:00 via Android
    @Perry 服了,大神当然都是不处理边际情况的,不用回了 block 了
    cmdOptionKana
        24
    cmdOptionKana  
       2020-10-16 08:22:00 +08:00
    第一考虑总量。另一个思路是考虑频率,比如,如果生成 ID 的间隔必然超过一秒,那用 timestamp 转 64 进制,再加个两位随机字符就可以了。
    cmdOptionKana
        25
    cmdOptionKana  
       2020-10-16 08:24:47 +08:00
    @black11black 这个 block 冤枉了,忽略小概率情况是很常见的做法,小规模系统连密码库的 nonce (要求唯一性) 都可以采用随机数。
    Perry
        26
    Perry  
       2020-10-16 08:25:14 +08:00
    @black11black 使用正确的情况下,大部分 hash 或者 GUID 的碰撞概率都是 astronomically low 的,如果你觉得这算是边际情况的话那你可以去处理。听到与自己观点不一样的声音就 block 对方这个行为有点巨婴了。
    black11black
        27
    black11black  
       2020-10-16 08:27:42 +08:00 via Android
    @cmdOptionKana 问题是你不做,真撞了怎么办呢,比如现在有个坏东西,故意给你传两份 md5 一样的 hexstring
    workg
        28
    workg  
       2020-10-16 09:47:21 +08:00
    Date.now().toString(36) + Math.random().toString(36).slice(2) ?
    cmdOptionKana
        29
    cmdOptionKana  
       2020-10-16 10:04:15 +08:00
    @workg 看情况,Date.now()精确到毫秒,如果一秒内并发生成很少 ID,则可以除以 1000 精确到秒,这样 ID 可以短些。另外 toString 最高只能转为 36 进制,如果用其他方法转为 64 进制,还可以再缩短 ID 长度。
    Maboroshii
        30
    Maboroshii  
       2020-10-16 10:19:23 +08:00
    snowflake 转 base32
    imdong
        31
    imdong  
       2020-10-16 10:19:32 +08:00
    先给楼主分享自己有过的两个类似的经验吧:

    15 年,公司接了一个电商买公交乘车码的东西,乘客手机购买后生成数字序列号给司机验证后可乘车。

    由于需要手输,所以数字要短,当时做过一些研究,楼主可以参考一下结论(一定量情况下,直接随机数和瞎搞胡搞的看起来随机的没差):

    ![image.png]( https://i.loli.net/2020/10/16/7wYaKPWrDjBNgkt.png)

    ![image.png]( https://i.loli.net/2020/10/16/qFEaijgyPBhs7rD.png)

    然后附上我前段时间搞得一个离线 CDK,里面又一些思路楼主可以参考:

    顺序生成,但是通过在二进制上一定的变换,可以得到看似随机的结果,但和原值一一对应,不重复。

    https://www.qs5.org/Post/680.html

    ( 15 年时我还很菜,别喷,虽然我现在依然菜,但谁喷我 ,我就画圈圈骂谁。)
    mcluyu
        32
    mcluyu  
       2020-10-16 10:25:26 +08:00
    uuidgen
    threebr
        33
    threebr  
       2020-10-16 10:29:30 +08:00 via Android
    感觉就是找一个有序数列到同样长度无序数列能够一一对应的函数,不行就像 19l 说的,预生成这样的对应列表
    newtype0092
        34
    newtype0092  
       2020-10-16 10:33:12 +08:00   ❤️ 3
    @black11black 你的每段代码都处理了因为 cpu 二极管电位异常导致计算结果不正确的异常了么?
    没有的话请 block 我,这种边际情况都不处理你不配和我们讨论~
    manhere
        35
    manhere  
       2020-10-16 10:51:32 +08:00 via Android
    hashids
    shuqin2333
        36
    shuqin2333  
       2020-10-16 11:09:49 +08:00
    short uuid
    gamexg
        37
    gamexg  
       2020-10-16 11:29:04 +08:00
    https://hashids.org/
    https://github.com/pjebs/optimus-go

    都是直接对 id 进行可逆加密的办法。
    另外也可以考虑直接用 aes 等方式加密。
    cmdOptionKana
        38
    cmdOptionKana  
       2020-10-16 11:29:45 +08:00
    @imdong 随机唯一码,如果不是事先生成,一般思路都是 时间+设备码+随机数,传统的 UUID 与现在流行的 snowflake 都是这个思路。如果不加入一些环境常数(比如随时间而变化、随设备而变化、随地点变化),那肯定不管怎么折腾都只是一个随机数(随机数+随机数=随机数)。
    cheng6563
        39
    cheng6563  
       2020-10-16 12:59:44 +08:00 via Android
    全随机是真的会重的,一般要带上时间,但这样就长了。可以预先随机一些 ID 放池子里,用一个取一个,只是这样比较慢
    imdong
        40
    imdong  
       2020-10-16 13:20:19 +08:00
    @cmdOptionKana 这个不是真正的随机,是可以用于数据库自增字段,然后对自增字段进行一定的处理,使其变得看起来像是随机数一样(结果定长)。

    而且连续两个数之间可能看不出规律(不知道处理方式的情况下)。
    a570295535
        41
    a570295535  
       2020-10-16 13:44:12 +08:00 via Android
    就用楼上那些方式,
    1 、用代码生成 100 万个 id 或更多
    2 、去重复并放进数据库
    3 、用户来一个取一个
    完成!
    随取随用,只有一开始你自己麻烦一次,这样不仅短还不会重复!
    unixeno
        42
    unixeno  
       2020-10-16 13:53:21 +08:00 via Android
    @black11black md5 这种已经能有快速碰撞算法的 hash 讨论这个就没意义了,你要用 sha256 还能撞吗?你要是现在能找到碰撞的 sha256,第一件事儿应该是去发个论文
    单论生日攻击,sha256 你要达到 10^-15 的碰撞概率需要 1.5*10^31 个数据,这个概率啥概念?大概是下一秒小行星撞地球然后人类灭绝的概率
    至于 10^31 啥概念?现在人类所有数码化保存的信息总量也才不到 10^22
    与其担心极小概率的碰撞,你不如先担心一下高能粒子打到你 CPU 上造成 bit 反转让你 hash 算错了
    kaiki
        43
    kaiki  
    OP
       2020-10-16 13:57:55 +08:00
    重复问题上,再次随机就行了,大家没必要那么严肃。
    那么是实时查写号码池,还是提前准备号码池呢?
    imn1
        44
    imn1  
       2020-10-16 14:01:23 +08:00
    如果你所说的场景,不必随机,只要时间序列做一个最小转换就行了,只要外部不知道转换算法,看上去就是随机的
    网站或者业务的一些 id,往往还包含了轻量的分类信息,这个就不是单纯随机就能完成的需求了
    popoer
        45
    popoer  
       2020-10-16 14:08:54 +08:00
    snowflake 不香吗
    wyz123723
        46
    wyz123723  
       2020-10-16 14:33:42 +08:00
    @black11black 你这问题就和有人真破解了 sha256 了怎么办
    wyz123723
        47
    wyz123723  
       2020-10-16 14:36:25 +08:00   ❤️ 1
    hash 碰撞的概率比一坨量子突然汇聚成一个特别喜欢你的美女的概率还要小
    jaylee4869
        48
    jaylee4869  
       2020-10-16 15:25:02 +08:00
    redis increment
    xuewuchen
        49
    xuewuchen  
       2020-10-16 15:50:30 +08:00
    GUID 吧。。
    killergun
        50
    killergun  
       2020-10-16 15:54:37 +08:00
    感觉你这个需求不就是短地址生成
    imhui
        51
    imhui  
       2020-10-16 16:00:42 +08:00
    如果是单机服务,线型同余 或许可以试一下
    azoon
        52
    azoon  
       2020-10-16 16:02:10 +08:00
    楼主要求不高,这么随便的话。就每次生成随机字符串时判断数据库是否存,存在就再次生成,就好了吧。
    我之前给别人做了个拍照预约系统的订单号就这么搞。
    xuanbg
        53
    xuanbg  
       2020-10-16 16:12:04 +08:00
    @imdong 我搞了个编码生成器,就是顺序生成,但是通过查表变换,可以得到看似随机的结果,但和原值一一对应,不重复。

    代码很简单:
    for(int i = len - 1; isEncrypt && i > 0; code = garble(code)) {
    --i;
    }
    private static String garble(String str) {
    int len = str.length();
    String first = len > 2 ? str.substring(0, 1) : "";
    String high = len > 3 ? str.substring(1, len - 2) : "";
    String low = String.valueOf(set.get(str.substring(len - 2, len)));
    return high + low + first;
    }
    Jooooooooo
        54
    Jooooooooo  
       2020-10-16 16:19:02 +08:00
    了解一下鸽笼原理
    tamer
        55
    tamer  
       2020-10-16 16:20:52 +08:00
    @wyz123723 那么请问有没有办法能加快这样的汇聚呢,很急,在线等
    xuanbg
        56
    xuanbg  
       2020-10-16 16:21:10 +08:00
    @xuanbg set 就是 00-99 的密码表,通过查表可以得到一个对应的预生成的随机值。加密后的数字理论上必需得到密码本、交换方法和交换次数才能还原加密前的数字,三者缺一不可。
    tabris17
        57
    tabris17  
       2020-10-16 16:21:50 +08:00
    hashids
    iyangyuan
        58
    iyangyuan  
       2020-10-16 16:37:45 +08:00
    预生成,最简单最可靠。
    假设长度 6 位,每一位可选[a-z][0-9],那么就是 20 亿的容量(不够用增加长度即可)。
    每次预生成,不能太多,也不能太少,那么我们可以控制前 2 位递增(00,01...zy,zz),每次生成固定前 2 位,后 4 位全量,这样就是百万级别的容量,应该够用一段时间,快消耗完时依此类推。
    这样就能满足生成快、读取快,不重复,足够短。
    TomVista
        59
    TomVista  
       2020-10-16 16:56:34 +08:00
    36 进制 id,每次随机一个数字进行随机递增,产生随机 id.
    TomVista
        60
    TomVista  
       2020-10-16 17:16:09 +08:00
    @TomVista 带大小写的话,就是 62 进制,8 位就是 2 百万亿,够用到天荒地老了,随机范围 1000 的话,还在 2 千亿级别.
    JCZ2MkKb5S8ZX9pq
        61
    JCZ2MkKb5S8ZX9pq  
       2020-10-16 19:07:35 +08:00
    看了楼上的思路,忽然想到固定排列组合+伪随机,自定义个种子,是不是也可以?
    xcatliu
        62
    xcatliu  
       2020-10-16 19:12:24 +08:00   ❤️ 1
    最近发现的一个 star 很多的 https://github.com/ai/nanoid,看了下功能很全,比如可以自定字典和长度:

    ```js
    import { customAlphabet } from 'nanoid'
    const nanoid = customAlphabet('1234567890abcdef', 10)
    model.id = nanoid() //=> "4f90d13a42"
    ```
    phithon
        63
    phithon  
       2020-10-16 19:26:14 +08:00
    看到楼上有提到 hashids 的了
    https://hashids.org/
    dreasky
        64
    dreasky  
       2020-10-16 20:27:41 +08:00
    black11black
        65
    black11black  
       2020-10-17 00:53:45 +08:00
    @wyz123723
    @unixeno
    @newtype0092
    不是概率小不小的问题,我觉得你作为设计者,当然不可能允许设计范围内存在一种小概率情况让程序不知道怎么处理,设计外情况当然不算在内,电位异常不是你能控制的,但你能控制的范围内你肯定要处理,所以我就问碰撞了怎么处理,楼上有人也说过了碰撞了就重随机这种简单答案,或者有人说用 sha256 可以基本避免恶意设计碰撞,这都是解决方案,你有方案就贡献方案,没方案就不回,没什么必要杠来杠去的。

    再说你真设计一个系统,你当然要考虑设计安全性,像我说的你如果完全没有碰撞处理方案,那随便一个人稍微有点恶意,传了经过设计的特殊字串,就能让你的程序抛出异常,这是完全有可能发生的情况而不是什么极小概率事件,显然设计过系统的都没法接受。也不知道现在杠精这么多都在杠什么,如果你们写程序的时候就真不加碰撞处理的代码,那我们也不用讨论什么了,道不同不相为谋,没必要
    Deepseafish
        66
    Deepseafish  
       2020-10-17 10:19:34 +08:00 via Android
    @black11black 「或者有人说用 sha256 可以基本避免恶意设计碰撞,这都是解决方案」
    这不按照你的逻辑还是没有考虑碰撞的情况吗?这不等于还是在说碰撞概率低,怎么就又是解决方案了。
    black11black
        67
    black11black  
       2020-10-18 02:15:31 +08:00
    @Deepseafish 尝试跟杠精讨论是我的错,block 了不用回了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4810 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 09:57 · PVG 17:57 · LAX 02:57 · JFK 05:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.