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

Question

这里是我的问题陈述：

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

我可以使用什么样的算法？

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

有什么建议吗？

Answer 1

散列不起作用，因为它可能产生冲突。每个有效输入位都必须映射到输出位。

对于字母，您有 90 - 65 = 25 个不同的值，因此您可以使用 5 位来表示字母。

3 位数字有 1000 个不同的值，因此您需要 10 位。

如果将这些位组合起来，就会得到从输入到 15 位数字的唯一映射。

这种方法很简单，但可能会浪费一些比特。如果输出必须尽可能短，可以映射如下：

output = (L - 'A')*1000 + N

其中L为字母值，'A'为字母A的值，N为3位数字。然后你可以用尽可能少的位来表示output的完整范围，即25*1000 - 1 = 24999。这里又是15位，所以简单的方法不会浪费space.

如果输出位少于输入位，则需要哈希函数。我强烈建议像上面那样将字符串映射到二进制数据，并使用一个简单的函数将输入映射到输出，原因如下：

通用哈希函数无法区分输入位，因为它对它们的含义一无所知。
对于 256 个输出位，在散列 5.7e38 个值之后，发生冲突的几率为 75%。资料来源：Birthday Attack。

5.7e38 看起来很大，但对应的只有 129 位（2^129 = 6.8e38）。在这种情况下，这意味着有超过 75% 的机会有一对字符串 9 (129/15 = 8.6) 元素碰撞。

另一方面，如果您使用非常简单的映射函数，例如：

你可以保证最多17个元素.

的任意两个字符串之间不会发生冲突

与此处相比，为生成唯一 ID 而优化的哈希函数可能比通用哈希执行得更好，但我怀疑它们能否保证所有 256 位值的无冲突哈希。

结论：如果大多数输入字符串的元素少于 17 个，我更喜欢这个而不是散列。

Answer 2

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

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

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

用于基于桶的数据结构（字典）的简单散列函数必须很快。碰撞不仅是可以容忍的，而且是需要的。散列的大小（以位为单位）通常很小。由于冲突，这种类型的哈希不适合您的目的。
A checksum 试图避免冲突并且速度相当快。如果它足够大，这可能足以满足您的情况。
加密散列 的特点是不可能（或很难）发现冲突（即使输入和散列都已知）。它们也是不可逆的（从哈希中不可能找到输入）。对于您的用例，这些通常在计算上是昂贵的并且矫枉过正。
唯一标识任意输入的散列，如CityHash and SpookyHash专为快速散列和无冲突标识而设计。

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

它也很快：每个周期三个字节比 md5 或 sha1 快几个数量级。 SpookyHash 在 public 域中可用（参见上面的 link）。

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

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

How to uniquely identify a set of strings using an integer