In Java 5 or later, you can use ConcurrentHashMap for this purpose. You can also use an implementation from Javolution package which is called FastMap. Both of them implement ConcurrentMap interface that includes some additional atomic methods such as putIfAbsent and replace.