You don't even need to say "atomic across multiple data structures", "atomic across multiple keys" in is enough as it's likely next level of atomicity you'll require after atomics over single keys.

But if you require that you're in this higher level of transactional semantics that hashmaps don't try to solve (you can still use them as building blocks of course).

I think the furthest hashmap api could go is to do: 1. CaS - simple compare-and-swap on single key 2. CaSS - compare-and-swap on one key and set other key + read two keys tuple

Having 2. would be quite powerful already and you could solve a lot of tasks with it.

Fancy locking over key ranges/key expressions would also be interesting but that starts to be more like database, not hashmap anymore.