这个库最开始是python的版本https://github.com/skorokithakis/shortuuid

后来还有一个Go的版本https://github.com/lithammer/shortuuid

UUID字符长度为32(去掉-), ShortUUID默认生成字符长度为20, 所以在以前在python项目中作为短的唯一标识生成, 趁着有空试试撸一个swift的版本https://github.com/skytoup/shortuuid。

刚开始分析python版的源码, 发现设计得还挺简单的。所有算法逻辑都在一个文件, 源码也就141行。

UUID简介

全称Universally Unique Identifier, 是通用唯一识别码, 由128 bit(16 byte)的数值组成。

具体介绍: https://baike.baidu.com/item/UUID/5921266?fr=aladdin

算法大概流程

ShortUUID包含一组字符Alphabet用于生成短UUID的字符, 以ascii码小到大排序并且不重复。

• UUID转(encode)short UUID

  • 把UUID作为数据不断整除Alphabet的长度, 并以余数作为索引选取Alphabet的字符, 直至被除数为0, 最后组成的字符翻转。

  • 伪代码

    while UUID > 0:
        UUID, rem = UUID / Alphabet.length, UUID % Alphabet.length
        `short uuid` += `Alphabet`[rem]
    
    `short uuid`.reverse()

• short UUID转(decode)UUID

  • 就是把encode的算发反转, UUID(初始为0)作为数据乘以Alphabet的长度, 再加上short UUID对应Alphabet的索引位置。

  • 伪代码

    UUID = 0
    for char in `short UUID`:
        UUID * `Alphabet`.length + `Alphabet`.indexOf(char)

看似简单, 实现起来还是有些难度

大数运算

UUID为128 bit的数据, python自带大数运算功能, 但swift的最大位数Int也只有UInt64和Int64, 即大正整数运算只能用进行64 bit进行运算。而且在标准库中暂未发现有大数运算的相关支持库, 所以只能写一个。

这个算法仅用到128 bit的运算有

• 除并且求余
• 乘

• 加

  主要实现思路是只拆分为32 bit的数据进行分别运算, 最后把拆分的运算结果组合为128 bit运算结果(具体实现看源码)

UUID5

python标准库有相关实现, 但swift没有。实现也比较简单, 主要流程是namespace对应UUID bytes拼上input string再进行SHA1(结果为160 bit), 取前128 bit修改部分数据即可。

相关链接

• python uuid源码: https://github.com/python/cpython/blob/main/Lib/uuid.py
• oc的uuid5源码: https://gist.github.com/eliburke/1a55ed616bb15a7f908b