V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
vzyw
V2EX  ›  程序员

qq 群匿名昵称分配原理

  •  
  •   vzyw · 2016-12-28 11:31:10 +08:00 · 3485 次点击
    这是一个创建于 2703 天前的主题,其中的信息可能已经有所发展或是发生改变。

    请问类似 qq 群里匿名昵称分配是用什么算法的?

    要做聊天室,假设聊天室内每个用户用户名都不相同,每个聊天室人数上限是 10 人,服务器上有 10 个昵称 nicknames[10]可以选择(nicknames 一个数组)。我的想法是根据用户名映射到一个昵称上,比如用户名是 abc 的用户对应 nicknames[2],用户名是 cbd 的用户对应 nicknames[5]。然后这个哈希函数可以根据一个种子变换出不同的映射值,比如用时间做种子,今天 abc 对应的是 2 ,明天 abc 对应的是 4 。

    简单的说就是通过一个哈希函数映射出 1-10 的数 ,这样的哈希函数能设计出来吗?

    5 条回复    2016-12-29 00:38:04 +08:00
    hxsf
        1
    hxsf  
       2016-12-28 12:18:51 +08:00
    hash 的结果是一定会重复的

    所以,不如
    1. 有个 存贮 所有名字的 set ,来一个人取出一个名字。可以使不重复
    2. 每次生成新名字的时候看一下有没有人在用。
    Kilerd
        2
    Kilerd  
       2016-12-28 13:04:46 +08:00
    方法肯定是有的,按你的思路,我可以想到一种方案

    昵称池 nicknames , 用户 Hash ( hash 算法自己选择)

    然后选择一个随机数 g, 使 gcd(g, len(nicknames)) = 1 // 这里是为了保证可以产生一个长度跟 nicknames 一样的置换

    然后 用户的昵称就可以是 nicknames[g^(用户 hash )]

    这里有可能 产生同一个昵称 , 当 g^(用户 1 hash) = g^(用户 2 hash) 时, 也就是 hash 模= hash (mod len(nicknames)) 时。

    为了避免这个情况,两种解决方法:

    1 。 hash 值 是要小于 或者近似等于 len(nicknames) , 或者用户数量很少的时候,出现重复的概率很低(这里讨论大量用户时)

    2 。 用一个已使用的昵称池来记录已使用的昵称, 如果已经使用了, 那么就执行 nicknames[g^(用户 hash + 1 )]



    PS: 这里用到 幂快速模算法。自己百度。


    KEYWORD: 群、 置换(轮换)、 gcd 、 幂快速模算法
    vzyw
        3
    vzyw  
    OP
       2016-12-28 13:29:00 +08:00
    @hxsf
    @Kilerd
    谢谢指导,我去研究一下
    jianzhiyao020
        4
    jianzhiyao020  
       2016-12-28 13:53:00 +08:00
    利用 redis 的 set ,
    需要加用户的时候,随机一个匿名放入该群的匿名 set ,速度和唯一性都有保障
    为了实现每天不同匿名的效果,可以在这个 set 初始化的时候,设定 expire ,到这天的结束自动释放
    williamscorn
        5
    williamscorn  
       2016-12-29 00:38:04 +08:00
    谈一下自己的想法。

    首先,腾讯的 qq 群是各有人数上限的, 50 人群, 100 人群, 200 人群, 500 人群这种。

    不妨把不同人数上限的群对应到不同的昵称组,每个昵称组内放 很多个 该组人数上限 的昵称包,昵称包里昵称的个数等于这个组人数的上限。
    群与昵称包的对应关系可以直接用 群编号%包个数 一一对应。
    而在每个群里的用户,直接按序对应昵称就行了。

    那么每天,只要先对昵称组内 shuffle 一下昵称包,再对每个昵称包 shuffle 一下昵称,每个群的每个人昵称就不一样了。

    这样做的好处是,时间和空间复杂度是跟用户人数无关的,只跟组的个数和包的大小有关,是线性的,而组的个数和包的大小都是可控制的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1312 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 70ms · UTC 17:51 · PVG 01:51 · LAX 10:51 · JFK 13:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.