As I know, there is no pre-built structure  satisfying your requirements (at least in JDK). you have to wrap your map  by your own-built class and for locking use java.sun.com/.../ReentrantReadWriteLock.html. With this class you can completely control your read- and write-locking. The class' javadoc has some samples. I found them useful.