5

我试图String通过添加一个新字符来测试哈希码的工作原理，然后反过来将它减去，但是当我进行计算时它没有给我正确的答案。

例如

int PRIME = 31;

//this will print 1687846330 
System.out.println("mlkjihgfedcb".hashCode());   

//this will print 783628775 which equals to "mlkjihgfedcba".hashCode();
System.out.println(("mlkjihgfedcb".hashCode() * PRIME + (int) 'a')); 

//this will print 25278344 which doesn't equals to "mlkjihgfedcb".hashCode()
System.out.println(("mlkjihgfedcba".hashCode() - (int) 'a') / PRIME);

我想知道我是否在上面的最后一步做正确的数学？溢出对计算不重要吗？

4

3 回答 3

9

哈希函数不是可逆函数。作为证明，请考虑Pigeonhole 原则，您只能将整数范围内的值存储在 hashCode 中，但字符串的数量是无限的。因此，必须有多个具有相同 hashCode 的字符串（并且有）。

于 2013-12-27T22:48:32.827 回答
5

将一个大数乘以 31 会导致整数溢出，不能使用除以 31 来反转。

但是请坚持：intJava 中使用的算术等价于算术模 2 32。由于 31 是奇数，它具有乘法逆模 2 32。因此，乘以 31 的乘法可以与乘以所述“逆”的乘法相反。那是：

int inverse = -1108378657;
// This will print the hashCode of mlkjihgfedcb
System.out.println(("mlkjihgfedcba".hashCode() - (int) 'a') * inverse);
于 2013-12-27T22:50:36.470 回答
1

失败的具体原因是

1687846330 * 31 + 97 = 52323236327

数字 52,323,236,327 比 anint所能容纳的要大得多，因此信息会从左端丢失。该信息无法通过反转hashCode()算法来恢复。

如果你做算术，你会看到你得到的第二个字符串的哈希码正好是52323236327 mod 2 31

更重要的是，从对象到哈希码的映射是不透明和不可逆的。仅仅因为它今天以特定的方式实现并不意味着库的下一个版本必须以同样的方式进行。唯一的保证是碰撞的可能性极低（但非零）。

于 2013-12-27T22:47:35.240 回答