如何从唯一的字符串生成唯一的整数？

Question

我有一个对象，其中包含一个字符串，用于保存唯一的ID（例如“ocx7gf”或“67hfs8”）。 我需要提供一个实现int hascode()方法的对象，使其具有唯一性。

最简单/最快的方法如何将字符串转换为唯一的整数？

谢谢。

编辑-好的，我已经知道String.hashcode是可能的。但在任何地方都不推荐使用它。实际上，如果没有其他建议的方法-当我的对象在集合中并且我需要哈希码时，我应该使用它吗？我应该将其连接到另一个字符串中以使其更加成功吗？

- Bick

---

你做不到。整数值有限，但字符串数量是无限的。因此，并非每个字符串都能有其自己的整数哈希值。但你可以计算一个唯一的BigInteger哈希值。 - Ingo

@Ingo，我看不出BigInteger作为哈希码有很多用处。它们往往太大了。 - Jon Hanna

@Jon，确实。字符串本身可能是最紧凑的键之一。我只是为了完整性而添加了BigInteger的想法。 - Ingo

不，哈希码在很多地方都被推荐使用，并且被几个标准容器隐式使用。如果您有特定的原因不使用它来解决您的问题，请详细说明，否则人们就不知道为什么不只是使用 Java 字符串哈希码背后的相当不错的代码。 - Jon Hanna

规则＃1：如果JDK已经提供了，请不要自己编写代码。 JDK代码一直在更新，因此您可能只需更新到更高版本的Java即可获得更好的性能实现。如果您自己编写它，它不仅可能比JDK提供的差得多（让我们真实一点：这是您与整个Sun / Oracle程序员团队的对抗），而且您还需要承担维护的负担。不要试图聪明，只需执行String.hashCode()。如果您想优化代码，则很有可能您的代码中有许多其他地方可以从优化中受益。 - Frans

Answer 1

不需要实现一个返回唯一值的算法，因为大多数实现都会出问题。你需要做的是在位级别上进行良好分散，特别是对于常见值（如果有比其他值更常见的值）。除非您了解格式的特殊知识，否则只需使用字符串本身的哈希码即可。如果具有关于ID格式限制的特殊知识，则可能可以自定义并获得更好的性能，但错误的假设可能会使情况变得更糟。注意要在哈希算法中保持良好的位分布，因为完全唯一是不可能的，哈希冲突是可能的。哈希方法知道这一点并且可以处理它，但这确实会影响性能，所以我们希望冲突尽可能少见。此外，哈希通常是重新计算的，因此我们的32位数字可能会被缩小到例如0至22的范围内，并且我们希望在其中实现尽可能好的分配。我们还希望在计算哈希时不要花费太长时间，以免它成为瓶颈。这是一个不完美的平衡行为。坏的哈希方法的经典例子是针对X、Y整数对的哈希方法：

return X ^ Y;

虽然这种方法在 4^32 种可能的输入中返回了 2 ^ 32 种可能的值，但在现实世界中，我们经常会遇到 X 和 Y 相等的坐标集合（例如 {0, 0}、{1, 1}、{2, 2} 等），它们都会散列为零，或者匹配对（{2,3}和{3,2}）将散列为相同的数字。因此，我们更好地采用以下方法：

return ((X << 16) | (x >> 16)) ^ Y;

现在，这种方法可能产生恶劣的结果的可能性与前一种相同，但在实际情况下，它往往表现更好。

当然，如果你正在编写一个通用类（不知道可能的输入是什么）或者对手头的任务有更好的理解，则需要进行不同的工作。例如，如果我使用日期对象但知道它们都只是日期（时间部分总是午夜）并且仅在几年内，那么我可能会更喜欢自定义哈希代码，只使用日期、月份和低位数的年份，而不是标准哈希码。不过，Date的编写者无法掌握这些知识，必须尽量照顾每个人。

因此，假如我知道给定的字符串始终由6个大小写不敏感的字符组成，在[a-z]或[0-9]范围内（您的问题似乎是这样的，但不清楚），那么我可以使用一种算法为每个字符分配从0到35（每个字符的36个可能值）之间的值，然后遍历整个字符串，每次将当前值乘以36并加上下一个字符的值。

假设ID分布良好，这将是最佳选择，特别是如果我使得哈希中低位数的数字与ID中最频繁更改的字符匹配（如果可以这么说），因此在重新哈希为较小范围时仍能保持良好的表现。

不过，缺乏对格式的确切了解，我不能确定做出这样的决策，并且我可能会使情况变得更糟（使用更慢的算法而实际上哈希质量并没有提高或甚至降低）。

您有一个优势，即由于它本身是一个ID，则假定没有其他非相等对象具有相同的ID，因此无需检查其他属性。但并非总是如此。

- Jon Hanna

---

+1 指出哈希码本质上并不是唯一的。 - Ingo

你能详细解释一下“在位上有良好的分布”吗？我没太理解那部分。 - Bick

嘿，非常感谢。那很有趣。由于我不知道我的散布范围有多广或最常更改的字符是什么，因此我将采用使用String.hashcode()作为映射的根本方式。我认为从这些评论中我可以理解这是相当合理的解决方案。如果在我的集合中发生冲突，我的律师将与你联系。我的律师将会在这个页面上联系到你们所有人。与此同时，感谢您给我的启示。 - Bick

您的律师可能会指出免责声明，并建议如果有许多冲突（除非集合本身编写得很糟糕，否则少数并不重要），那么现在是从重新阅读上面开始更详细地检查哈希的时候了 ;) - Jon Hanna

Answer 2

无法从长度不受限制的字符串中获取唯一的整数。有大约40亿（2^32）个唯一的整数，但是有无限多个唯一的字符串。

String.hashCode()不能给你唯一的整数，但它会尽力根据输入字符串给出不同的结果。

编辑

您编辑后的问题说String.hashCode()不推荐使用。这不正确，它是推荐使用的，除非您有特殊原因不使用它。如果确实有特殊原因，请提供详细信息。

- Jon Bright

---

改为“几乎无限” :-) - Jon Bright

嘿，“无限”的说法很强大 :) - Jon Hanna

"真的，真的，真的，很大"？;) - Jon Hanna

使用哈希码处理大约20K个长度为255的字符串，您有什么想法？安全吗？ - Anmol Gupta

对于那些少量的字符串，一个只有10个字节大小的哈希可能已经足够了。如果你想使用标准哈希函数，你可以使用 SHA-256 并使用 32 字节（或者十六进制编码为64个字符）。 - Jon Bright

Answer 3

看起来你有一个基于36进制的数字（a-z + 0-9）。为什么不使用Integer.parseInt(s, 36)将其转换为int类型？显然，如果有太多唯一的ID，它将无法适合一个int，但在这种情况下，你只能使用String.hashCode()，它尽最大努力接近唯一。

- Jonathan

---

使用 long 可能比 int 更值得考虑。 - Peter Lawrey

@Peter hashCode() 返回的是一个 int，而不是一个 long。否则我会建议你使用它。 - Jonathan

如果这仅仅是用于hashCode()，那么结果不需要是唯一的。我假设OP知道这一点。 ;) - Peter Lawrey

@Peter 确实。很难确定他是想要一个唯一的整数，还是想要一个哈希码。如果只是一个唯一的整数，那么考虑使用 long 或者甚至是 BigInteger。 - Jonathan

我猜他想要一切都在一个地方。;) 顺便加个赞。 - Peter Lawrey

Answer 4

除非您的字符串在某种程度上受限，或者您的整数比您要转换的字符串包含更多位，否则无法保证唯一性。

假设您有一个32位整数和一个64个字符的字符集用于您的字符串。这意味着每个字符六位。这将允许您将五个字符存储到整数中。超过五个字符就不能存储。

- paxdiablo

Answer 5

将每个字符串字符表示为一个五位二进制数字，例如a表示为00001，b表示为00010等。因此，有32种组合可能。例如，cat可以写成00100 00001 01100，然后将这个二进制数转换为十进制，例如4140，因此cat就是4140。同样地，您可以通过先将4140转换为二进制，然后将五位二进制映射到字符串来获取cat。

- Abhishek Choudhary

Answer 6

一种方法是为每个字母分配一个值，为字符串中的每个位置分配自己的倍数，例如a=1，b=2等等。然后，第一个数字（从左到右读取）中的所有内容将乘以一个质数，下一个数字将乘以下一个质数，以此类推，使得最终数字乘以比该数字中可能子集的数量更大的质数（26+1表示空格或52+1表示大写字母等其他支持的字符）。如果将数字映射回第一个数字（最左边的字符），则从唯一字符串映射回1或6无论第一个字母是什么，都会产生唯一值。

例如，Dog可能是30、3（15）、101（7）或782，而God可能是33、3（15）、101（4）或482。生成唯一字符串比唯一性更重要，如果保留原始数字，则它们在生成中可能很有用，例如30（782）对于区分类似字符串的目的将对某些12（782）是唯一的。Dog永远是Dog，但它永远不会是Cat或Mouse。

- Nicholas Iverson