How to efficiently select a random element from a Scala immutable HashSet -

i have scala.collection.immutable.hashset want randomly select element from.

i solve problem extension method this:

implicit class hashsetextensions[t](h: hashset[t]) {   def nextrandomelement (): option[t] = {     val list = h.tolist     list match {       case null | nil => none       case _ => (list (random.nextint (list.length)))     }   } } 

...but converting list slow. efficient solution?

warning answer experimental use only. real project should use own collection types.

so did research in hashset source , think there little opportunity someway extract inner structure of valuable class hashtrieset without package violation.

i did come code, extended ben reich's solution:

package scala.collection  import scala.collection.immutable.hashset import scala.util.random  package object random {   implicit class hashsetrandom[t](set: hashset[t]) {     def randomelem: option[t] = set match {       case trie: hashset.hashtrieset[t] => {         trie.elems(random.nextint(trie.elems.length)).randomelem       }       case _ => some(set.size) collect {         case size if size > 0 => set.iterator.drop(random.nextint(size)).next       }     }   } } 

file should created somewhere in src/scala/collection/random folder

note scala.collection package - thing makes elems part of hashtrieset visible. solution think, run better o(n). current version should have complexity o(ln(n)) of immutable.hashset's operation s.

another warning - private structure of hashset not part of scala's standard library api, change version making code erroneous (though it's didn't changed since 2.8)