34

首先，我想确保我知道这样一个事实，即重新散列是一个明智的话题。但是我想听听你的一些意见，你会在这里采取什么方法。

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

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

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

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

  • 自动递增的 ID：如果我使用某种自动递增的 id，我可以将此 id 转换为混淆字符串并传递它。这将是最简单的方法，只要周围的键很少，键就不会很长。但是，我必须引入一个我并不真正想要的中心化实体。
  • 缩短 UUID：我可以只取原始 128 位 uuid 的一些位。那么我至少应该考虑UUID的版本。或者这还有什么问题吗？
  • 重新散列UUID：我可以在我的初始 UUID 上应用第二个散列算法并存储映射。

还有其他方法吗？什么是有利的？

提前致谢！

4

4 回答 4

27

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

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

3）如果你愿意接受一些中央管理，它不一定是痛苦的。中央机构可以向每个客户端分配中等大小的地址空间块，然后客户端可以在分配 ID 时遍历该子范围。这保证了没有冲突，但也避免了每个 ID 的往返。一种方法是使用 32 位整数作为 ID，一次分配一个 16 位块。换句话说，第一个客户端得到 0001，它允许 00010000 到 0001FFFF。

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

于 2010-02-12T18:05:36.510 回答
10

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

de305d54-75b4-431b-adb2-eb6b9e546013

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

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

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

于 2015-01-28T19:17:32.037 回答
4

只是想到了几件事：

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

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

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

于 2010-02-12T18:17:30.443 回答
1

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

该算法并非设计为安全或高效，但应该可以解决问题。

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];
  }
}
于 2012-09-01T14:16:33.637 回答