qq 群匿名昵称分配原理

[vzyw]

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

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

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

[hxsf]

hash 的结果是一定会重复的

所以，不如
1. 有个 存贮 所有名字的 set ，来一个人取出一个名字。可以使不重复
2. 每次生成新名字的时候看一下有没有人在用。

[Kilerd]

方法肯定是有的，按你的思路，我可以想到一种方案

昵称池 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]

@hxsf
@Kilerd
谢谢指导，我去研究一下

[jianzhiyao020]

利用 redis 的 set ，
需要加用户的时候，随机一个匿名放入该群的匿名 set ，速度和唯一性都有保障
为了实现每天不同匿名的效果，可以在这个 set 初始化的时候，设定 expire ，到这天的结束自动释放

[williamscorn]

谈一下自己的想法。

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

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

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

这样做的好处是，时间和空间复杂度是跟用户人数无关的，只跟组的个数和包的大小有关，是线性的，而组的个数和包的大小都是可控制的。