Re: synchronized HashMap vs. HashTable
On Thu, 22 May 2008, Mikhail Teterin wrote:
Lew wrote:
The question isn't can you use Hashtable, but why would you?
Thanks to all for the answers. I'm using HashMap for now, but here is what
my /ideal/ implementation would allow:
. Multiple threads should be able to /insert/ into the Map in parallel
Okay.
. Attempts to /query/ the Map should not fail (return null) as long as
any other thread is in the middle of inserting...
Okay - what *should* happen in that case?
Here is the explanation... My application has to send questions to an
external service, which replies asynchronously (some questions are easier
to answer than others).
Upon submitting a question, the service's API returns a correlation ID,
which the response will also bear.
To match the received replies with the asked questions, I'm using a
Map<CorrelationID,MyObject>.
Once in a blue Moon, an answer would come back to the replies-processing
thread /before/ the questions-asking thread had the chance to finish
inserting the ID into the Map. The replies-processing thread then treated
the reply as "unsolicited", etc.
How about if the reply-processing thread can't find the question in the
map, it waits for a bit and then tries again? Even better, how about it
just yields?
void processAnswer(CorrelationID id, Answer a) {
Question q = null ;
while ((q = questions.get(id)) == null) Thread.yield() ;
// your version should avoid an infinite loop here
q.answer(a) ;
}
This will mean that the answer-processing thread gets held up every now
and then, but it's once in a blue moon, and the question-processing
threads can still run.
If you don't fancy that, have a queue of answers, and if you get an
unsolicited one, push it onto it. Then, after every successful processing
of a question, go through the queue and try putting the entries on it into
the map. That avoids any holdups, although it is a bit baroque.
I've switched to synchronized HashMap for now, but that means, only one
thread can be accessing the Map at any moment, which introduces some
unnecessary stalling: only one thread can be asking the question or
matching up the reply.
I don't think that'll solve the problem, actually: there's still a
potential race condition (as we call these things in the trade) between
question and answer threads. The sequence could be:
questioner sends question
questioner runs out of time
answerer runs
answerer receives answer
answerer locks map
answerer looks up question - AND FAILS!!!
answerer unlocks map
answerer runs out of time
questioner runs
questioner locks map
questioner registers question - BUT TOO LATE!
questioner unlocks map
If you want to preclude that, the questioner has to lock the map *before*
it sends the question, and unlock it after it's registered it. you can't
do that with any implementation of Map, because it's a matter than extends
beyond the map itself. You'd have to use an explicit synchronized block.
If, after all that, you do want fast concurrent access, look at the Map
implementations in java.util.concurrent.
There is also the rocket science of lock-free data structures, and the
voodoo of wait-free data structures. I can't find any code or libraries
implementing them for java, but see:
http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html
http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf
http://blogs.azulsystems.com/cliff/2007/06/engineering_a_h.html
http://blogs.azulsystems.com/cliff/2007/09/more-thinking-a.html
And be terrified.
tom
--
buy plastic owl