首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >用户ID生成唯一邀请码的几种方法

用户ID生成唯一邀请码的几种方法

作者头像
恋喵大鲤鱼
发布于 2021-12-06 03:17:19
发布于 2021-12-06 03:17:19
9.7K00
代码可运行
举报
文章被收录于专栏:C/C++基础C/C++基础
运行总次数:0
代码可运行

文章目录

1.需求描述

有一个业务需求,需要根据用户 ID(数值型 >=10000000)生成一个唯一的长 6 个字符的邀请码,用于邀请新用户注册。

2.需求分析

从业务需求和一般产品邀请码的使用体验上来看,邀请码有以下几个特点:

  • 不可重复:不用用户 ID 生成的邀请码是不同的;
  • 唯一确定:一个用户 ID 只能生成一个邀请码;
  • 是否可逆:是否需要通过邀请码反推对应的用户 ID 是什么。

本文将以 Golang 为例,给出根据用户 ID 生成唯一且不重复的邀请码的常见方法与实现示例。

3.字符集

首先需要确定组成邀请码的字符集,一般采用数字和英文大小写字母共计 62 个字符。如果长度时 6 的邀请码,那么空间大小 62^6 = 56,800,235,584,这是一个非常大的空间,足够用户量为亿级别的业务使用。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// AlphanumericSet 字母数字集
var AlphanumericSet = []rune{
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
	'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
}

当然,为什么提升用户体验,可以把 O、o、0、I、1 这五个形似易混淆的字符去掉,本文就不去了。

4.方法一:随机数+唯一性判断(不可逆)

使用用户 ID 作为种子初始化随机数发生器,随机生成字符集下标,取出对应的字符拼接成邀请码。

注意,这里会存在生日问题,随着已生成的邀请码数量的上升,发生碰撞的概率将会大大增加。

如果生成 100W 个邀请码,假设前 100W 一个都不重复,那么下一个重复的概率是((1/62)^6 * 100W)≈1/5.6W,冲突率已经到了在万分之一的概率,远大于直觉(1/62)^6

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// GetInvCodeByUID 获取指定长度的邀请码
func GetInvCodeByUID(uid uint64, l int) string {
	r := rand.New(rand.NewSource(int64(uid)))
	var code []rune
	for i := 0; i < l; i++ {
		idx := r.Intn(len(AlphanumericSet))
		code = append(code, AlphanumericSet[idx])
	}
	return string(code)
}

fmt.Println(GetInvCodeByUID(100000000, 6)) // uGkK9K
fmt.Println(GetInvCodeByUID(100000001, 6)) // UPFlHa
fmt.Println(GetInvCodeByUID(100000002, 6)) // keKZ01

缺点:

  • 唯一性判断引入第三方组件,增加依赖,降低了可靠性;
  • 在 >=99.99% 的情况下,唯一性判断都是通过的,浪费存储资源。

5.方法二:Hash+唯一性判断(不可逆)

对用户 ID 做 Hash(如 MD5)运算,获取散列值后取散列值的多个字节映射到字符集,然后组成邀请码。因为可能发生碰撞,所以需要做唯一性判断,比如借助 DB(Redis)来判断。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// GetInvCodeByUID 获取指定长度的邀请码
func GetInvCodeByUID(uid string, l int) string {
	// 因为 md5 值为 16 字节
	if l > 16 {
		return ""
	}
	sum := md5.Sum([]byte(uid))
	var code []rune
	for i := 0; i < l; i++ {
		idx := sum[i] % byte(len(AlphanumericSet))
		code = append(code, AlphanumericSet[idx])
	}
	return string(code)
}

// 示例
fmt.Println(GetInvCodeByUID("100000000", 6)) // btCcwX
fmt.Println(GetInvCodeByUID("100000001", 6)) // sxQ1mq
fmt.Println(GetInvCodeByUID("100000002", 6)) // swA3pk

缺点:

  • 唯一性判断引入第三方组件,增加依赖,降低了可靠性;
  • 在 >=99.99% 的情况下,唯一性判断都是通过的,浪费存储资源。

我们可以写一个单测来看下长度为 6 的邀请码,在字符空间为 62 ,一千万用户量下的碰撞率。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
func TestGetInvCodeByUID(t *testing.T) {
	sUID, eUID := 10000000, 20000000
	var md5ConCnt int  // md5 前 6 字节冲突次数
	var codeConCnt int // 邀请码冲突次数
	mHash := make(map[uint64]struct{})
	mCode := make(map[string]struct{})
	// 统计 1KW 个用户ID生成邀请码发生碰撞的次数
	t.Run("getConflictNumTestCase", func(t *testing.T) {
		for uid := sUID; uid < eUID; uid++ {
			sum := md5.Sum([]byte(strconv.Itoa(uid)))
			md5Value := uint64(sum[5]) | uint64(sum[4])<<8 | uint64(sum[3])<<16 | uint64(sum[2])<<24 |
				uint64(sum[1])<<32 | uint64(sum[0])<<40
			if _, ok := mHash[md5Value]; ok {
				md5ConCnt++
				codeConCnt++
				continue
			}
			mHash[md5Value] = struct{}{}
			code := GetInvCodeByUID(strconv.Itoa(uid), 6)
			if _, ok := mCode[code]; ok {
				codeConCnt++
				continue
			}
			mCode[code] = struct{}{}
		}
		if md5ConCnt != 0 || codeConCnt != 0 {
			t.Errorf("md5ConCnt=%v, codeConCnt=%v conRate=%v", md5ConCnt, codeConCnt, float64(codeConCnt)/float64(eUID-sUID))
		}
	})
}

执行单测命令go test -run TestGetInvCodeByUID$

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
--- FAIL: TestGetInvCodeByUID (13.01s)
    --- FAIL: TestGetInvCodeByUID/getConflictNumTestCase (13.01s)
        main_test.go:35: md5ConCnt=0, codeConCnt=900 conRate=9e-05
FAIL
exit status 1
FAIL    test    13.331s

可见前 6 个字节的散列值没有发生冲突,但是冲突率还是比较高的,在万分之一的级别。这种方式产生碰撞的原因是:虽然每个字节是不同值,但是对字符集大小取模后可能会相同,所以就有可能出现碰撞。随着用户量的增加,这里的碰撞概率会越来越高。

降低冲突率的办法是增加邀请码的空间,有两个办法:

  • 增加生成邀请码的字符空间;
  • 增加邀请码的长度。

6.方法三:进制法(可逆)

用户 ID 是唯一的,生成一个唯一的邀请码也是理所当然的。

因为我们的用户ID是一个数值,可以将其看作是一个 62 进制的数,每一位的值范围是 0~61,类似于 10 进制数的每一位的范围是 0~9,取 62 进制数位的每一位作为字符集的下标,高位用 0 补全,这样我们便可以采用除法取整与取模来实现。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// GetInvCodeByUIDUnique 获取指定长度的邀请码
func GetInvCodeByUIDUnique(uid uint64, l int) string {
	var code []rune
	for i := 0; i < l; i++ {
		idx := uid % uint64(len(AlphanumericSet))
		code = append(code, AlphanumericSet[idx])
		uid = uid / uint64(len(AlphanumericSet)) // 相当于右移一位(62进制)
	}
	return string(code)
}

// 示例
fmt.Println(GetInvCodeByUIDUnique(100000000, 6)) // ezAL60
fmt.Println(GetInvCodeByUIDUnique(100000001, 6)) // fzAL60
fmt.Println(GetInvCodeByUIDUnique(100000002, 6)) // gzAL60

缺点:

  • 连续用户ID生成的邀请码也是连续的,用户易输错;
  • 连续用户ID生成的邀请码也是连续的,规律性强,可以反推用户ID。

如果业务场景对这两个缺点可以接受的话,那么这个方法就足够用了。

7.方法四:进制法+扩散、混淆(可逆)

扩散 (Diffusion) 和混淆 (Confusion) 是 C. E. Shannon 提出的设计密码体制的两种基本方法,其目的是为了抵抗坏人对密码的统计分析。在分组密码的设计中,充分利用扩散和混淆,可以有效地抵抗坏人从密文的统计特性推测明文或密钥。扩散和混淆是现代分组密码的设计基础。

所谓扩散就是让明文中的每一位影响密文中的许多位,或者说让密文中的每一位受明文中的许多位的影响。这样可以隐蔽明文的统计特性。当然,理想的情况是让明文中的每一位影响密文中的所有位,或者说让密文中的每一位受明文中所有位的影响。

所谓混淆就是将密文与密钥之间的统计关系变得尽可能复杂,使得对手即使获取了关于密文的一些统计特性,也无法推测密钥。使用复杂的非线性代替变换可以达到比较好的混淆效果,而简单的线性代替变换得到的混淆效果则不理想。

使用扩散和混淆的方式可以对进制法进行改进。

如何扩散呢?

可以将个位和其它每一位作和后取余,即可把个位的变化传导到每一位。为了使结果看起来更随机,可以给每一位分配不同系数。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// GetInvCodeByUID 获取指定长度的邀请码
func GetInvCodeByUID(uid uint64, l int) string {
	var code []rune
	slIdx := make([]byte, l)
	for i := 0; i < l; i++ {
		slIdx[i] = byte(uid % uint64(len(AlphanumericSet)))               // 获取 62 进制的每一位值
		idx := (slIdx[i] + byte(i)*slIdx[0]) % byte(len(AlphanumericSet)) // 其他位与个位加和再取余(让个位的变化影响到所有位)
		code = append(code, AlphanumericSet[idx])
		uid = uid / uint64(len(AlphanumericSet)) // 相当于右移一位(62进制)
	}
	return string(code)
}

// 示例
fmt.Println(GetInvCodeByUIDUniqueNew(100000000, 6))	// eN2r08
fmt.Println(GetInvCodeByUIDUniqueNew(100000001, 6)) // fO4u4d
fmt.Println(GetInvCodeByUIDUniqueNew(100000002, 6)) // gP6x8i

从示例结果可以看出,相邻的用户ID对应的邀请码虽然不是连续的,但是每一位还是有很强的规律,左起第一位间隔一,第二位间隔二,第三位间隔三,以此类推。

如何隐藏这些规律呢?

我们可以对用户ID进行变换,比如放大或者加盐

放大可以对用户ID乘以一个与 62 互质的数,比如 3。这是因为根据循环群的性质:若 m 和 p 互质,则 m 可以作为整数同余加法群 [0, p) 的生成元,通过累加取模运算生成整个群,即 ( id * m ) % p 的结果包含 [0, p) 的所有整数,这保证了放大后结果的分布和原数据的分布同样均匀。

举个例子: 如果 p = 3,那么 [0, p) = {0, 1, 2},2 与 3 互质,那么我们可以通过 2 这个生成元生成整个群。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
(0*2) % 3 = 0 % 3 					= 0
(1*2) % 3 = 2 % 3 					= 2
(2*2) % 3 = (2 + 2) % 3 			= 1
(3*2) % 3 = (2 + 2 + 2) % 3			= 0
(4*2) % 3 = (2 + 2 + 2 + 2) % 3		= 2
(5*2) % 3 = (2 + 2 + 2 + 2 + 2) % 3	= 1
...

右侧的余数便组成了一个 3 阶循环群 {0, 1, 2}。3 阶指元素个数,循环指不管生成元 2 累加多少次,对 3 取余后结果都是在 {0, 1, 2} 中,出现循环的情况。

对 ID 放大后,我们也可以加个盐,可以是一个固定值,也可以是每个用户ID对应一个值,我这里取一个固定值 123456789。盐不要太小,太小缺乏隐蔽性;也不能太大,太大会占用过多用户 ID 的取值空间。比如位数可以和最大用户ID的位数保持一致。

放大和加盐后的效果:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const (
	PRIME1 = 3
	SALT  = 123456789
)
uid = uid*PRIME1 + SALT

// 示例
fmt.Println(GetInvCodeByUID(100000000, 6))	// dFchi3
fmt.Println(GetInvCodeByUID(100000001, 6))	// gIiqui
fmt.Println(GetInvCodeByUID(100000002, 6))	// jLozGx

可见,邀请码的规律性肉眼已经看不出来了。

然后是混淆,如何混淆呢?

混淆我用了P-box的方式,其实就是将数字洗牌。比如把 1234567 洗成 5237641。这样处理之后可以隐藏明文和密文之间的关系。洗牌的方式也很简单,选择一个和 CODE_LENGTH(本文中为 6)互质的数 PRIME2(可以选择 5),和数组角标相乘取余即可(原理同 PRIME1)。

最终的代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const (
	PRIME1 = 3 // 与字符集长度 62 互质
	PRIME2 = 5 // 与邀请码长度 6 互质
	SALT   = 123456789	// 随意取一个数值
)

// GetInvCodeByUIDUniqueNew 获取指定长度的邀请码
func GetInvCodeByUIDUniqueNew(uid uint64, l int) string {
	// 放大 + 加盐
	uid = uid*PRIME1 + SALT

	var code []rune
	slIdx := make([]byte, l)

	// 扩散
	for i := 0; i < l; i++ {
		slIdx[i] = byte(uid % uint64(len(AlphanumericSet)))                   // 获取 62 进制的每一位值
		slIdx[i] = (slIdx[i] + byte(i)*slIdx[0]) % byte(len(AlphanumericSet)) // 其他位与个位加和再取余(让个位的变化影响到所有位)
		uid = uid / uint64(len(AlphanumericSet))                              // 相当于右移一位(62进制)
	}

	// 混淆
	for i := 0; i < l; i++ {
		idx := (byte(i) * PRIME2) % byte(l)
		code = append(code, AlphanumericSet[slIdx[idx]])
	}
	return string(code)
}

// 示例
fmt.Println(GetInvCodeByUID(100000000, 6)) // d3ihcF
fmt.Println(GetInvCodeByUID(100000001, 6)) // giuqiI
fmt.Println(GetInvCodeByUID(100000002, 6)) // jxGzoL

8.小结

本文介绍了常见的通过用户 ID 生成唯一邀请码的几种方法,大家可以根据业务场景选择使用。

当然,本文介绍的方法可能并不满组某些业务场景的需求,比如用户ID并不是数值型,那么就需要我们根据具体场景用合适的方法解决问题。没有最好的方法,只要能解决问题就是好方法。

参考文献

趣谈唯一邀请码生成方法 简单的密码学生成唯一邀请码 记录使用 Golang math/rand 随机数遇到的坑 维基百科.混淆与扩散 CSDN.以模6加法群(Z6,+)认识循环群及其特点 维基百科.阶 (群论)

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/09/07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
数据科学 IPython 笔记本 7.10 组合数据集:合并和连接
Pandas 提供的一个基本特性,是内存中的高性能的连接和合并操作。如果你曾经使用过数据库,那么你应该熟悉这种类型的数据交互。它的主要接口是pd.merge函数,我们将看到几个在实践中如何工作的例子。
ApacheCN_飞龙
2022/06/03
1.1K0
Python自动化办公之Excel对比工具
今天我们继续分享真实的自动化办公案例,希望各位 Python 爱好者能够从中得到些许启发,在自己的工作生活中更多的应用 Python,使得工作事半功倍!
周萝卜
2022/04/06
9900
Python自动化办公之Excel对比工具
用 Python 帮财务小妹对比 Excel,小妹这次破防了。。。
由于工作当中经常需要对比前后两个Excel文件,文件内容比较多,人工肉眼对比太费劲,还容易出错,搞个Python小工具,会不会事半功倍
周萝卜
2021/11/08
5740
ElasticSearch 索引查询使用指南——详细版
  绿色表示一切正常, 黄色表示所有的数据可用但是部分副本还没有分配,红色表示部分数据因为某些原因不可用.
双面人
2019/04/10
3.8K0
ElasticSearch 索引查询使用指南——详细版
《Pandas Cookbook》第04章 选取数据子集1. 选取Series数据2. 选取DataFrame的行3. 同时选取DataFrame的行和列4. 用整数和标签选取数据5. 快速选取标量6
第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 第07章 分组聚合、过滤、转换 第08章 数据清理 第09章 合并Pandas对象 第10章 时间序列分析 第11章 用Matplotlib、Pandas、Seaborn进行可视化
SeanCheney
2018/10/10
3.8K0
天池大数据竞赛 Spaceack带你利用Pandas,趋势图与桑基图分析美国选民候选人喜好度
首先,这是一篇面向新人的教程导向的分析文章,(by the way其实我也是新手,从比赛开始才学的Pandas库,这也是我的一篇学习笔记),所以会包含很多函数的基础用法,解题思路等等, 流程会比较详细。
Spaceack
2021/01/05
1K0
不平衡数据集分类实战:成人收入数据集分类模型训练和评估
一个常用的例子是成人收入数据集,它涉及到社交关系、教育水平等个人数据,以此来预测成人的收入水平,判断其是否拥有5万美元/年的个人收入。数据集中个人收入低于5万美元的数据比高于5万美元的数据要明显多一些,存在着一定程度的分布不平衡。 针对这一数据集,可以使用很多不平衡分类的相关算法完成分类任务。
deephub
2020/05/09
2.4K0
不平衡数据集分类实战:成人收入数据集分类模型训练和评估
Python连接MIMIC-IV数据库并图表可视化
这种直接SQL提取方式很直接,但是不是最好的方式也不利于数据的进一步统计分析、可视化和预测分析, 所以我们这里讲解下:
科研收录
2023/12/12
4370
Python连接MIMIC-IV数据库并图表可视化
ElasticSearch初体验
构建在开源基础之上, Elastic Stack 让您能够安全可靠地获取任何来源、任何格式的数据,并且能够实时地对数据进行搜索、分析和可视化
小旋锋
2019/01/21
1.1K0
数据缺失、混乱、重复怎么办?最全数据清洗指南让你所向披靡
在拟合机器学习或统计模型之前,我们通常需要清洗数据。用杂乱数据训练出的模型无法输出有意义的结果。
机器之心
2020/04/22
2.9K0
数据缺失、混乱、重复怎么办?最全数据清洗指南让你所向披靡
《Pandas Cookbook》第02章 DataFrame基本操作1. 选取多个DataFrame列2. 对列名进行排序3. 在整个DataFrame上操作4. 串联DataFrame方法5. 在
In[1]: import pandas as pd import numpy as np pd.options.display.max_columns = 40 1. 选取多个DataFrame列 # 用列表选取多个列 In[2]: movie = pd.read_csv('data/movie.csv') movie_actor_director = movie[['actor_1_name', 'actor_2_name', 'actor_3_name
SeanCheney
2018/10/10
4.9K0
《Pandas Cookbook》第02章 DataFrame基本操作1. 选取多个DataFrame列2. 对列名进行排序3. 在整个DataFrame上操作4. 串联DataFrame方法5. 在
Elasticsearch7.6学习笔记1 Getting start with Elasticsearch
安装方法见: https://www.cnblogs.com/woshimrf/p/docker-es7.html
Ryan-Miao
2020/04/12
1.7K0
将文本特征应用于客户流失数据集
在我的上一篇博客“什么是嵌入,你能用它做什么”中,我谈到了嵌入可以把高维、非结构化的数据转换成低维的数值表示,可以用在各种机器学习模型中。
磐创AI
2021/09/03
1K0
用 Pandas 进行数据处理系列 二
获取行操作df.loc[3:6]获取列操作df['rowname']取两列df[['a_name','bname']] ,里面需要是一个 list 不然会报错增加一列df['new']=list([...])对某一列除以他的最大值df['a']/df['a'].max()排序某一列df.sorted_values('a',inplace=True,ascending=True) , inplace 表示排序的时候是否生成一个新的 dataFrame , ascending=True 表示升序,默认为升序,如果存在缺失的补值( Nan ),排序的时候会将其排在末尾
zucchiniy
2019/10/30
8.6K0
如何使用方差阈值进行特征选择
今天,数据集拥有成百上千个特征是很常见的。从表面上看,这似乎是件好事——每个样本的特征越多,信息就越多。但通常情况下,有些特征并没有提供太多价值,而且引入了不必要的复杂性。
deephub
2021/04/16
2.3K0
ElasticSearch
​ 保存在某个index下,某种type的一个数据document,文档是json格式的,document就像是mysql中的某个table里面的内容。每一行对应的列叫属性
OY
2022/03/20
1.3K0
ElasticSearch
COVID-19数据分析实战:数据清洗篇
2020 年全球的关键词非COVID19 莫属。虽然现在关于病毒的起源众说纷纭,也引起了不小的外交冲突。作为数据爱好者,还是用数据说话比较靠谱。
Ai学习的老章
2020/05/25
1.4K0
COVID-19数据分析实战:数据清洗篇
利用 Python 分析 MovieLens 1M 数据集
MovieLens数据集是一个关于电影评分的数据集,里面包含了从IMDB, The Movie DataBase上面得到的用户对电影的评分信息,详细请看下面的介绍。
JavaEdge
2022/11/30
1.8K0
利用 Python 分析 MovieLens 1M 数据集
一文搞懂:什么是Stacking堆叠?手把手带你搭建堆叠模型,附有python源码和数据集。
在该文章采用的是Lightgbm模型进行的分类预测,本次分享一个在竞赛中常用的策略,堆叠。
机器学习司猫白
2025/01/21
6540
一文搞懂:什么是Stacking堆叠?手把手带你搭建堆叠模型,附有python源码和数据集。
数据科学的原理与技巧 四、数据清理
数据以多种格式出现,并且在分析的实用性方面差别很大。尽管我们希望,我们所有的数据都以表格的形式出现,并且每个数值的记录都一致和准确,但实际上,我们必须仔细检查数据,找出最终可能导致错误结论的潜在问题。
ApacheCN_飞龙
2022/12/01
9640
推荐阅读
相关推荐
数据科学 IPython 笔记本 7.10 组合数据集:合并和连接
更多 >
目录
  • 文章目录
  • 1.需求描述
  • 2.需求分析
  • 3.字符集
  • 4.方法一:随机数+唯一性判断(不可逆)
  • 5.方法二:Hash+唯一性判断(不可逆)
  • 6.方法三:进制法(可逆)
  • 7.方法四:进制法+扩散、混淆(可逆)
  • 8.小结
  • 参考文献
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档