Scala Default Execution

Question

I can see that from the Scala documentation scala.collection.immutable.Set is just a dash. Which of the default implementations of Set? HashSet or TreeSet (or something else)?

I would like to know / plan the runtime of certain functions.

Example:

scala> val s = Set(1,3,6,2,7,1) res0: scala.collection.immutable.Set[Int] = Set(1, 6, 2, 7, 3) 

• What will be the running time of s.find (5), O (1) or O (log (n))?

• How does this apply to Map, what is the best way to understand this?

Answer 1

After looking at the source code, you can find that for the four elements there is an optimized implementation provided by EmptySet , Set1 , Set2 , Set3 and Set4 , which simply hold a single value.

For example, here is the Set2 Declaration (with scala 2.11.4):

 class Set2[A] private[collection] (elem1: A, elem2: A) extends AbstractSet[A] with Set[A] with Serializable 

And here is the implementation of contains :

 def contains(elem: A): Boolean = elem == elem1 || elem == elem2 

or find implementation

 override def find(f: A => Boolean): Option[A] = { if (f(elem1)) Some(elem1) else if (f(elem2)) Some(elem2) else None } 

Very simple.

For kits with more than four elements, the main implementation is a HashSet . We can easily check this in the REPL:

 scala> Set(1, 2, 3, 4).getClass res1: Class[_ <: scala.collection.immutable.Set[Int]] = class scala.collection.immutable.Set$Set4 scala> Set(1, 2, 3, 4, 5, 6).getClass res0: Class[_ <: scala.collection.immutable.Set[Int]] = class scala.collection.immutable.HashSet$HashTrieSet 

At the same time, find should always iterate over all the HashSet , since it is unsorted, so it will be O(n) . Conversely, a search operation, for example, contains , will be O(1) .

Here's a more detailed link about the performance of scala collections in general.

Speaking of Map , the same concepts apply. The implementation of Map optimized up to 4 elements, and then.