Когда использовать Scala TreeMap?

Question

Учитывая следующий пример из TreeMap:

scala> import scala.collection.immutable.TreeMap 
import scala.collection.immutable.TreeMap 

scala> val tm = TreeMap(("foo" -> List(2,1))) 
tm: scala.collection.immutable.TreeMap[String,List[Int]] = Map(foo -> List(2, 1)) 

scala> tm + ("bar" -> List(300, 4)) 
res0: scala.collection.immutable.TreeMap[String,List[Int]] = Map(bar -> List(300, 4), foo -> List(2, 1)) 

scala> res0 + ("bippy" -> List(4)) 
res1: scala.collection.immutable.TreeMap[String,List[Int]] = Map(bar -> List(300, 4), bippy -> List(4), foo -> List(2, 1)) 

Это не для меня ясно, как, когда это выгодно использовать TreeMap над Map. Когда это?

Answer 1

TreeMap гарантирует, что записи, находящиеся на карте, отсортированы в порядке, используя ключи, где Map не предоставляет такую ​​гарантию.

Итак, если вы хотите заказать ключи на карте, используйте TreeMap, иначе обычной карты будет достаточно. Место, где я использую TreeMap, генерирует токены для Twitter's API. Чтобы создать токен, требуется, чтобы строка была создана с использованием параметров url, которые сортируются лексиграфически. Я получаю url params на карте, а затем помещаю его в TreeMap, чтобы отсортировать его.

Идя немного глубоко -

Scala использует Hash Tries создать HashMap (что реализация по умолчанию карты), где структура данных является Trie и ключи хэшируются. Кроме того, Scala оптимизирует HashMap, когда размер меньше 5 (source). Он обеспечивает постоянный поиск и стоимость вставки в обычных случаях.

С другой стороны, TreeMaps построены с использованием Red Black trees. Красное Черное дерево имеет поиск и стоимость вставки O (ln n).

Итак, используйте карту, если вы не хотите, чтобы ключи сортировались для лучшей производительности.

Более подробная информация в коллекции docs