F# Map.add time and space complexity

Question

As far as I know the Map-datatype in F# is immutable (in contrast to arrays). This raises for me the question what the Map.add function exactly does internally. Does it copy the whole structure to leave the original unaltered (which would be very inefficient) or does it use a cleverer strategy that assures that the time complexity is still roughly log n? Unfortunately in the Microsoft docs things like complexity aren't mentioned at all although important in certain cases.

Answer 1

F# Map uses a sorted balanced tree under the hood. During updates only the nodes involved in the path to the update is updated. The rest is reused.

FYI the Mapsource code: https://github.com/Microsoft/visualfsharp/blob/master/src/fsharp/FSharp.Core/map.fs

Answer 2

The question of "what Map.add does internally" is one that you can answer yourself by looking at the implementation.

In general, F# Map is a persistent data structure based around a self-balancing search tree. The general idea behind using that sort of structure is that on update only part of the structure needs to be rewritten - and that part is in fact created from scratch - while subtrees that don't change are shared between the "old" and the "updated" versions of the structure.

The complexity of the lookup and add operations are O(log n), average case (as you'd expect from the underlying tree structure).