趣谈唯一邀请码生成方法

趣谈唯一邀请码生成方法

前段时间项目上需要生成唯一邀请码!嘿嘿,多简单的一件事,心里就已默默将代码写了一遍。但小小的邀请码生成却也小有乾坤,这就是后话了。

一、最简单的实现

很多人 肯定都和我一开始一样!嘿嘿,这还不简单,26个字母+10个数字,去掉容易混淆的,O、0、I、1等字符就剩下32个,

        /**
         * 随机字符串
         */
        private static final char[] CHARS = new char[] {'F', 'L', 'G', 'W', '5', 'X', 'C', '3',
            '9', 'Z', 'M', '6', '7', 'Y', 'R', 'T', '2', 'H', 'S', '8', 'D', 'V', 'E', 'J', '4', 'K',
            'Q', 'P', 'U', 'A', 'N', 'B'};

然后再生成随机的六个重复的数字,对应着CHARS中的数字下标,邀请码生成搞定

            Random random = new Random();
            List<Character> list =  random.ints(0,32)
                .distinct().limit(6).boxed().map(t -> CHARS[t]).reduce().collect(toList());

好啦,邀请码生成好了。你还要不重复是吧,OK!没问题,我们把邀请码保存到缓存里面,例如redis。每次新生成的邀请码都先去缓存判断下是否存在,如果已经存在则再生成一个,直到找到合适的。 功能完成。喝下午茶去。。。。

思考 :这种实现是否真的最佳实现了呢? 至少存在以下一些问题

  • 唯一性判断需要通过缓存,引入第三方组件,并且消耗内存资源
  • 在99.999%的情况下,缓存判断是否存在都是 FALSE 的,可以说是一种浪费
  • 用户与邀请码的对应关系需要记录,如果数据库查询的话,至少需要在邀请码字段上加个索引,又是要消耗资源

那么我们有其它办法来解这个问题吗?

二、数学和密码学来实现

前提 :存在唯一的标识,例如给用户生成邀请码,那么用户id就是唯一标识(id在任何情况下都不会重复)。

那么我们首先想到的是根据唯一的id,是使用算法来生成。

       /**
         * 生成邀请码
         *
         * @param id 唯一的id主键
         * @return code
         */
        String gen(Long id) {
            //进行补位
            id = id * PRIME1 + SLAT;
            //将 id 转换成32进制的值
            long[] b = new long[CODE_LENGTH];
            //32进制数
            b[0] = id;
            for (int i = 0; i < CODE_LENGTH-1; i++) {
                b[i + 1] = b[i] / CHARS_LENGTH;
                b[i] = b[i] % CHARS_LENGTH;
            }
            b[5] = (b[2] + b[3] + b[4]) * PRIME1 % CHARS_LENGTH;
            StringBuilder buffer = new StringBuilder();
            Arrays.stream(b).boxed().map(Long::intValue).map(t -> CHARS[t]).forEach(buffer::append);
            return buffer.toString();
        }

大概就是像上面代码一样,先将id扩大,然后再转换成32进制的数。为啥是32进制呢,因为 CHARS 里面是32个char,那么32进制正好对应 CHARS 的下标。

好了,基于算法根据id来生成邀请码就完成了。然后再逆向下算法,就可以根据邀请码来还原成用户id,找到是哪个用户的了。

YEAH、YEAH!任务完成

然后代码一运行

  public static void main(String [] args){
        for(long id=10000L;id<10020L;id++){
            String code = InviteCode.instance().gen(id);
            System.out.println("code:"+code);
        }
  }
code:HASCL6
code:DASCL6
code:JASCL6
code:QASCL6
code:AASCL6
code:FNSCL6
code:WNSCL6
code:CNSCL6
code:ZNSCL6
code:7NSCL6

连续的 id 产生的邀请码是惊人的相似,后四位是完全相同的!这样如果有心用户发现这个规律后,就有可能破解邀请码的生成算法。

三、再进一步

之前有说过密码学,密码学里面有两个重要概念,就是扩大和混淆。既然后四位如此的相似,那么我们希望能够扩大后四位的差异。

       /**
         * 生成邀请码
         *
         * @param id 唯一的id主键
         * @return code
         */
        String gen(Long id) {
            //补位,并扩大整体
            id = id * PRIME1 + SLAT;
            //将 id 转换成32进制的值
            long[] b = new long[CODE_LENGTH];
            //32进制数
            b[0] = id;
            for (int i = 0; i < CODE_LENGTH - 1; i++) {
                b[i + 1] = b[i] / CHARS_LENGTH;
                //扩大每一位的差异
                b[i] = (b[i] + i * b[0]) % CHARS_LENGTH;
            }
            b[5] = (b[0] + b[1] + b[2] + b[3] + b[4]) * PRIME1 % CHARS_LENGTH;

            //进行混淆
            long[] codeIndexArray = new long[CODE_LENGTH];
            for (int i = 0; i < CODE_LENGTH; i++) {
                codeIndexArray[i] = b[i * PRIME2 % CODE_LENGTH];
            }

            StringBuilder buffer = new StringBuilder();
            Arrays.stream(codeIndexArray).boxed().map(Long::intValue).map(t -> CHARS[t]).forEach(buffer::append);
            return buffer.toString();
        }

这样我们就能对连续id生成差异化的邀请码了。

   public static void main(String [] args){
        for(long id=10000L;id<10020L;id++){
            String code = InviteCode.instance().gen(id);
            System.out.println("code:"+code);
        }

    }
code:H8XKDR
code:DEHGQH
code:JKA6FD
code:QUZDCJ
code:ABVA7Q
code:FXLCSN
code:W9YT4L
code:C6K4N5
code:ZRXL53

四、结语

任务总算完成了,汇报给领导求表扬。但生成算法还是存在瑕疵的,因为对于六位数的邀请码,只取了5个有效位,第六位作为校验位。所有最大能表示的id到千万级,如果还需要更大的id,则需要扩大邀请码的位数。

详细算法地址(包含将邀请码还原成id的算法哦):https://gist.github.com/zjnxyz/6ef6007f493a0edea6837cc06e934abc

整理了一下源码


import java.util.Arrays;

public class InviteCode {

	/**
	 * 随机字符串
	 */
	private static final char[] CHARS = new char[] { 'F', 'L', 'G', 'W', '5', 'X', 'C', '3', '9', 'Z', 'M', '6', '7',
			'Y', 'R', 'T', '2', 'H', 'S', '8', 'D', 'V', 'E', 'J', '4', 'K', 'Q', 'P', 'U', 'A', 'N', 'B' };

	private final static int CHARS_LENGTH = 32;
	/**
	 * 邀请码长度
	 */
	private final static int CODE_LENGTH = 6;

	/**
	 * 随机数据
	 */
	private final static long SLAT = 1234561L;

	/**
	 * PRIME1 与 CHARS 的长度 L互质,可保证 ( id * PRIME1) % L 在 [0,L)上均匀分布
	 */
	private final static int PRIME1 = 3;

	/**
	 * PRIME2 与 CODE_LENGTH 互质,可保证 ( index * PRIME2) % CODE_LENGTH 在
	 * [0,CODE_LENGTH)上均匀分布
	 */
	private final static int PRIME2 = 11;

	/**
	 * 生成邀请码
	 *
	 * @param id 唯一的id主键
	 * @return code
	 */
	public static String gen(Long id) {
		// 补位
		id = id * PRIME1 + SLAT;
		// 将 id 转换成32进制的值
		long[] b = new long[CODE_LENGTH];
		// 32进制数
		b[0] = id;
		for (int i = 0; i < CODE_LENGTH - 1; i++) {
			b[i + 1] = b[i] / CHARS_LENGTH;
			// 按位扩散
			b[i] = (b[i] + i * b[0]) % CHARS_LENGTH;
		}
		b[5] = (b[0] + b[1] + b[2] + b[3] + b[4]) * PRIME1 % CHARS_LENGTH;

		// 进行混淆
		long[] codeIndexArray = new long[CODE_LENGTH];
		for (int i = 0; i < CODE_LENGTH; i++) {
			codeIndexArray[i] = b[i * PRIME2 % CODE_LENGTH];
		}

		StringBuilder buffer = new StringBuilder();
		Arrays.stream(codeIndexArray).boxed().map(Long::intValue).map(t -> CHARS[t]).forEach(buffer::append);
		return buffer.toString();
	}

	/**
	 * 将邀请码解密成原来的id
	 *
	 * @param code 邀请码
	 * @return id
	 */
	public static Long decode(String code) {
		if (code.length() != CODE_LENGTH) {
			return null;
		}
		// 将字符还原成对应数字
		long[] a = new long[CODE_LENGTH];
		for (int i = 0; i < CODE_LENGTH; i++) {
			char c = code.charAt(i);
			int index = findIndex(c);
			if (index == -1) {
				// 异常字符串
				return null;
			}
			a[i * PRIME2 % CODE_LENGTH] = index;
		}

		long[] b = new long[CODE_LENGTH];
		for (int i = CODE_LENGTH - 2; i >= 0; i--) {
			b[i] = (a[i] - a[0] * i + CHARS_LENGTH * i) % CHARS_LENGTH;
		}

		long res = 0;
		for (int i = CODE_LENGTH - 2; i >= 0; i--) {
			res += b[i];
			res *= (i > 0 ? CHARS_LENGTH : 1);
		}
		return (res - SLAT) / PRIME1;
	}

	/**
	 * 查找对应字符的index
	 *
	 * @param c 字符
	 * @return index
	 */
	private static int findIndex(char c) {
		for (int i = 0; i < CHARS_LENGTH; i++) {
			if (CHARS[i] == c) {
				return i;
			}
		}
		return -1;
	}
}


原文:https://my.oschina.net/bravozu/blog/1827254
作者: BravoZu

4赞

学习了

秀啊

懂密码学,数学就是牛逼。我试过了id百万之类没重复的。我们这个应用系统来说够够的。最舒服的就是可以根据邀请码逆向出来用户id,不用查DB。

不是有hashid

1赞

hashid 是啥操作?老哥讲讲看。我的邀请码需要求是

  1. 数字和字母组成,固定6位长度
  2. 百万级别用户不重复,可以通过邀请码逆向算出用户id
  3. 邀请码的生成没有规律(连续ID的生成,肉眼无法看出规律就是了)

学习了
这个就类似于JWT的实现
利用密码学与Payload来识别唯一与合法

学习了~
有个疑问想问一下,什么场景下需要用户的邀请码保证唯一性?并且用户的邀请码需要长期有效呢?正常不就几分钟有效,redis设置个过期时间就搞定的事儿吗。。

这是邀请码,适用于用户生成的邀请链接不会失效的场景。你说那个是验证码吧? :joy:

我的,搞混了哈哈。那就说得通了。

同之前看到的一篇15年的文章(这一篇)思路相同,但是博主这一个解释了原理,对于没有密码学基础的我,解了迷惑

1赞

但是这个算法支持不了千万级别的用户数量。如果要支持,就必须要增加邀请码的长度。
一直想找一个。6位长度,支持千万级记录的邀请码生成算法。 :joy:

修改邀请码长度为9之后,解不出生成邀请码的id了 :sweat_smile:

哪儿有9位的邀请码。。这太长了。用户咋记啊?

突然 想到这个算法。
经过验证
极限值为 10773290L

当使用以下 值id 算法就失效了。
10773291L

10773291
GG9C5G
-411519

作者也说了,最大支持千万级。。我也想找一个支持数十亿级别的算法。

都是直接复制,没人会记的

1赞

:joy: 有道理,不过我最长见过8位的邀请码,9位的还没见过好像。