algorithm - 如何将可变长度字符串转换为 16 个字符的字符串？

Question

我需要将长度为 60 - 100 个字符的可变长度字符串转换为 16 个字符的唯一字符串。请注意，输入也将是唯一的。我可以使用一些现有的哈希算法吗？或者还有其他方法可以实现吗？

Answer 1

可变长度 60 字符串唯一可以比 16 长度字符串多得多。

所以一个通用的、好的算法是不可能的。就像从每个唯一的字母（az）生成一个数字（0-9）

Answer 2

根据鸽巢原理，哈希函数没有唯一的输出。如果您实际上有少于 < 2^16 个不同的输入，这是可能的，但这不是我所知道的任何散列函数的设计目标，您必须在了解所有输入的情况下创建散列函数。所以你必须模仿它。合理有效的最简单方案似乎是：

• 保持从输入字符串到整数的关联数组
• 散列字符串时，在关联数组中查找
  • 如果在关联数组中，则返回关联值
  • 否则，让map[input] = map.entry_count()并返回

这会为每个输入分配一个唯一的整数，并在 O(1) 预期时间或 O(log n) 时间内进行散列，但这需要一些空间。然后，如果必须，您可以将此整数转换为字符串，例如使用 base64 编码、十六进制表示法，或者通过将其解释为某种字符编码中的字符串（尽管您必须注意以有效字符串结尾）。这些中的每一个都为您提供了超过 10^16 个结果，并且使字符串不太可能与数字混淆。