Re: hash codes
Simon wrote:
Patricia Shanahan schrieb:
Simon wrote:
VisionSet schrieb:
...
If 2 equal hashcodes do not however indicate an object is equal,
but rather if this is the case the calling code should also then call
equals(). This reduces hugely the number of times in total equals() is
I agree. So actually, if hash values are cached, comparing
hashValue()s should
be the first thing to do inside the equals() method (as opposed to
letting the
user do this each time before he uses the equals). Do you know why
String.equals() doen't do this?
The hash values are cached, and are pre-checked before calling equals,
in classes such as HashMap.
Probably I expressed myself incorrectly. I should have said "*since* hash values
are cached..." I'm not asking why String doesn't cache them, but why String
doesn't use them in its equals() method.
You seem to be ignoring the issue of which class caches hash codes when.
String does not cache hash codes. HashMap, for example, does cache the
hash code for each key in the map, and only calculates the probe key
hash code once during a get.
I'm not sure that calculating and caching the hash values in String
would be a gain. It would depend on the average number of comparisons
per String, and also the lengths of the matching prefixes.
Let's forget about the prefix length for a second and assume that the strings
differ only in the last character compared. Then, comparison and hash code
computation need, I believe, almost the same computation time. So you gain
something as soon as a String is involved in more than only a few (I would guess
2) comparisons.
Now, assume the strings differ after a short prefix. Then, as you said, you can
easily lose time by computing hash values instead of starting the comparison and
terminating with false quickly. Now you can do several things:
1 - Use the hash value at least if it was computed by some other reason before
(this is free)
Checking the hash codes costs three comparisons. The condition to
abandon is that the hashes are different and neither of them is zero,
the value used for a hash that has not yet been calculated.
If either hash code has not been calculated, or the strings being
compared are equal, or differ but have equal hash codes, or differ
somewhere in the first few characters, it is a net loss.
Note that the pre-check behavior of HashMap tends to reduce the
probability of comparisons between strings whose hash codes have already
been calculated. While it does force hash code calculation, it never
calls equals for a pair of objects with different hash codes.
It is possible that it might be a gain, but not obvious. It would
require experiments across a wide range of benchmarks.
2 - Many Strings of length n are created in linear time anyway (e.g. by reading
them from a file or stream, creating them with a StringBuffer, user input, ...).
So you can afford computing the hash value on the fly or after it has been
created and still have linear time. The only way to create a string of length n
in sublinear time I can think of is by substring() etc. E.g. the constructors
String(char[]), String(char[],int,int), and String(String) could call
hashValue() almost for free since they need linear time anyway.
String(char[]) etc. use System.arraycopy. Although it is also linear
time, for any reasonably long string is it much faster than character by
character copying.
3 - In String.equals() you could compute the hash value as you go along. If the
Strings are equal, you have computed the hash code for free and you can cache
it. If you terminate earlier, you can throw away your intermediate result. You
could still improve this by completing the hash value computation if the
matching prefix has length at least n/2, say. Ok, that doesn't improve the
situation much for adversarial input, but for typical inputs it could be
competitive. And you can also randomize that, and...
What? You think this is getting clumsy...
Well. One could use at least the first option since this one is essentially free.
Nope. If it does any good at all, it costs three comparisons.
Patricia