Производительность реализаций неизменяемых множеств в Scala

Недавно я погрузился в Scala и (возможно, предсказуемо) потратил довольно много времени на изучение API неизменяемых коллекций в стандартной библиотеке Scala.

Я пишу приложение который обязательно выполняет много +/- операций на больших наборах. По этой причине я хочу убедиться, что выбранная мной реализация представляет собой так называемую «постоянную» структуру данных, чтобы избежать копирования при записи. Я видел этот ответ Мартина Одерски, но это не совсем прояснило для меня проблему.

Я написал следующий тестовый код для сравнения производительности ListSet и HashSet для операций добавления:

import scala.collection.immutable._

object TestListSet extends App {
  var set = new ListSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

object TestHashSet extends App {
  var set = new HashSet[Int]
  for(i <- 0 to 100000) {
    set += i
  }
}

Вот примерное измерение времени выполнения HashSet:

$ time scala TestHashSet

real    0m0.955s
user    0m1.192s
sys     0m0.147s

And ListSet:

$ time scala TestListSet

real    0m30.516s
user    0m30.612s
sys     0m0.168s

Минусы односвязного списка - это операция с постоянным временем, но эта производительность выглядит линейной или хуже. Связано ли это снижение производительности с необходимостью проверять каждый элемент набора на предмет равенства, чтобы он соответствовал инварианту набора без дубликатов? Если это так, я понимаю, что это не связано с «постоянством».

Что касается официальной документации, все, что я смог найти, это следующая страница, но она кажется неполной: Scala 2.8 Collections API - Характеристики производительности . Поскольку ListSet изначально кажется хорошим выбором из-за занимаемой им памяти, возможно, в документации по API должна быть некоторая информация о его производительности.