hash - 缩短/重新哈希 UUID

Question

首先，我想确保我知道这样一个事实:重新哈希是一个明智的话题。不过，我想听听您的一些意见，以及您会采取什么方法。

我正在构建一个分布式应用程序，其中节点远程创建由 UUID 标识的实体。最终，所有实体应聚集在专用的排出节点上，该节点使用这些 UUID 存储所有实体。

现在我想创建额外的标识符，这对于人类用户来说更方便。对 UUID 进行 Base64 编码仍会创建包含 22 个字符的 ID，这不适合人类使用。所以我需要诸如 URL 缩短服务之类的东西。应用双射函数不会有帮助，因为它们不会减少信息值(value)。当然，我知道我需要丢失信息才能缩短 id。而且我还知道，哈希信息的任何减少都会增加冲突的可能性。我被困住了，减少信息以便为人类创建更短的 ID 的最合适方法是什么。

以下是一些先决条件:我将提供通过我的数据存储映射 {UUID，缩短的 ID} 的能力。我仍然更喜欢非集中式解决方案。我可能永远不会需要总共超过一百万个 ID (~2^20)。

以下是我到目前为止的想法:

• 自动递增 ID: 如果我使用某种自动递增 id，我可以将此 id 传输到模糊字符串并传递。这是最简单的方法，只要周围的键很少，键就不会很长。然而，我必须引入一个我并不真正想要的中心化实体。
• 缩短 UUID:我可以只采用原始 128 位 uuid 的一些位。那么我至少应该考虑 UUID 的版本。或者这还有什么问题吗？
• 重新哈希 UUID:我可以对初始 UUID 应用第二种哈希算法并存储映射。

还有其他方法吗？有什么优惠？

提前致谢!

Answer 1

1) 要缩短 UUID，您可以简单地将上半部分与下半部分进行异或(然后重复，直到它足够短)。这将保留分布特征。与任何缩短输出的解决方案一样，它会增加由于生日悖论而发生碰撞的可能性

2) XOR 相当于一个简单的哈希，但由于不需要额外的混合，所以没问题。您可以在 UUID 上使用 CRC 或非加密哈希，但我不认为这有任何改进。

3) 如果您愿意接受一些集中管理，那并不一定会很痛苦。中央机构可以向每个客户端分配中等大小的地址空间 block ，然后客户端在分配 ID 时可以迭代该子范围。这保证了没有冲突，而且还避免了每个ID的往返。一种方法是使用 32 位整数作为 ID，一次分发一个 16 位 block 。换句话说，第一个客户端获得 0001，这允许 00010000 到 0001FFFF。

4) 您可以使用 UUID 插入数据库，但也可以有一个身份字段。这将提供一个替代的、更紧凑的唯一 ID，它可以限制为 32 位 int。