Re: HashMap vs linear table lookup
Mike Schilling wrote:
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.
You're right, because hashCode() is an idempotent calculation. If it gets
calculated twice it does no harm.
The safety in String's hashCode() case has nothing to do with whether storing
the value is atomic or not. Checking the value, then calculating it, then
storing it is not atomic.
Lazy initialization is a check-and-set, so there's no guarantee that the
calculation will occur only once, absent synchronization. It works all right
for idempotent operations but if the calculation were for something that could
change, you'd potentially lose more than time to failure to synchronize.
Nevertheless, it works for calculation of hashCode() for immutable instances
like String's, because the same value is calculated even if repeated.
Thus, "suitably thread-safe" is guaranteed for String hashCode(), but not
always for all calculations for all classes. I thank you for pointing out the
hole in my reasoning - thread safety really doesn't apply to String hashCode().
--
Lew