CODEWITHSUNDEEP
scalasetshuffle
Sudheer Aedama
Sudheer Aedama

Reputation: 2144

Sort Order for Scala Set and shuffling

scala
Welcome to Scala version 2.10.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_79).
Type in expressions to have them evaluated.
Type :help for more information.

scala> 300 to 1000 toSet
warning: there were 1 feature warning(s); re-run with -feature for details
res0: scala.collection.immutable.Set[Int] = Set(645, 892, 809, ...)

// Question # 1: I expected that the order would be different when I ran this again. It's the same order as res0. So I thought, may be the range is too small to differ in order for different reason (system entropy etc.)

scala> 300 to 1000 toSet
warning: there were 1 feature warning(s); re-run with -feature for details
res1: scala.collection.immutable.Set[Int] = Set(645, 892, 809, ...)

// Question # 2: This is totally weird. Even after shuffling I see the same order. Why ?

scala> scala.util.Random.shuffle((300 to 1000).toSet)
res2: scala.collection.immutable.Set[Int] = Set(645, 892, 809, ...)

Upvotes: 0

Views: 334

Answers (2)

Mike Curry
Mike Curry

Reputation: 1609

The ordinary Sets makes no guarantees about order whatsoever. This means it can choose to store the data in any order it chooses to and deems to be the most efficient or convenient.

It may choose to store in a different order depending on the order that the items are given to it or it may not. It makes no guarantees.

Importantly, if it happens to do so in one version of scala, depending on this particular result would be dangerous as there is explicitly no guarantees.

So, I don't know why it chooses to have this result, but the result is effectively arbitrary and you cannot rely on it. Shuffling the Set has no concrete value, as the Set may choose to store them in any order it chooses regardless.

If you need order in a Set, then choose TreeSet or SortedSet which can make guarantees about the order that elements will be returned.

Somebody else with more knowledge about the internals of the Set implementation in scala may provide a more detailed answer on the specifics of the implementation.

As I understand the default immutable Set is a HashSet implementation and so, for any given Set of values, the buckets are unlikely to change regardless of the order they are inserted.

Upvotes: 2

Arne Claassen
Arne Claassen

Reputation: 14404

The standard immutable Set in scala is implemented as a Hash Tries. It's basically a tree using the hash code of the value added to it. That is how it efficiently detects values already existing in the Set.

Because the hash code of the added values are the same regardless of the order in which they are added to the set, it is reasonable for the Set to always be in the same order. The caveat, of course, is that this order is neither externally deterministic, nor is it guaranteed. So even if you liked the ordering of the Set, there is no guarantee that it will not change in any point release of the compiler or JVM

Upvotes: 2

Related Questions