生成 v5 UUID。什么是名称和命名空间？

Type 3 和 Type 5 UUID 只是一种将哈希填充到 UUID 中的技术：

类型 1：将 MAC 地址+日期时间填入 128 位

类型 3：将 MD5 哈希填充到 128 位

类型 4：将随机数据填充到 128 位

类型 5：将 SHA1 哈希填充到 128 位

类型 6：顺序 UUID 的非官方想法

编辑：非官方类型 6 现在有一个官方的 rfc

SHA1 哈希输出 160 位（20 字节）；哈希的结果被转换为 UUID。

使用来自 SHA1 的 20 字节摘要：

SHA1 Digest:   74738ff5 5367 e958 1aee 98fffdcd1876 94028007
UUID (v5):     74738ff5-5367-5958-9aee-98fffdcd1876
                             ⭡    ⬑first two bits set to 1 and 0, respectively
                             ╰─low nibble is set to 5, to indicate type 5

我要散列什么？

你可能想知道我应该散列的是什么。基本上你散列连接：

sha1(命名空间UUID+AnyString);

您在字符串前面加上一个所谓的命名空间，以防止名称冲突。

UUID RFC 为您预定义了四个命名空间：

名称空间_DNS：{6ba7b810-9dad-11d1-80b4-00c04fd430c8}

NameSpace_URL：{6ba7b811-9dad-11d1-80b4-00c04fd430c8}

名称空间_OID：{6ba7b812-9dad-11d1-80b4-00c04fd430c8}

名称空间_X500：{6ba7b814-9dad-11d1-80b4-00c04fd430c8}

所以，你可以一起散列：

StackOverflowDnsUUID = sha1(Namespace_DNS + "stackoverflow.com");
StackOverflowUrlUUID = sha1(Namespace_URL + "stackoverflow.com");

然后，RFC 定义了如何：

从 SHA1 中取出 160 位

并将其转换为 128 位的 UUID

基本要点是只取前 128 位，在 type 记录中填充一个 5，然后将 clock_seq_hi_and_reserved 部分的前两位设置为分别为 1 和 0。

更多示例

现在您有了一个生成所谓 Name 的函数，您可以拥有该函数（在伪代码中）：

UUID NameToUUID(UUID NamespaceUUID, String Name)
{
    //Note: All code on stackoverflow is public domain - no attribution required.

    Byte[] hash = sha1(NamespaceUUID.ToBytes() + Name.ToBytes());
    Uuid result;

    //Copy first 16-bytes of the hash into our Uuid result
    Copy(hash, result, 16);

    //set high-nibble to 5 to indicate type 5
    result[6] &= 0x0F; 
    result[6] |= 0x50; 

    //set upper two bits to "10"
    result[8] &= 0x3F; 
    result[8] |= 0x80; 

    return result;
}

（注意：系统的字节序会影响上述字节的索引）

现在你可以打电话了：

uuid = NameToUUID(Namespace_DNS, 'www.stackoverflow.com');
uuid = NameToUUID(Namespace_DNS, 'www.google.com');
uuid = NameToUUID(Namespace_URL, 'http://www.stackoverflow.com');
uuid = NameToUUID(Namespace_URL, 'http://www.google.com/search&q=rfc+4112');
uuid = NameToUUID(Namespace_URL, 'http://stackoverflow.com/questions/5515880/test-vectors-for-uuid-version-5-converting-hash-into-guid-algorithm');

现在回到你的问题

对于版本 3 和版本 5 UUID，必须提供额外的命令行参数命名空间和名称。命名空间是字符串表示形式的 UUID 或内部预定义命名空间 UUID 的标识符（当前已知为“ns:DNS”、“ns:URL”、“ns:OID”和“ns:X500”）。名称是任意长度的字符串。

namespace 是您喜欢的任何 UUID。它可以是预定义的之一，或者您可以自己制作，例如¹：

UUID Namespace_RectalForeignExtractedObject = '8e884ace-bee4-11e4-8dfc-aa07a5b093db'

名称是任意长度的字符串。

该名称只是您希望附加到命名空间的文本，然后经过哈希处理并填充到 UUID 中：

uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'screwdriver');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'toothbrush');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'broomstick');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'orange');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'axe handle');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'impulse body spray');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'iPod Touch');

---

名称和命名空间可用于创建（很可能）唯一 UUID 的层次结构。

粗略地说，类型 3 或类型 5 UUID 是通过将命名空间标识符与名称散列在一起生成的。第 3 类 UUID 使用 MD5，第 5 类 UUID 使用 SHA1。只有 128 位可用，其中 5 位用于指定类型，因此所有哈希位都不会进入 UUID。 （MD5 也被认为是密码破解，而 SHA1 已处于最后阶段，因此不要使用它来验证需要“非常安全”的数据）。也就是说，它为您提供了一种创建可重复/可验证的“哈希”函数的方法，将可能的分层名称映射到概率上唯一的 128 位值，可能像分层哈希或 MAC 一样。

假设您有一个 (key,value) 存储，但它只支持一个命名空间。您可以使用类型 3 或类型 5 UUID 生成大量不同的逻辑命名空间。首先，为每个命名空间创建一个根 UUID。这可以是类型 1（主机+时间戳）或类型 4（随机）UUID，只要您将它存储在某处即可。或者，您可以为您的根创建 一个 随机 UUID（或使用 null UUID: 00000000-0000-0000-0000-000000000000 作为根），然后使用“uuid -v5 $ROOTUUID $NAMESPACENAME”为每个命名空间创建一个可重现的 UUID。现在，您可以使用“uuid -v5 $NAMESPACEUUID $KEY”为命名空间中的键创建唯一的 UUID。可以将这些 UUID 放入单个键值存储中，避免冲突的可能性很高。这个过程可以递归地重复，例如，如果与 UUID 键关联的“值”又代表某种逻辑“命名空间”，如存储桶、容器或目录，那么它的 UUID 可以依次用于生成更多层次结构UUID。

生成的类型 3 或类型 5 UUID 包含命名空间 id 和命名空间内名称（键）的（部分）散列。它不再保存命名空间 UUID，就像消息 MAC 保存对其进行编码的消息的内容一样。从 uuid 算法的角度来看，名称是一个“任意”（八位字节）字符串。但是，它的含义取决于您的应用程序。它可以是逻辑目录中的文件名、对象存储中的对象 ID 等等。

虽然这适用于中等数量的命名空间和键，但如果您的目标是大量唯一且概率非常高的键，它最终会失去动力。生日问题（又名生日悖论）的 Wikipedia 条目包括一个表格，该表格给出了不同数量的键和表格大小的至少一次冲突的概率。对于 128 位，以这种方式散列 260 亿个密钥的概率为 p=10^-18（可以忽略不计），但是 26 万亿个密钥，将至少一次冲突的概率增加到 p=10^-12（万亿分之一），并且散列26*10^15 键，将至少一次碰撞的概率增加到 p=10^-6（百万分之一）。调整编码 UUID 类型的 5 位，它会更快地用完，因此一万亿个密钥大约有万亿分之一的机会发生一次碰撞。

有关概率表，请参见 http://en.wikipedia.org/wiki/Birthday_problem#Probability_table。

有关 UUID 编码的更多详细信息，请参阅 http://www.ietf.org/rfc/rfc4122.txt。

---

名称只不过是某个名称空间中唯一的标识符。问题是命名空间通常非常小，并且其中一个名称经常与其他名称冲突。例如，我的车牌号（名称）在我所在州 DMV 的命名空间中是唯一的，但它可能在世界上不是唯一的；其他州 DMV 可能在自己的命名空间中使用了相同的名称。哎呀，其他人可能有一个电话号码（姓名）也匹配，因为那是另一个命名空间等。

UUID 可以被视为存在于单个命名空间中，如此庞大以至于它可以为所有事物提供唯一的名称；这就是“普遍”的意思。但是如何将其他命名空间中的现有名称映射到 UUID？

一个明显的解决方案是为每个项目生成一个 UUID（V1 或 V4），以替换其不相交名称空间中的旧名称。缺点是它们要大得多，您必须将所有新名称传达给拥有数据集副本的每个人，更新所有 API 等。很可能您实际上无法完全摆脱旧名称无论如何，这意味着现在每个项目都有两个名称，那么你让事情变得更好还是更糟？

这就是 V3/V5 的用武之地。UUID 看起来和 V4 一样随机，但实际上是确定性的；任何拥有命名空间正确 UUID 的人都可以独立地为该命名空间内的任何给定名称生成相同的 UUID。您根本不需要发布它们，甚至不需要预先生成它们，因为任何人都可以根据需要即时创建它们！

DNS 名称和 URL 是非常常用的命名空间，因此为它们发布了标准 UUID； ASN.1 OID 和 X.500 名称并不常见，但标准机构喜欢它们，因此他们也为它们发布了标准命名空间 UUID。

对于所有其他命名空间，您必须生成自己的命名空间 UUID（V1 或 V4）并将其传达给需要它的任何人。如果您有多个命名空间，那么必须为每个命名空间发布 UUID 显然并不理想。

这就是层次结构的来源：您创建一个“基本”UUID（任何类型），然后将其用作命名其他命名空间的命名空间！这样，您只需发布基本 UUID（或使用明显的 UUID），其余的每个人都可以计算。

例如，让我们继续为 StackOverflow 创建一些 UUID；在 DNS 命名空间中有一个明显的名称，所以基础很明显：

uuid ns_dns = '6ba7b810-9dad-11d1-80b4-00c04fd430c8';
uuid ns_base = uuidv5(ns_dns, 'stackoverflow.com');

StackOverflow 本身为用户、问题、答案、评论等提供了单独的命名空间，但这些也相当明显：

uuid ns_user     =  uuidv5( ns_base, 'user'     );
uuid ns_question =  uuidv5( ns_base, 'question' );
uuid ns_answer   =  uuidv5( ns_base, 'answer'   );
uuid ns_comment  =  uuidv5( ns_base, 'comment'  );

这个特定的问题是#10867405，所以它的 UUID 是：

uuid here = uuidv5(ns_question, '10867405');

请注意，在这个过程中没有什么随机的，所以任何遵循相同逻辑的人都会得到相同的答案，但是 UUID 命名空间是如此之大，以至于它（实际上，考虑到 122 位加密哈希的安全性）永远不会与从任何其他命名空间/名称对生成的 UUID。

---