十进制数字转换为62进制

发表于 | 分类于

起因

承前，在魔改naiveboom的过程中，发现原作者使用UUIDv4作为消息主键（id），导致生成的链接比较冗长，而且带着多余的“-”号。
就想替换成更短的id以改善用户体验。以前用过shortid，后来它的作者推荐更安全高效的nanoid。
但既然这次魔改的是个玩具级项目，而且阅后即焚条目保存期限不会超过15天（暂定），那么可以尝试不引入依赖，自己写个方法来生成短id。

时间戳？Base64？

直接用当前毫秒数的时间戳作为id？

有点暴力，位数有些长（数字长度达到13位），不能很好的避免碰撞。

用当前毫秒数时间戳+Base64生成一个id？

其实Base64是一种比较“浪费空间”的编码方式，理论上编码后的字符长度会比编码前多出1/3。例如：

1
window.btoa('1669101673288'); // -> 'MTY2OTEwMTY3MzI4OA==' (输出比输入还长)

时间戳+进制转换

时间戳由十进制转换为更高进制的计数方式？

1
2
3
4
5
(1669101673288).toString(); // -> '1669101673288'
(1669101673288).toString(16); // -> '1849e365b48'
(1669101673288).toString(32); // -> '1gif3cmq8'
(1669101673288).toString(36); // -> 'larw1hl4'
(1669101673288).toString(62); // 报错了 Uncaught RangeError: toString() radix argument must be between 2 and 36

可见Number.prototype.toString方法的参数默认值是10，最大支持到36进制，也就是0至9、a至z这36个字符组成的字符集。

toRadix(62)

想把A至Z甚至 -_!* 这些URL友好的字符也利用起来，来进一步缩短id长度。
Google了一下直接找到答案：https://stackoverflow.com/a/2557508

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Number.prototype.toRadix= function (base) {
  var symbols = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
  var decimal = this;
  var conversion = "";
  if (base > symbols.length || base <= 1) {
    return false;
  }
  while (decimal >= 1) {
    conversion = symbols[(decimal - (base * Math.floor(decimal / base)))] + conversion;
    decimal = Math.floor(decimal / base);
  }
  return (base < 11) ? parseInt(conversion) : conversion;
}

var n = 123456;
n.toRadix(62); // returns: 'w7e'
var d = 1669101673288;
d.toRadix(62); // returns: 'tnTKwqs'

  • 可见通过将十进制整数转换为62进制，可以显著减少字符串长度（62进制相比36进制还能再减少一个字符的长度）

优化toRadix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function toRadix (number, base = 62, isReverse = false) {
  var symbols = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_~!*()';
  if (base > symbols.length || base <= 1) return null;
  if (!Number.isInteger(number) || number < 0) return null;
  if (number === 0) return '0';
  var conversion = '';
  while (number >= 1) {
    conversion = symbols[number % base] + conversion;
    number = Math.floor(number / base);
  }
  return conversion;
}

var d = 1669101673288;
toRadix(d, 62); // -> "tnTKwqs"
toRadix(d, 64); // -> "oiudBJ8"
toRadix(d, 66); // -> "kcQrRCg"
  • 扩充字符集支持到最大69进制
  • 不侵入Number原型链
  • 入参校验、精简代码
  • 仍然不支持负数和小数

进一步优化toRadix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function toRadix(input, base = 62, isReverse = false) {
  var symbols = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_~!*()';
  if (base > symbols.length || base <= 1) return null;
  var generate = function (input, base) {
    if (!Number.isInteger(input) || input < 0) return null;
    if (input === 0) return '0';
    var conversion = '';
    while (input >= 1) {
      conversion = symbols[input % base] + conversion;
      input = Math.floor(input / base);
    }
    return conversion;
  }
  var revert = function (input, base) {
    var sum = 0;
    var arr = input.split('');
    arr = arr.slice(0, base);
    while (arr.length) {
      var symbol = arr.shift();
      var idx = symbols.indexOf(symbol);
      if (idx === -1) return null;
      sum += idx * (base ** arr.length);
    }
    return sum;
  }
  if (!isReverse) {
    return generate(input, base);
  } else {
    return revert(input, base);
  }
}

(1669101673288).toString(36); // -> 'larw1hl4'
toRadix(1669101673288, 62); // -> 'tnTKwqs'
toRadix('larw1hl4', 36, true); // -> 1669101673288
toRadix('tnTKwqs', 62, true); // -> 1669101673288
  • 支持解码（将其他进制的字符串还原回十进制）

TypeScript函数重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function toRadix(number: number, base: number): string | null;
function toRadix(string: string, base: number): number | null;
function toRadix(
  input: number | string,
  base: number = 62
): string | number | null {
  const symbols = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_~!*()';
  if (base > symbols.length || base <= 1) return null;
  if (typeof input === 'number') {
    if (!Number.isInteger(input) || input < 0) return null;
    if (input === 0) return '0';
    let conversion = '';
    while (input >= 1) {
      conversion = symbols[input % base] + conversion;
      input = Math.floor(input / base);
    }
    return conversion;
  } else {
    let sum = 0;
    const arr = input.split('').slice(0, base);
    while (arr.length) {
      const symbol = arr.shift();
      if (!symbol) return null;
      const idx = symbols.indexOf(symbol);
      if (idx === -1) return null;
      sum += idx * base ** arr.length;
    }
    return sum;
  }
}
toRadix(1669101673288, 62); // -> 'tnTKwqs'
toRadix('tnTKwqs', 62); // -> 1669101673288
  • 用TypeScript重写了进制转换函数，省掉第3个参数
  • 仍然不支持负数和小数

后记

最后仍然没有支持负数和小数，有需要时再补全吧。

symbols字符集其实可以加入小数点（点也是URL-Friendly的），但为了将来支持小数，没有把点放进去。

实际应用这个函数的时候，还针对时间戳入参，截断舍弃了一些高位数字（shortid的做法是将时间戳减去一个固定的曾经的时间戳以大幅度减少输出字符串的长度），加入随机数和机器码之类的信息，进一步减少碰撞的可能性，顺带增强了输出字符串的随机性。

除了用来替代UUID，想到一个可能的场景就是服务端需要对一串数字进行编码，但这个数字本身比较敏感不想让前端用户解码出来，或者不想在http请求时明文传输（这个场景编得比较牵强。。），那么服务端可以将symbols中的60多个字符乱序排列，生成指定进制字符串。

1
2
3
4
5
6
7
8
9
// 乱序symbols
let arr ='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_~!*()'.split('');
for (let i = 0; i < arr.length; i++) {
  const rand = ~~(Math.random() * arr.length);
  [arr[i], arr[rand]] = [arr[rand], arr[i]];
}
let symbolsShuffled = arr.join('');
console.log(symbolsShuffled);
// -> '5R7n4PEraX8UqI~Y320WFQNsikSD)CZz(Gc!*xAhVwoJKmHbeL9OMTdvu1-ljftB6_ypg'

前端用户在不知道symbols排列顺序的情况下，硬猜字符集并且猜中的概率会是1/(62!)甚至是1/(69!)，即62或69的阶乘分之一（62的阶乘 = 3.146997326038794e+85）。在字符集不被泄露的前提下（同时也不允许用户自由改变入参重复调用toRadix方法来探测规律），这种自定义字符集参与的编码也就近似于加密了。

Buy me a coffee ☕