You don't need locks with immutable objects. Since they're immutable, any operation that usually will mutate the object, generate another immutable instead. The most common example is str: the sum of two strings in Python (and in many other languages) produces a new string.
This is usually slower than modifying a mutable object (as atomic types), but they allow you to remove the bottleneck of a lock.
See also immutables.Map: https://github.com/MagicStack/immutables