title: What kind of data structure is used for immutable maps?
body: <p>I know how normal mutable maps work (using hashtables), and I know how immutable lists work (recursive linked lists) and their advantage over mutable lists (constant time appending without messing up the original) but how do immutable maps (e.g. Scala's) work? </p>
  
  <p>I know the advantage of not messing with the original map when generating new maps, but how does the underlying data structure work, and what kind of performance characteristics do they have, for example compared to mutable hash tables? Is there any standard data structure which people use to implement these, that I could go look up in CLRS/wikipedia?</p>