Re: HashMap vs linear table lookup
"Lew" <lew@lewscanon.com> wrote in message
news:QsSdnRO6f82mBCDanZ2dnUVZ_i2dnZ2d@comcast.com...
Thomas Schodt wrote:
Lew wrote:
EJP wrote:
As the poster said, the hashCode for a String is computed once
per String. It is not recomputed every time you call
String.hashCode().
Are you sure of that? The Javadocs don't mention that.
I guess java implementations are not required to
but the sun implementation caches the hash
(kinda changing the internal state of an immutable object...)
Actually, the immutability of an object only applies to its external
state. Lazy instantiation of things like hashCode() or (for classes
other than String) the toString() result is a standard idiom. One
hopes that the String implementation of hashCode() is suitably
thread-safe, otherwise they are changing the external state.
What would "suitably thread-safe" require here? The external behavior
is that all calls to hashCode() should return the same value. I think
this algorithm works fine:
1. define a private int _hashCode;
2. on a call to hashCode(), check the value of _hashCode. If it's
non-zero, return it.
3. otherwise, calculate the hash code of the string.
4. store this value in _hashcode
5. return _hashcode
The only thread-safety issue is that the store of _hashcode in step 4
be atomic, and I think that that's guaranteed by the JVM.. You could
minimize the number of hash code calculations by locking between steps
2 and 4, ensuring that all threads will see the changed value of
_hashcode once it's ready, but that's merely an optimization.