Prev: Direct Client Needs : 10 Java with strong exp on JMS in North Carolina
Next: When String.hashCode() returns 0 (Was: what the benefit is by using annotation, like "@Immutable" ?)
From: Daniel Pitts on 26 Jul 2010 15:19
On 7/26/2010 12:12 AM, Andreas Leitgeb wrote:
> Jim Janney<jjanney(a)shell.xmission.com> wrote:
>> Andreas Leitgeb<avl(a)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/>
 | 
Pages: 1
Prev: Direct Client Needs : 10 Java with strong exp on JMS in North Carolina
Next: When String.hashCode() returns 0 (Was: what the benefit is by using annotation, like "@Immutable" ?)