缩短/重组UUID

Question

首先，我想确认的是，重新哈希是一个敏感的话题。但我想听听你们的意见，你们会采取什么方法。

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

现在，我想创建更适合人类用户的附加标识符。将UUID进行Base64编码仍然会创建具有22个字符的ID，这对于人类使用不合适。因此，我需要类似于URL缩短服务的东西。应用双射函数不会有所帮助，因为它们不会减少信息价值。当然，我知道我需要失去信息才能缩短ID。我也知道，任何哈希的信息减少都会增加碰撞的可能性。

我陷入了困境，最适合的方法是缩短人类ID的信息。

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

我想到的一些想法如下：

- 自动增加的ID：如果我使用某种自动增加的ID，我可以将此ID转换为模糊的字符串并传递这个ID。这将是最简单的方法，只要周围没有太多的键，键就不会很长。但是我必须引入一个集中式实体，而我并不真正想要。 - 缩短UUID：我可以只取原始128位UUID的一些位。然后我应该至少考虑UUID的版本。或者还有其他什么问题吗？ - 重新哈希UUID：我可以在我的初始UUID上应用第二个哈希算法，并存储映射。

还有其他方法吗？哪种方法更好？

提前感谢！

- b_erb

Answer 1

1) 为了缩短UUID，你可以简单地对UUID的前半部分和后半部分执行XOR操作（并重复此过程直到符合长度要求）。这样做将保留分布特征。像任何缩短输出结果的解决方案一样，由于生日悖论，它会增加冲突的可能性。

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

3) 如果你愿意接受“一定的”中央管理，那么这不必让人头疼。中央机构可以向每个客户端分配中等规模的地址空间块，然后客户端在分配ID时可以遍历该子范围。这保证了没有冲突，同时避免了每个ID的往返。一种方法是使用32位整数作为ID，一次分配16位块。换句话说，第一个客户端被分配0001，这允许00010000到0001FFFF。

4) 你可以使用UUID插入到数据库中，但也可以有一个标识字段。这将提供一个备用更紧凑的唯一ID，可以限制为32位整数。

- Steven Sudit

---

@3：我受到分布式节点系统的UUID限制。我不想再添加自己的ID，所以我会继续使用UUID来进行数据存储。我只想提供一些“别名”ID。 - b_erb

我会加上一个(4)，但我不确定我是否支持它。 - Steven Sudit

@4：我打算使用CouchDB，它没有任何自动递增的身份特征，并且默认情况下使用UUID。因此，我正在寻找的额外哈希值只是每个条目的附加属性，并将使用视图进行解析。 - b_erb

鉴于此，我认为（4）不适合您。 （1）足够好吗？请记住，生日悖论表明32位只能获得少于64k的非冲突。 - Steven Sudit

@PartlyCloud - 你能提供一些示例代码吗？主要是关于第一项？可以吗？ - Pure.Krome

@Pure: 这个很简单。主要是使用Guid.ToByteArray()方法获取一个16字节的数组。然后可以使用^运算符对字节进行异或操作。如果需要32位的输出，需要将每组四个输入字节合并为一个输出字节。我建议交错排列，以便第一个输出字节来自偏移量0、4、8和12的组合。以此类推。 - Steven Sudit

Answer 2

你考虑过使用外部别名方法吗？比如选择一个人类友好术语的字典，用它们来使UUID的某些部分更易读（与地理编码系统（例如What3Words）进行比较）：

de305d54-75b4-431b-adb2-eb6b9e546013

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

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

使用这些易于理解的名称，用户很少会看到心理哈希碰撞（斑马出现两次），并且您的数据库不会增长。翻译是双射的，纯粹是UI。

- Christopher Oezbek

Answer 3

脑海中浮现出一些要点：

你的使用情况是什么？如果你的担忧是分布式生成ID，一个解决方案是给每台机器分配其自己独特的整数ID，并将其用作ID的前缀或后缀。

如果没有中央实体来跟踪ID，这种方法并不能真正地帮助你。你可以借鉴UUID本身的思路，在上述分配的机器ID与系统时间相结合。这将使你的ID长度缩短到64位+机器ID的大小。基本上，这就是UUID V1方案，只不过你使用的是比MAC地址更短的内容作为机器ID。如果你知道你可以从2010年2月12日开始，你甚至可以进一步缩短。

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

- Jim L

---

请查看我对Steven答案的第一条评论，以了解我受系统限制必须使用UUID。 - b_erb

另一件事是UUID通常是由该算法生成的值的哈希版本。 - Steven Sudit

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];
  }
}

- Relefant