Created:        2024-05-08 Wed
Last modified:  2025-04-21 Mon

Scala 3: Collections¶

Mutable Iterables

^trait Iterable
- ^class PriorityQueue: a heap

Immutable Seqs

^trait Seq [List]
- ^trait IndexedSeq [Vector] : indexed sequence that have efficient `apply` and `length`
  - ^abstr ArraySeq : backed by an array
  - ^class NumericRange
  - ^class Range
  - ^class Vector : radix-balanced finger tree of width 32, efficient general-purpose data structure
- ^trait LinearSeq [List] : linear sequence that have efficient `head` and `tail`
  - ^abstr List : linked list, structural sharing, more like in Lisp, not Java
  - ^class LazyList : linked list with lazy evaluation
  - ^class Queue : implemented as a pair of `List`s: `in` and `out`

Mutable Seqs

^trait Seq [ArrayBuffer]
- ^class ListBuffer : backed by an immutable list, constant time prepend, append
- ^trait IndexedSeq [ArrayBuffer] : indexed sequence that have efficient `apply` and `length`
  - ^abstr ArraySeq : backed by an array, non-growable
  - ^trait IndexedBuffer [ArrayBuffer]
    - ^class ArrayDeque : a double-ended queue that internally uses a resizable circular buffer, `prepend` and `append` take constant amortized
      - ^class Queue
      - ^class Stack
    - ^class ArrayBuffer : backed by an array, `append` take constant amortized time

Immutable Maps

^trait Map [HashMap]
- ^abstr IntMap : a trie based on binary digits
- ^abstr LongMap : a trie based on binary digits
- ^class HashMap : Compressed Hash-Array Mapped Prefix-tree
- ^trait SeqMap [VectorMap] : trait for ordered maps
  - ^class ListMap : a list-based data structure, first inserted visiting order, inefficient
  - ^class TreeSeqMap : HashMap and a tree (adapted IntMap) for the ordering of the keys by insertion (default) or modification
  - ^class VectorMap : HashMap and Vector which preserves insertion order
- ^trait SortedMap [TreeMap] : key-value pairs are sorted, range queries are supported
  - ^class TreeMap : RedBlack tree

Mutable Maps

^trait Map [HashMap]
- ^class AnyRefMap : a hashtable with open addressing, basic map operations are faster than those in HashMap
- ^class CollisionProofHashMap: a hashtable with red-black trees in the buckets for good worst-case performance on hash collisions
- ^class HashMap : a hashtable; uses lists sorted by hash, not trees, for buckets
- ^class ListMap: backed by an immutable list, first inserted visiting order, deprecated, use an immutable.ListMap assigned to a var
- ^class LongMap: a hashtable with open addressing, basic map operations are faster than those in HashMap
- ^class OpenHashMap: deprecated, use LongMap, AneRefMap instead
- ^trait SeqMap [LinkedHashMap] : trait for ordered maps
  - ^class LinkedHashMap: HashMap implementation and linked list data structure, which preserves insertion order
- ^trait SortedMap [TreeMap] : key-value pairs are sorted, range queries are supported
  - ^class TreeMap : RedBlack tree

Immutable Sets

^trait Set [HashSet]
- ^class HashSet : Compressed Hash-Array Mapped Prefix-tree
- ^class ListSet : a list-based data structure, first inserted visiting order, inefficient
- ^trait SortedSet [TreeSet]
  - ^abstr BitSet
  - ^class TreeSet : RedBlack tree

Mutable Sets

^trait Set [HashSet]
- ^class HashSet : a hashtable; uses lists sorted by hash, not trees, for bins
- ^class LinkedHashSet : HashSet implementation and linked list data structure, which preserves insertion order
- ^trait SortedSet [TreeSet]
  - ^abstr BitSet
  - ^class TreeSet : RedBlack tree