In Java, the hash code for a String object is computed as
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
using int arithmetic, where s[i] is the ith character of the string, n is the length
of the string, and ^ indicates exponentiation.
According to Josua Bloch's Book Effective Java he has explianed given below
The value 31 was chosen because it is an odd prime. If it were even and the multiplication
overflowed, information would be lost, as multiplication by 2 is equivalent to shifting.
advantage of using a prime is less clear, but it is traditional. A nice property of 31
is that the multiplication can be replaced by a shift and a subtraction for better
performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.