首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xfund4
V2EX  ›  PHP

如何生成固定长度唯一随机字符串?

  •  
  •   xfund4 · 2018-01-15 17:41:45 +08:00 · 9330 次点击
    这是一个创建于 743 天前的主题,其中的信息可能已经有所发展或是发生改变。
    1. 字符串长度固定在 8 位[a-zA-Z0-9],仅要求千万数据量下保证唯一
    2. 不需要根据随机串解码出原值。
    3. 随机串不能被猜测出。
    4. 有自增 ID 可以使用,但是随机串不能有规律。
    第 1 条附言  ·  2018-01-16 14:53:26 +08:00
    谢谢各位提供的方案。

    预生成的方案应该是最合理的 能满足真随机和唯一。 不过暂时不会考虑预生成所以排除了。

    由于可能发生 批量生成的场景(抽奖活动预创建 1W 个兑换码)所以想避开检查碰撞的查询数据库操作。

    至于随机和唯一 两者的数学上的冲突 不在讨论范围内,我想表达的是 看似随机 无法被猜测这个要求。

    自增长 ID 辅助生成已经可以满足我的需求。 另外想了解下 如果没有依赖自增长 ID。 这种场景 常用的方案是哪些
    57 回复  |  直到 2018-01-17 05:00:43 +08:00
    maemual
        1
    maemual   2018-01-15 17:43:08 +08:00
    自增 ID 改成随机自增 x
    Sypher
        2
    Sypher   2018-01-15 18:00:56 +08:00
    丢 list 里啊,生成的时候检查下 list.contains(newStr)。
    Keyes
        3
    Keyes   2018-01-15 18:01:36 +08:00 via Android   ♥ 1
    生成订单号吗?参考京东做法,订单号有一个用户 id 作为 parent,随便猜,没有用,而且订单号可以做很短,客服和客户可以很容易识别
    bearice
        4
    bearice   2018-01-15 18:03:37 +08:00
    XTEA 加密
    xfund4
        5
    xfund4   2018-01-15 18:05:38 +08:00
    @Keyes 类似于 生成邀请码,兑换码。
    porrat
        6
    porrat   2018-01-15 18:07:12 +08:00
    sha1(random_chars)
    scriptB0y
        7
    scriptB0y   2018-01-15 18:07:20 +08:00
    uuid.uuid4()
    porrat
        8
    porrat   2018-01-15 18:07:57 +08:00
    看错了,以为是 40 位,可以再编码一次
    xfund4
        9
    xfund4   2018-01-15 18:08:27 +08:00
    @Sypher 类似兑换码的业务,数据库压力很低, 不想借助 redis 之类的服务。

    另外,生成的随机串要求上面给错了。 是 [A-Z1-9]
    chinvo
        10
    chinvo   2018-01-15 18:09:10 +08:00
    ksuid K-Sortable Globally Unique IDs 长度太长不符合楼主要求

    shortid 7-14 位,位数不固定

    hashids 同位数不固定(非传统意义 ID,而是将数字 ID 加密,可逆算法
    lululau
        11
    lululau   2018-01-15 18:10:51 +08:00
    邀请码兑换码肯定要存库的,这个直接随机就好了吧,随机完了查下库里是不是有这个数了,有的话就重新随机一个,一个 alphanum 字符可以编码 5 位,就按 4 位算,8 个字符可以编码 4 个字节了,4 个字节怎么还不够千万;还是说不知道怎么把一个整数转换成 alphanum 字符串?
    xfund4
        12
    xfund4   2018-01-15 18:11:27 +08:00
    @chinvo 由于数据量是可控的, 所以额外要求了生成的串 必须是 8 位 [A-Z1-9]
    honeycomb
        13
    honeycomb   2018-01-15 18:13:43 +08:00 via Android
    最笨的一个办法是用 csprng 导出二进制数,再转换成楼主需要的 36 进制
    tabris17
        14
    tabris17   2018-01-15 18:14:24 +08:00
    根据自增 ID,用 skip32 加密,然后 base62 编码
    moult
        15
    moult   2018-01-15 18:14:28 +08:00
    自增 ID 从 10 进制转到 62 进制。然后再追加随机字符串补全 8 位。这样可以不用去数据库校验是否重复,虽然前面几位有规律,但是后面是随机的,也能做到猜不出。
    http://php.net/manual/en/function.random-bytes.php
    chinvo
        16
    chinvo   2018-01-15 18:14:41 +08:00
    @xfund4 hashids 可以控制最短位数,如果你的数据(数值型 id )没有超过一定限制,那么你固定最短 8 位就可以保证输出的字符串时 8 位的。另外 hashids 字符串范围可控,在初始化的时候传入一个 string 就好。

    我也没有其他更好的方案了,你可以先试一下这个。
    xfund4
        17
    xfund4   2018-01-15 18:16:53 +08:00
    @moult 是的,我不希望再查一次数据库防碰撞。62 进制补足 8 位 这个随机补位有可能会造成重复啊。
    lululau
        18
    lululau   2018-01-15 18:19:11 +08:00
    要随机就免不了碰撞,要不想检查碰撞就不可能随机。。。
    Magnus1k
        19
    Magnus1k   2018-01-15 18:24:23 +08:00   ♥ 3
    不想碰撞就把所有符合的字符串全部生成了,然后随机挑一点出来用。
    daodao
        20
    daodao   2018-01-15 18:26:16 +08:00
    hash
    zjp
        21
    zjp   2018-01-15 18:31:46 +08:00 via Android
    我用的是时间戳加 4 位随机数,限制 8 个字符的话时间戳范围取小一点不知道够不够
    toan
        22
    toan   2018-01-15 18:44:48 +08:00 via Android
    @Magnus1k 赞同。不想碰撞的话,先生成,后随机挑。
    目前我这做过一个实例,先生成可用数据池数据,比如先生出 2 万,生成的时候进行唯一检验,使用的时候从该池子里随机挑选,增加使用取数的效率。当池子数据量低于某个阈值了,就重新生成补满池子。
    ylsc633
        23
    ylsc633   2018-01-15 18:48:45 +08:00
    用这个吧 hashids

    我用过,感觉还不错,没有应用到大项目里,所以 测不出性能消耗

    这个只需要你保管好自己的 salt 就行了!

    用的 这个包 https://github.com/ivanakimov/hashids.php

    具体实践 类似于 https://www.g9zz.com/post/6ravkEd7bx 这种吧 后面是定长的,且没有特殊字符,还可反解出来
    xfund4
        24
    xfund4   2018-01-15 18:58:20 +08:00
    谢谢诸位提供的方案, 因为有自增 ID 来为保证唯一。确实 hashids 的方案比较适合。

    @chinvo @ylsc633
    xfund4
        25
    xfund4   2018-01-15 18:59:52 +08:00
    @chinvo @Magnus1k @toan 如果没有自增 ID,并且不希望是预生成的。 有没有更好的办法呢
    l1093178
        26
    l1093178   2018-01-15 19:01:03 +08:00
    完全随机的话,到 sqrt(62 ^ 8) ~= 14, 000, 000 这个数量级就会出现冲突( https://zh.wikipedia.org/wiki/生日問題),所以说只能考虑除了完全随机之外的方案
    可以考虑用这个库: https://github.com/c2h5oh/hide
    Kilerd
        27
    Kilerd   2018-01-15 19:03:07 +08:00
    sha3
    moult
        28
    moult   2018-01-15 19:03:11 +08:00
    @xfund4 不想数据库查询的话,肯定要基于一个现有的 ID 来生成了。
    1、基于数据库的自增 ID 来生成,就我#15 给你的办法,比如 1-5 位由自增 ID 转到 62 进制,不够 5 位就补 0,后面三位随机生成来避免猜测性。这样肯定不会重复的。
    2、基于时间戳+用户 ID,也是将随机串的其中几位来保存时间戳和用户 ID。虽然无法避免统一秒同一用户发多个请求,但是后面还有随机串在,生成重复的概率可以忽略不计。另外时间戳没必要 1970 开始,就从 2018 开始就好了,这样时间戳会小很多。
    SunnyMeow
        29
    SunnyMeow   2018-01-15 19:05:24 +08:00 via iPad
    kaneg
        30
    kaneg   2018-01-15 19:08:04 +08:00 via iPhone
    我的一个不成熟的想法:A-Z,0-9,共 36 位,每个 ID8 位,则共有 36^8 种可能,而你的需求只要千万数量级,那么可以把总的取值范围等分为千万块,每一块大概有上万个值。使用的时候先用你的自增 ID 取一个块,然后在这一块里随机取一个值。这样的结果是每个值都不会重复,每个值是万分之一的随机,所以被猜测的可能性也很小
    xupefei
        31
    xupefei   2018-01-15 19:14:29 +08:00
    8 位千万数据量不算很大,直接 rand 然后查重就可以做到。
    查重有很多办法可以用。不过上千万的数据,普通的哈希表已经慢到不行了。可以用 bloom filter 和各种 data sketch 算法。
    toan
        32
    toan   2018-01-15 19:16:09 +08:00 via Android
    @xfund4 碰撞问题没有好的办法避免。
    geelaw
        33
    geelaw   2018-01-15 19:17:27 +08:00
    用安全的随机置换即可。
    owenliang
        34
    owenliang   2018-01-15 19:35:40 +08:00 via Android
    随机生成字节系列,转 16 进制,去重保存
    renyijiu
        35
    renyijiu   2018-01-15 19:40:25 +08:00
    时间戳加一定长度字符串
    viko16
        36
    viko16   2018-01-15 19:49:45 +08:00
    实际应用上还得考虑把 "iIl1" 这类不易辨识的字母组合移除..
    innoink
        37
    innoink   2018-01-15 20:08:20 +08:00
    既然已经知道总数,那么预先生成存起来,然后随用随取
    innoink
        38
    innoink   2018-01-15 20:09:25 +08:00
    检查的时候用 bloomfilter
    qfdk
        39
    qfdk   2018-01-15 20:35:32 +08:00 via iPhone
    md5 (数据+ 随便)取指定长度
    julyclyde
        40
    julyclyde   2018-01-15 20:36:29 +08:00
    固定长度就不可能唯一啊
    yingfengi
        41
    yingfengi   2018-01-15 21:05:34 +08:00
    非程序员,写过一些小东西,我记得 php 有个获取当前时间戳生成一个 ID 的函数还是啥,生成的这个 ID 会是毫秒级的,反正是这么一个东西,之前用过,生成 ID 后 md5 作为一个 key,当初是这样只玩的。
    你可以,md5 之后随机取 8 位啥的
    以上,仅供参考
    billlee
        42
    billlee   2018-01-15 21:52:46 +08:00
    block_ciper(counter())
    fuyufjh
        43
    fuyufjh   2018-01-15 21:56:46 +08:00
    最科学的方法:把输出看成一个(26+26+10)进制、8 位的数

    random.randint(0, (26+26+10)**8)
    nccer
        44
    nccer   2018-01-15 22:41:01 +08:00   ♥ 1
    生成个池子,用的时候在里面选一个.
    zhx1991
        45
    zhx1991   2018-01-16 00:13:40 +08:00
    用上面说的某种碰撞很低但不是没有的随机策略

    然后在库里把这个字段设成唯一

    插入重复数据会报错(非常罕见), 捕获相应异常重来
    janxin
        46
    janxin   2018-01-16 11:05:06 +08:00
    提前生成随机字母数字池,过滤清洗重复数据。这段时间不占用业务响应时间。使用的时候取出任意(从头部或尾部取出),销毁之。
    w3sy
        47
    w3sy   2018-01-16 11:28:56 +08:00
    @Magnus1k 完全正确,数学问题,不用讨论了
    janxin
        48
    janxin   2018-01-16 11:32:26 +08:00
    刚刚说的还是比较业务偷懒了,其实技术一点的方法是设计一个映射算法即可。随便想了一个简单的:保证安全性前提下可以使用带校验位方式,可以占一个字母;为了混淆,可随机生成 2 位随机位,也可以用于后续 ID 的运算随机位可重复没关系,占用两个字节,不要求安全就随机三个字节;自增 ID 占用 5 位即可满足现有数量级需求,可按位或其他方式进行运算得到一个,还可以带入之前取到的随机数进行,凯撒之类的简单算法就可以。顺序还可以随机排序组合,能识别的前提下 XD
    raptor
        49
    raptor   2018-01-16 11:53:40 +08:00
    千万级就是小于 1 亿,对应二进制不到 27 位。
    A-Z1-9 8 位,相当于 35 进制的 8 位,对应二进制 41 位多点。
    生成一个 14 位的随机数,左移 27 位,和 ID 组成一个 41 位二进制数。
    自己设置一个密钥,再用 RC4 加密这个 41 位二进制数。
    最后把这个加密后的二进制数转为 35 进制的 A-Z1-9。

    这样可以保证唯一,猜不到,不用查数据库三个要求。

    解出 ID 的方法:
    字符串转成二进制,RC4 解密,把 41 位二进制最高 14 位填充成 0,再补 23 位 0 填充成 64 位,转成整数即是 ID。
    mingl0280
        50
    mingl0280   2018-01-16 12:23:36 +08:00
    SHA1/MD5 一个随机值(真随机值)取其中随意八位,然后查库有没有碰撞到的……
    其实讲道理这个碰撞在千万量级应该是不可能的……
    chuhemiao
        51
    chuhemiao   2018-01-16 13:10:45 +08:00
    是时候上区块链思想了
    lbp0200
        52
    lbp0200   2018-01-16 15:10:28 +08:00
    从老外那,抄来的
    od -x /dev/urandom | head -1 | awk '{OFS="-"; print $2$3,$4,$5,$6,$7$8$9}'
    pheyx
        53
    pheyx   2018-01-16 16:16:10 +08:00
    @honeycomb 你这个想法确实挺笨又 low 的
    mengzhuo
        54
    mengzhuo   2018-01-16 17:10:27 +08:00
    总空间只有 = 218,340,105,584,896
    你的要求是 = 000,000,0xx,xxx,xxx

    正好对半开
    把时间填在前面,唯一 id 填到后面,然后随便位移,置换,异或一下就好了(反正没人会真的看你的算法)
    SooHoo
        55
    SooHoo   2018-01-16 17:54:33 +08:00
    这两天公司业务需求,提现码(不能重复,不能被猜测到,不能太长,最多 6 位)
    大概说下生成规则

    先将数字小写字母大写字母打乱
    然后左边取 20 个字符作为 randomKey
    剩下右边给 numKey

    将用户 id 进行 numKey.length 进制换算,生成字符串 result

    长度不足 6 个,从 randomKey 随机取 6 个字符,插入 result 字符串 随机位置
    SooHoo
        56
    SooHoo   2018-01-16 17:57:40 +08:00
    @SooHoo

    接上 ,没发完 不小心发出来了
    ----------
    大概思想就是把 uid 放入到串里面,然后,随机插入 不包括 uid 的字符

    为了让用户稍微难些分析。就加入了进制转换,然后随机插入位置。

    可能有 BUG,欢迎指正。哈哈

    -----------------------------------------



    /**
    *
    * @param count 字符个数
    * @param uid 用户 id
    * @return
    */
    public static String randomString(int count, int uid) {

    String randomKey = CODE.substring(0, 20);
    String numKey = CODE.substring(20);

    StringBuilder result = new StringBuilder();

    while (uid > 0) { //转成 numKey.length 进制
    int p = uid % numKey.length();
    result.append(numKey.substring(p, p + 1));
    uid = uid / numKey.length();
    }

    if (result.length() < count) {//字数不足,随机字符补全
    Random random = new Random();
    int size = count - result.length();
    for (int i = 0; i < size; i++) {
    int r = random.nextInt(randomKey.length()); //随机取一个字符
    int p = random.nextInt(result.length() + 1);//随机一个位置
    result.insert(p, randomKey.substring(r, r + 1));
    }
    }
    return result.toString();
    }
    wwhc
        57
    wwhc   2018-01-17 05:00:43 +08:00
    md6sum -d32 用户 ID/随机数
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2334 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 35ms · UTC 14:07 · PVG 22:07 · LAX 06:07 · JFK 09:07
    ♥ Do have faith in what you're doing.