string - 如何使用整数唯一标识一组字符串

Question

这里是我的问题陈述:

• 我有一组匹配正则表达式的字符串。假设它匹配 [A-Z][0-9]{3}(即 1 个字母和 3 个数字)。
• 我可以有 1 到 30 之间的任意数量的字符串。例如，我可以有:
  • {A123}
  • {A123, B456}
  • {Z789, D752, E147, ..., Q665}
  • ...
• 我需要生成一个整数(实际上我可以使用 256 位)，无论元素的数量如何，它对于任何一组字符串都是唯一的(尽管元素的数量可用于生成整数)

我可以使用哪种算法？

我的第一个想法是将我的字符串转换为数字，然后对它们进行运算(我想到了哈希函数)，但我不确定什么样的公式会给我可能的结果。

有什么建议吗？

Answer 1

您有 2^333 个可能的输入集((26 * 10^3)​​ 选择 30 个)。

这意味着您需要一个 333 位宽的整数来表示所有可能性。您最多只有 256 位，因此会发生冲突。

这是哈希函数的典型应用。哈希有多种用途，因此选择正确的类型很重要:

• 用于基于桶的数据结构(字典)的简单哈希函数必须很快。碰撞不仅是可以容忍的，而且是需要的。散列的大小(以位为单位)通常很小。由于冲突，这种类型的哈希不适合您的目的。

• 校验和 尝试避免冲突并且速度相当快。如果它足够大，这可能足以满足您的情况。

• 加密散列 的特点是不可能(或很难)发现冲突(即使输入和散列都已知)。它们也是不可逆的(从哈希中不可能找到输入)。对于您的用例，这些通常在计算上是昂贵的并且矫枉过正。

• 用于唯一标识任意输入的散列，例如 CityHash和 SpookyHash专为快速散列和无冲突识别而设计。

SpookyHash 似乎很适合您的用例。它有 128 位宽，这意味着您需要 2^64 个不同的输入才能获得 50% 的单次碰撞机会。

它也很快:每个周期三个字节比 md5 或 sha1 快几个数量级。 SpookyHash 在公共(public)领域可用(见上面的链接)。

要在您的用例上应用任何散列，您可以将列表中的项目转换为数字，但将它们作为字符串提供似乎更容易。在这种情况下，您必须接受一种编码(ASCII 就可以)。

当 I18N 有问题时，我通常使用 UTF8 左右。然后，有时关注规范化很重要。但这不适用于您的简单用例。