The synchronizedMap will just prevent two actions on the map
to happen at same time:
 e.g. when you do a .get(...), at exactly the same time when
     another thread tries to do a .put(...,...).

If you need more actions in one go (conglomerate action), then
you still need explicit synchronization just like you wrote:

No, it isn't.  It's necessary, but with a synchronizedMap you
at least only need to explicitly protect conglomerate actions,
not every single .get() and .put() as you would need for normal
Maps when concurrently accessed in multiple threads.

Re-requesting a lock that the thread already has, shouldn't really
be that expensive.

That seems to be a good enough implementation.

I have a few questions, though.
Is the "AlreadyGotOneException" a sort of assertion against programmer
error?
Whether or not it is, does this mean the state of your application is
probably foobar?

If you are simply testing for programmer (or configuration) error,
then it might be better to do this instead:
oldValue = syncMap.put(key, value);
assert oldValue != null;
This has two side effects:
1. No extra sync
2. the new value does replace the old value, but an exception is still
thrown.

Hope this all helps,
Daniel.

That probably wont make a particularly large impact on performance. As a
matter of style, if I have to externally synchronise like that, then I
do it everywhere.

A better approach is to use a concurrent map (assuming value cannot be
null).

    Value old = map.putIfAbsent(key, value);
    if (old != null) {
        throw new AlreadyGotOneException();
    }

Tom Hawtin