Thread safe Hash Map?

You are on the right track using ConcurrentHashMap. For each point:

1. Check out the methods putIfAbsent and replace both are threadsafe and combine checking current state of hashmap and updating it into one atomic operation.
2. The get method is not synchronized internally but will return the most recent value for the specified key available to it (check the ConcurrentHashMap class Javadoc for discussion).

The benefit of ConcurrentHashMap over something like Collections.synchronizedMap is the combined methods like putIfAbsent which provide traditional Map get and put logic in an internally synchronized way. Use these methods and do not try to provide your own custom synchronization over ConcurrentHashMap as it will not work. The java.util.concurrent collections are internally synchronized and other threads will not respond to attempts at synchronizing the object (e.g. synchronize(myConcurrentHashMap){} will not block other threads).

Side Note:

You might want to look into the lock free hash table implementation by Cliff Click, it's part of the Highly Scalable Java library

(Here's a Google Talk by Cliff Click about this lock free hash.)

ConcurrentHashMap was designed and implemented to avoid any issues with the scenarios you describe. You have nothing to worry about.

A hash table supporting full concurrency of retrievals and adjustable expected concurrency for updates.updates.

javadoc of ConcurrentHashMap