Re: HashMap vs linear table lookup

From:

"Mike Schilling" <mscottschilling@hotmail.com>

Newsgroups:

comp.lang.java.programmer

Date:

Thu, 21 Feb 2008 18:10:10 -0800

Message-ID:

<6aqvj.5549$Mw.1609@nlpi068.nbdc.sbc.com>

Lew wrote:

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.

There would be an issue if the value were a long or a double. There
is no guarantee that the whole 64 bits is stored or fetched as an
atomic operation, so that if one thread does

    _hashCode64 = l;
    return _hashCode64;

as another does

    if (_hashCode64 != 0)
        return _hashCode;

The return might contain partly the correct result and partly the
original 0.

At least under the original Java memory model. This might have
changed with the current one.