The problem is that I'm actually using the HashMap not only for concurrency but also for synchronization. Looking at the Java ConcurrentHashMap it wouldn't work. I need the equivalent of an RwLock per key so that stale data is never read and there are never two writers for the same key. But thinking about it, it's a fairly different data structure from ConcurrentHashMap.