缩短/重新哈希 UUID

Question

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

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

现在我想创建额外的标识符，这对于人类用户来说更方便。对 UUID 进行 Base64 编码仍会创建包含 22 个字符的 ID，这不适合人类使用。所以我需要诸如 URL 缩短服务之类的东西。应用双射函数不会有帮助，因为它们不会减少信息价值。当然，我知道我需要丢失信息才能缩短 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) 如果您愿意接受一些中央管理，这并不一定是痛苦的。中央机构可以向每个客户端分配中等大小的地址空间块，然后客户端可以在分配 ID 时遍历该子范围。这保证了没有冲突，而且还避免了每个ID的往返。一种方法是使用 32 位整数作为 ID，一次分发一个 16 位块。换句话说，第一个客户端收到 0001，这允许 00010000 到 0001FFFF。

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

Answer 2

您是否考虑过使用外部别名方法，在该方法中您选择人类友好术语的字典并使用它们使 UUID（部分）更具可读性（与诸如 What3Words)：

de305d54-75b4-431b-adb2-eb6b9e546013

使用包含 65536 个单词的字典可能会变成：

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

用户不太可能看到这些人类可读名称的心理哈希冲突（斑马线出现两次）并且您的数据库大小不会增加。翻译是双射的并且纯粹是 UI。

甚至还有一个 RFC：https://datatracker.ietf.org/doc/html/ rfc1751

Answer 3

我脑海中浮现出几件事：

您的用例是什么？如果您担心将以分布式方式生成 ID，一种解决方案是为每台计算机分配其自己唯一的 int id，并将其用作其 id 的前缀或后缀。

如果没有一个中央实体，你就意味着没有任何东西可以跟踪 id，即使是在本地，这并没有真正的帮助。您可以从 UUID 本身借用一个页面，并将系统时间与上面分配的机器 ID 结合使用。这将使您降至 64 位 + 无论您的机器 ID 大小如何。基本上，这是 UUID V1 方案，只不过您使用的机器 ID 比 MAC 地址短。如果您知道可以从 2010 年 2 月 12 日开始，您也许可以进一步缩短。

如果您还没有查看维基百科 UUID 条目，您可能会从中得到一两个关于如何构建自己的想法。

Answer 4

这是我写的一个简单的哈希算法。您可以使用它......您可以轻松更改输入和输出映射以及散列的长度，以便权衡可读性与冲突可能性。

该算法的设计目的并不是安全或高效，但应该可以解决问题。

public class HashTools {

  final static String inputMapping = "0123456789ABCDEF";

  final static String[] outputMapping = new String[] {
      "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H",
      "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"
  };

  /* Input: String - containing mostly letters / numbers
   * Output: <hashLength> String using 0-9,A-Z encoding
   */
  public static String simpleHash(String str, int hashLength) {
    StringBuilder hashStr = new StringBuilder(hashLength);
    String strUpper = str.toUpperCase();
    int[] hash = new int[hashLength];

    int i, j, num;
    for (i = 0; i < strUpper.length(); i++) {
      char strChar = strUpper.charAt(i);
      num = mapCharToInt(strChar);

      j = i % hashLength;
      hash[j] += num;
    }

    for (i = 0; i < hashLength; i++) {
      hashStr.append(mapIntToHashChar(hash[i]));
    }

    return hashStr.toString();
  }

  private static int mapCharToInt(char hexChar) {
    return inputMapping.indexOf(hexChar);
  }

  private static String mapIntToHashChar(int num) {
    return outputMapping[num % outputMapping.length];
  }
}