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

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

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

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

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

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

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

    另外,生成的随机串要求上面给错了。 是 [A-Z1-9]
        10
    chinvo   212 天前
    ksuid K-Sortable Globally Unique IDs 长度太长不符合楼主要求

    shortid 7-14 位,位数不固定

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

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

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

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

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

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

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

    random.randint(0, (26+26+10)**8)
        44
    nccer   212 天前   ♥ 1
    生成个池子,用的时候在里面选一个.
        45
    zhx1991   212 天前
    用上面说的某种碰撞很低但不是没有的随机策略

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

    插入重复数据会报错(非常罕见), 捕获相应异常重来
        46
    janxin   211 天前
    提前生成随机字母数字池,过滤清洗重复数据。这段时间不占用业务响应时间。使用的时候取出任意(从头部或尾部取出),销毁之。
        47
    w3sy   211 天前
    @Magnus1k 完全正确,数学问题,不用讨论了
        48
    janxin   211 天前
    刚刚说的还是比较业务偷懒了,其实技术一点的方法是设计一个映射算法即可。随便想了一个简单的:保证安全性前提下可以使用带校验位方式,可以占一个字母;为了混淆,可随机生成 2 位随机位,也可以用于后续 ID 的运算随机位可重复没关系,占用两个字节,不要求安全就随机三个字节;自增 ID 占用 5 位即可满足现有数量级需求,可按位或其他方式进行运算得到一个,还可以带入之前取到的随机数进行,凯撒之类的简单算法就可以。顺序还可以随机排序组合,能识别的前提下 XD
        49
    raptor   211 天前
    千万级就是小于 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。
        50
    mingl0280   211 天前
    SHA1/MD5 一个随机值(真随机值)取其中随意八位,然后查库有没有碰撞到的……
    其实讲道理这个碰撞在千万量级应该是不可能的……
        51
    chuhemiao   211 天前
    是时候上区块链思想了
        52
    lbp0200   211 天前
    从老外那,抄来的
    od -x /dev/urandom | head -1 | awk '{OFS="-"; print $2$3,$4,$5,$6,$7$8$9}'
        53
    pheyx   211 天前
    @honeycomb 你这个想法确实挺笨又 low 的
        54
    mengzhuo   211 天前
    总空间只有 = 218,340,105,584,896
    你的要求是 = 000,000,0xx,xxx,xxx

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

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

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

    长度不足 6 个,从 randomKey 随机取 6 个字符,插入 result 字符串 随机位置
        56
    SooHoo   211 天前
    @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();
    }
        57
    wwhc   211 天前
    md6sum -d32 用户 ID/随机数
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   实用小工具   ·   698 人在线   最高记录 3762   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 20ms · UTC 22:31 · PVG 06:31 · LAX 15:31 · JFK 18:31
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1