I know this isn't strictly what was asked in the question, but I think this approach is worth considering.
Use Google Guava's ImmutableMap and make your value type mutable- with a wrapper type if necessary.
Before moving on, it's important to understand this: immutability at the map level only means you can't re-assign objects. There's nothing stopping you from calling mutator methods on the objects already in the map. With this insight, the above approach might be obvious, but let me explain via an example.
For me, the value type was AmtomicInteger- already perfectly mutable in exactly the right way I needed, so I didn't need to change anything. However, in general, let's say you have a type T, and you want a partially mutable map for this type. Well, you can almost do this via a mutable map whose values are wrapper types for that class. Here's a really basic wrapper type, which you might want to enhance with some encapsulation:
public class Wrapper<T>{
public T value;
Wrapper(T t){value = t;}
}
Then you simply create a regular ImmutableMap in the normal way, except fill it with objects of Wrapper instead of objects of T. When using the values, you need to unbox them from the wrapper.
Again, I know this isn't what was asked, and unboxing from a wrapper might be too painful for some use cases, but I'd imagine this would work in a lot of cases. Certainly for me, it helped me realise that I already had a mutable type that was basically a wrapper for an int, and so the ImmmutableMap was fine.