This page is no longer maintained — Please continue to the home page at

Re: How to do an efficient update of an immutable map

No replies
Rüdiger Klaehn
Joined: 2009-06-02,
User offline. Last seen 42 years 45 weeks ago.
Forgot reply to all.
I recommend benchmarking the relevant code with google caliper to see if it is actually a problem.
The scala hash map uses a very flat tree structure (maximum 32 children per node), which is much more efficient than a binary tree. Also, a trie is faster than a balanced tree for randomly distributed data like you would expect hash codes to be.

On Wed, Dec 21, 2011 at 2:43 PM, Tony Morris <tmorris [at] tmorris [dot] net> wrote:

I recommend writing a (immutable) self-balancing binary tree map, with accompanying zipper to achieve your operations efficiently.

On Dec 21, 2011 10:34 PM, "Alan Burlison" <alan [dot] burlison [at] gmail [dot] com> wrote:
On 21/12/2011 12:17, Daniel Sobral wrote:

An immutable map doesn't get replaced wholesale. Most of the new map
uses the same data as the old map, with just a sprinkling of new data
structures adjusted for the key that was inserted or removed.

Neat, thanks for the info.  If I wanted to go get my head around the implementation, where would be the best place to start looking?

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland