😏

UUID

花了一个晚上看了一下 UUID 的实现源码. 发现 UUID 有 5 个版本, 其中的特点分别为: V1: 以机子的网卡和时间戳以及一些其他的东西作为因子来生成一个唯一的标识符 V2: 没有提及 V3: 为了方便同样的标识符生成同样的 uuid, 用 MD5 来 hash 标识符和命名空间 V4: 生成一个 128 位的随机数来作为唯一标识符 V5: 和 V3 相似, 不过使用 sha-1 算法, 让标识符更难被预测.

如果我们仅仅只是为了生成一个唯一的标识符, 就用 V1 和 V4. 但是 V1 其实容易被预测, 所以现在已经不怎么用了, 更多的用 V4 的. 关于到底使用哪个, 可以看 stackoverflow 的一个帖子. 那么, UUID 的特点主要是分成: 8-4-4-4-12 的 16 进制表示来展现的, 对应的字节应该是 16(8+4+4+4+12 >> 1) 个. 当然最后会转化成字符串的话, 就变成 16 * 2 + 4(四个短横) 个了. 其中, 第三部分的第一个字符用来表示算法的版本号, 所以 v4 的版本是 4. 而第四部分的第一位用来表示变种, 我没太搞懂这是什么鬼, 但是可能的取值只能为 9 0 a b, 这可以通过 bit & 0x3f | 0x80 来做到的.

我只看了 4 和 5 两个版本的实现, 除去 sha-1 和 随机数生成器算法的话, 还是蛮简单的.😎

V4

V4 就是要求生成一个 128 位的伪随机数. 但是因为有 6 个 位会被强制使用(版本 4 位, 变种 2 位), 就剩下 122 位. 不过光是 122 位, 也就是 2 ^ 122 次方, 再根据生日悖论, 我们大概知道, 这个世界上有 50% 的几率发生碰撞的概率大概是多少. 反正就是很小. 但是, 这就要求随机数代码的高质量了, 显然这个是交给数学家去实现的咯, 而 nodejs 也内置了相应的代码. 所以说, V4 版本的实现就是, 使用 nodejs 生成一个 128 位的随机数. 再给固定的位置设置那 6 个 bit, 最后转成我们需要的字符串形式就可以咯! 那么在 nodejs 这个平台上又会出现哪些问题呢? 首先, 它的随机数发生器生成的是一个 Buffer 对象, 但是它还是能和数组一样取下标, 并不妨碍我们的正常使用. 接下来就是 特定位设置, 代码如下

// 6 就是第 7 个字节
rnds[6] = (rnds[6] & 0x0f) | 0x40
// 同理第九个字节
rnds[8] = (rnds[8] & 0x3f) | 0x80

接下来就是将整个 Buffer 转成我们需要的字符串咯! 不过, 就和今天写颜色的代码碰到的问题一样, 对于小于 16 的数, 如果我们直接用 toString 的话, 是不会自动补 0 的! 所以我们只能自己手动撸代码来保证 0 的出现. 显然, 只能使用字符串来填充这个 0 呢. 这个库的实现很暴力, 但是也很巧妙

var byteToHex = []
for (var i = 0; i < 256; ++i) {
  byteToHex[i] = (i + 0x100).toString(16).substr(1)
}

通过强制让数变成 3 位的十六进制, 这样就保证 0 时存在的, 然后不取高位, 真的棒! 最后一步, 就是根据随机数里的值, 对应到这个 byteToHex 中来, 并在合适的位置插入 -, 整个 UUID 就生成咯! 另外值得一提的是, 其实浏览器也支持一个 crypto 的包了, 虽然只有一个函数, 叫做 getRandomValues, 这个函数接受一个 TypedArray 数组, 并且没有返回值, 属于mutable. 我们需要多大的尺寸, 多大的范围, 就传递相应的进去就行咯.

这样的话, 似乎我也能自己写一个浏览器能用的 V4 版本的 UUID 咯 😎

V5

V5 要求必须有两个参数提供, name, namespace. name 就是你想生成 uuid 的值, 而 namespace 则是一个 16 进制表示的, 16 个字节字符串. 比如，我们相对我的名字进行解码，就可以 v5('YangKui', 'thisisanamespace'); 不过为了方便, 我们干脆用 V4 版本来生成. 但是，单纯的 UUID 是 36 个字节，所以需要先转成 bytes 形式。 可以使用正则表达式来替换.

let bytes = []
uuid.replace(/[a-zA-Z0-9]{2}/g, hex => bytes.push(parseInt(hex, 16));

同样的，我们还需要对 name 进行编码, 我们可以这样实现:

function stringToBytes(str) {
  str = unescape(encodeURLComponent(str)) // UTF8 escapse
  return Uint8Array.from([...str].map(i => i.charCodeAt(0)))
}

第一行的目的是生成一个都小于 255 的 UTF-8 编码, 像下面这样。

A38A178D 6DAC 4F8E 9EEC 001450B372AC

最后, 获得了 name 和 namespace 的编码值后, 只需要对 namespace.concat(name) 调用 sha1, 就成了我们需要的 uuid 值， 然后和 v4 一样设置版本号和变种信息. 至于 sha1 实现原理, 我不太明白, 不过 nodejs 提供了代码. 在它的 crypto 模块中, 可以这样使用:

crypto
  .createHash('sha1')
  .update(bytes)
  .digest('hex')

其中 bytes 就是我们要 hash 的部分. 所以为什么能提供一样的 UUID? 因为 name 和 namespace 都一样, 所以生成的就是一样的啦! 不过, 我在看了 SHA-1 的源码后, 发现它本身就会对传进来的数据做同样的操作来保证都是 Uint8 类型, 所以说上面的 stringToBytes 其实是可以去掉的.