使用哈希码作为唯一ID

Question

我正在一个基于java的系统中工作，我需要为视觉显示中的某些元素设置一个id。一类元素是字符串，因此我决定使用 String.hashCode() 方法来获取这些元素的唯一标识符。

然而，我遇到的问题是，如果 id 为负数，并且

String.hashCode

经常返回负值，那么我在 borks 中工作的系统会返回负值。一种快速解决方案是仅在哈希码调用周围使用 Math.abs() 以保证得到正结果。我对这种方法想知道的是两个不同元素具有相同哈希码的机会有多大？

例如，如果一个字符串返回哈希码 -10，而另一个字符串返回哈希码 10，则会发生错误。在我的系统中，我们讨论的是通常不超过 30 个元素的对象集合，因此我认为这并不是一个真正的问题，但我很好奇数学的含义。

Answer 1

哈希码可以被认为是伪随机数。据统计，当

int

哈希码为正时，当总体规模约为 54K 时，任意两个元素之间发生冲突的几率达到 50%（any

int

为 77K）。请参阅生日问题概率表了解各种哈希码大小的冲突概率。

此外，您单独使用

Math.abs()

的想法是有缺陷的：它并不总是返回正数！在2的补码算术中，

Integer.MIN_VALUE

的绝对值就是它本身！众所周知，

"polygenelubricants"

的哈希码就是这个值。

Answer 2

哈希值不是唯一的，因此它们不适合 uniqueId。

关于哈希冲突的概率，你可以阅读生日悖论。实际上（据我记得）当从 N 值的均匀分布进行绘制时，您应该在绘制后发生碰撞

$\sqrt(N)$

（您可能会更早地发生碰撞）。问题是 Java 的

hashCode

实现（尤其是在散列短字符串时）不提供均匀分布，因此您会更早地遇到冲突。

Answer 3

您已经可以获得两个具有相同哈希码的字符串。如果您认为自己有无限数量的字符串并且只有 2^32 个可能的哈希码，那么这一点应该是显而易见的。

你只是在取绝对值时让它的可能性更大一点。风险很小，但如果您需要一个唯一的ID，这不是正确的方法。

Answer 4

当您只有 30-50 个值时，您可以做的是将您进入 HashMap 的每个字符串与正在运行的计数器一起注册为值：

HashMap StringMap = new HashMap<String,Integer>();

StringMap.add("Test",1);
StringMap.add("AnotherTest",2);

然后您可以通过调用以下命令来获取您的唯一 ID：

StringMap.get("Test"); //returns 1