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

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@tmorris.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.burlison@gmail.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?