Java哈希码反向计算

Question

我正在尝试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); 

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

Answer 1

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

Answer 2

将大数乘以31会导致整数溢出，使用31除法不能逆转整数溢出。

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

int inverse = -1108378657;
// This will print the hashCode of mlkjihgfedcb
System.out.println(("mlkjihgfedcba".hashCode() - (int) 'a') * inverse);