Re: hashcode values
Wizumwalt@gmail.com wrote On 06/07/06 16:02,:
I create a string of color codes (which are just int values) and store
the hash code as the key in a Hashtable.
[code]
str = new String("" + aColor + "," + anotherColor + "," +
anotherColor);
myHashtable.put(str.hashCode(), new Integer(someId));
[/code]
Later on I recieve some data and rebuild the string w/ the exact
contents as before and calc the hash code of that string. Then I pull
the value from the Hashtable based on the hashcode which is the key.
[code]
str = new String("" + aColor + "," + anotherColor + "," +
anotherColor);
mySelection = (Integer) myHashtable.get(str.hashCode());
[/code]
My question is, is this always going to work or can the hashcode be
different on the string even though the contents are the same? Am I
using hashcodes correctly here?
A String's hashCode is entirely determined by its
contents, so two Strings with identical content will have
identical hashCodes. More generally, any two objects for
which equals() returns true must have identical hashCodes.
However, the reverse does not necessarily hold! Two
equal objects necessarily have equal hashCodes, but two
objects with equal hashCodes are *not* necessarily equal.
One way to see that this must be true is to note that the
universe of possible Strings is far larger than the number
of distinct hashCodes: a hashCode is a 32-bit int, but the
number of possible String values has about 34359738368 bits.
Therefore, some Strings that are different -- a huge number
of different Strings, in fact -- must have the same hashCode.
What does this mean for you? Well, if you have the bad
luck to construct two different Strings that have the same
hashCode, one of them will overwrite the other in your
Hashtable (a HashMap is usually preferred, by the way).
You could store the ID for the first entry, then clobber
it with the ID for the second, and then when you rebuild
the first color's String you'll retrieve the second entry's
ID from the Hashtable. Not, perhaps, what you had in mind.
Despite the huge numerical disparity between the number
of possible Strings and the number of different hashCodes,
you would actually have to be pretty unlucky to run into a
collision like this. The population of possible Strings
includes a lot of values you'll probably never run across:
Strings of length 123456789 containing only Korean characters,
that sort of thing. Still, the famous "birthday paradox"
works against you: if you compute hashCodes for N objects,
the chance of a collision rises (roughly) as the square of N.
Fortunately, the fix is simple: Don't use the hashCode
as the key, use the String itself! The Hashtable (or HashMap)
already understands how to disambiguate keys that have equal
hashCodes: it uses the equals() method to find out whether
they are actually the same or merely a colliding pair. Keys
that happen to have equal hashCodes even though they have
distinct values are no trouble for Hashtable and HashMap.
--
Eric.Sosman@sun.com