When String.hashCode() returns 0 (Was: what the benefit is by using
annotation, like "@Immutable" ?)
On 7/26/2010 12:12 AM, Andreas Leitgeb wrote:
Jim Janney<jjanney@shell.xmission.com> wrote:
Andreas Leitgeb<avl@gamma.logic.tuwien.ac.at> writes:
Has anyone found e.g. an english dictionary-word with hashCode 0, yet?
Or perhaps the name of some commonly used class in Java standard library
or some other String likely occurring in innocent code?
All strings of the form "\0", "\0\0", "\0\0\0", etc.
Well, they're *almost* trivial ;-)
For ordinary words, I ran the following against the
dictionary file on a Linux system and got no hits.
Thanks for the code (I guess I'd have been too lazy, myself ;)
I ran it against all the pure class-names (like "java.lang.String",
and "java/lang/String") from $JAVA_HOME/lib/rt.jar and found no
match, either. Not even for each "Lpath/to/ClassName;".
The conditions under which String.hashCode() would return 0:
1. Empty String
2. All characters in the string are \0. (Empty string is the trivial
case of this)
3. The string is long enough that s[0]*31^(length-1) is close enough
to, or over 2^32, and the rest of the characters add up just right.
Some basic math indicates that the minimum string length for that final
condition is 5
Basic Math:
(2^16)*31^(x-1) = 2^32
31^(x-1) = 2^31/(2^16)
31^(x-1) = 2^16
(x-1)ln(31) = 16 ln 2
x-1 = (16 ln 2)/ ln(31)
x = (16 ln 2)/ ln(31) +1
x ~= 4.21
So, you basically end up with an equation with 5 variables (for the
smallest strings, there are larger ones as well)
s[0]*(31^4)+s[1]*(31^3)+s[2]*(31^2)+s[3]*31+s[4] ??? 0 mod 2^32
Someone else can work out the valid values, but I know that s[0]=4650 is
near one such value.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>