CODEWITHSUNDEEP
scalafunctional-programmingimmutability
Li Haoyi
Li Haoyi

Reputation: 15802

What kind of data structure is used for immutable maps?

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?

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?

Upvotes: 15

Views: 1895

Answers (2)

oxbow_lakes
oxbow_lakes

Reputation: 134310

Persistent Hash maps are implemented using a structure called a Hash trie. It was originally proposed by Phil Bagwell (who is a member of the Scala group at EPFL) but actually implemented by Clojure first. It hit scala when 2.8 came out in 2010.

There is a great talk on functional data structures by Dan Spiewak where the mechanics of the hash trie are explained extremely lucidly (along with other things such as banker's queues)! He also explains asymptotic big-O performance very well in the talk.

Last October saw Phil give another talk at the London scala Lift Off, this time on parallel persistent data structures.

Persistent sorted maps are implemented via a Red-Black tree

Upvotes: 19

duffymo
duffymo

Reputation: 308878

It could be a tree (red-black) or a hash map. Their access characteristics depend on the underlying implementation. A tree is O(log n) for read access; a hash map is O(1).

Upvotes: 1

Related Questions