一个看似乱序的 ID 的编码和校验方式(编码法生成不重复随机数)
不知道这样的 “方式” 或者 “场景” 该叫什么名字,所以只好起这么个奇怪的标题。
我第一次接触这个 “场景”,是在 11 年的一个项目: 国家图书馆在馆内部署了多个游客辅助设备,除了导航、答疑等基本功能外,还有拍照留恋功能。成本考虑,这些设备公用一台打印机,放在图书馆正门附近。 也就是,在所有设备上的拍照,最终集中到一个地方打印取照片。
最直接的思路当然是取号,但是有以下情况要考虑。
- 我们无法实现号码(包括二维码呀条形码)的打印。(能实现的话,直接出照片得了,不是么)
- 号码不可以太长,经过实验,我们发现 4 位数字字母混合已经是极限,最佳的体验是 3 位数字字母混合或者 4 位数字。
- 不可以顺序(或者其他简单可预测的规律),最好自带校验,熊孩子太危险。
最后大家都建议使用随机数,或者 hash 后取前几个字符。 但是我非常反对,我觉得凡是统计学有一定印象的都知道小数据集随机是无法做 id 的。 举个极端的例子,0-9 做随机:第二个数重复的概率是 0.1,第三个数重复的概率是 0.28,四个数已经是 0.5 左右了。 而我希望的效果,0-9 做编码:第二到第九个数重复的概率都是 0。
我采用类似这样的算法: 0001 然后从右向左按位,分别加上 0,1,2,3 并且取模。 3211 这其实是个很基本的编码方式了。 当然加 0,1,2,3 很容易看出来,但使用其他乱序的方式就难以看出来了。 对于打击熊孩子来说已经足够了。 改进一,混用进制:讲 10 进制,转为其他进制,然后采用此算法,再转回进制。 16 进制是显而易见的,但其实我们可以自定义一些进制,参考 base64 的算法。 改进二,如果可以牺牲一位,可以做自校验,生成随机数,或者以某一位为基准,进行加密或者混淆。 1111 编码为 8372 然后补个 0 08372 然后随便每位上加同一个数,随便加,因为我们知道最高位原本是 0。 加完就是 19483 HEX 显示就是 4C1B 完美
进过改进的算法可以给 ID 编码,对于非关键数据,可以增加用户体验,也减少碰撞攻击的机会。 比如我的博客文章 ID 是自增的,我又不希望别人知道我写了多少博客,我就可以用这个方式给博客的 ID 重新编码。