The Magic Behind Immutable Maps, Or Why Erlang Didn't Have Maps Years Earlier

Erlang variables are immutable. But what happens when we do Map2 = maps:put(Key, Value, Map1)? Surely the VM doesn't copy all of Map1 to a new Map2 in memory just to add that new Key-Value pair? But then how does it give us the illusion that Map1 still exists, without the new pair? How does it keep track of which erlang map contains which pairs? And which performance costs do our applications pay for that magic?