Java hashcode reverse calculation

Question

I am trying to test out how String hashcode works by adding a new character and do the reverse to subtract it out, however it didn't give me the right answer when i did the calculation.

For example

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);

I am wondering did i do the math right on my last step above ? overflow shouldn't matter for the calculation right ?

It's not reversible. e.g. stackoverflow.com/questions/9406775/… — BillRobertson42
– BillRobertson42, Commented Dec 27, 2013 at 22:34
@Bill I don't see people explain about why is it not reversible in that thread...where do you see it ? — peter
– peter, Commented Dec 27, 2013 at 22:40
If two different strings can produce the same result, you could not know which one of those strings produced that hash code, so you could not reverse the calculation. — BillRobertson42
– BillRobertson42, Commented Dec 27, 2013 at 22:42

Elliott Frisch · Accepted Answer · 2013-12-27 22:48:32Z

11

Hash functions are not reversible functions. As proof, consider the Pigeonhole principle, you can only store values in the integer range in a hashCode but there are an infinite number of Strings. Therefore, there must be multiple strings with the same hashCode (and there are).

answered Dec 27, 2013 at 22:48

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Joni · Accepted Answer · 2017-01-22 10:50:37Z

5

Multiplying a big number by 31 leads to integer overflow, which cannot be reversed using division by 31.

But hold on though: arithmetic using int in Java is equivalent to arithmetic modulo 2³². Since 31 is odd it has a multiplicative inverse modulo 2³². Therefore multiplication by 31 can be reversed with multiplication by the said "inverse." That is:

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

edited Jan 22, 2017 at 10:50

answered Dec 27, 2013 at 22:50

Joni

112k14 gold badges151 silver badges201 bronze badges

3 Comments

peter Over a year ago

how do we get or calculate the inverse number ?

Joni Over a year ago

You can use the extended Euclidean algorithm, or use Hensel's lemma. The latter is easiest to implement: first set x = a = 31 and then repeat x = x*(2-a*x) until it converges, up to five times.

Joni Over a year ago

But you don't have to calculate it, it's -1108378657

Jim Garrison · Accepted Answer · 2013-12-27 23:02:04Z

2

The specific reason this fails is

1687846330 * 31 + 97 = 52323236327

The number 52,323,236,327 is much larger than what an int can hold, so information is lost off the left-hand end. That information cannot be recovered by inverting the hashCode() algorithm.

If you do the arithmetic you'll see that the hash code you got for the second string is exactly 52323236327 mod 2³¹

More important, the mapping from objects to hash codes is intended to be opaque and non-reversible. Just because it's implemented in a specific way today does not mean the next version of the library has to do it the same way. The only guarantee is that the possibility of collision is extremely low (but non-zero).

edited Dec 27, 2013 at 23:02

answered Dec 27, 2013 at 22:47

Jim Garrison

87k20 gold badges161 silver badges196 bronze badges

1 Comment

supercat Over a year ago

I don't know any way the behavior of the string's hash function could change without breaking any switch statements that use a string argument, since the compiled code includes hardcoded hash values for the strings.

Collectives™ on Stack Overflow

Java hashcode reverse calculation

3 Answers 3

Comments

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related