Re: Cannot seem to lock HashMap
byoder@hotmail.com wrote:
....
But I cannot say for sure if this will cause the behavior or problems
you mention above (return NULL becuase of unsynchronized get()
method). One thing that leads me to think you ARE correct is the
implementation of Hashtable HAS a synchronized get() method. But it
seems strange to me that HashMap would have such a BIG vunerability in
it - but perhaps that is what you get when using unsynchronized
HashMap vs. Hashtable.
I am not suggesting a vulnerability in the sense of a failure of HashMap
to conform to its contract. The scenario requires a structural change to
the map while get is running. The API documentation says "If multiple
threads access this map concurrently, and at least one of the threads
modifies the map structurally, it must be synchronized externally.". The
vulnerability lies in trying to use HashMap in a way that is contrary to
its contract.
The scenario is a simple single processor case. How well do you
understand the Java memory model? See
http://java.sun.com/docs/books/jls/third_edition/html/memory.html#17.4
I think that tomorrow I will take the HashMap source code and run some
tests to prove or disprove this theory, since I cannot tell by looking
at it. But if true, then I will need to also synchronize the get()
method in my wrapper class.
Synchronization bugs may be hard to reproduce, and remember that you
don't just have to deal with the one scenario I suggested. In order to
not synchronize get you would need to look at its interaction with every
method in HashMap.
An easier approach might be to first do a performance test simply
synchronizing get. It may run fast enough. For the default load level,
the average chain length it needs to search is 0.75 entries. If get is
too slow to synchronize, I would suspect a bad hashCode function in the
key class, and try to fix that.
Below methods are from HashMap.java (1.5.0_12):
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key ||
key.equals(k)))
return e.value;
}
return null;
}
static int indexFor(int h, int length) {
return h & (length-1);
}
I looked at 1.5.0_3. The same point applies to the later code - consider
a resize happening anywhere between indexFor committing to its result
and the end of the search.
This brings out an important point. If you are going to depend for
correctness of your program on assumptions about how API methods are
implemented, you cannot just review one implementation. You need to
review EVERY version on which you intend to support your program.
Patricia