Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What kind of Map does a Scala Iterable's "toMap" method return?

Tags:

scala

A Scala Iterable has a toMap method, which returns a Map. What is this map backed by? What are its performance characteristics?

Is there any way to specify that toMap should return a HashMap?

like image 504
Brogrammer Avatar asked Sep 21 '11 22:09

Brogrammer


1 Answers

It returns an immutable.HashMap, which is actually an immutable hash array mapped trie. This data structure is essentially a hybrid between a multilevel hashtable and a trie. The worst-case complexity of a hash array mapped trie is O(log n) for all operations, although with a very low constant factor - hash array mapped tries are very shallow, and typically have only a few indirections. You can read more about the performance characteristics here or run a couple of microbencharks. The performance is acceptable in most cases.

The toMap always returns a hash trie. If you want a mutable hash table, then do this:

import collection._
mutable.HashMap() ++= xs

instead of:

xs.toMap
like image 69
axel22 Avatar answered Nov 08 '22 12:11

axel22