--- title: 'Collection Types' source: 'https://academia.sh/en/courses/kotlin/collection-types' course: 'The Kotlin Language' language: en updated: '2026-10-21T05:02:39+00:00' license: 'CC BY-SA 4.0' objectives: - 'Measures that a read-only List interface can be a view of the same mutable object' - "Reads from the output that a list's equality rests on its content, not its type" - 'Shows that the equality of a set and a map is independent of element order' - 'Separates the null a map returns for a missing key from the exception that a getValue call throws' --- # Collection Types Measures that a read-only interface does not mean immutability, that a list's equality comes from its content, and that sets and maps compare equal regardless of order. The previous lesson, "Generics and Variance", showed that a type parameter is erased at run time. This lesson goes through the structures that carry type parameters most often: collections. A program almost always works on several values at once: order lines, user names, setting keys. Kotlin offers three basic collections for them: the ordered **list (`List`)**, which allows duplicates; the **set (`Set`)**, which does not; and the **map (`Map`)**, which goes from a key to a value. Each of the three has two faces. The `List`, `Set` and `Map` interfaces declare only read operations: the element count, access to an element, the containment question. The operations that add and remove elements live in `MutableList`, `MutableSet` and `MutableMap`. The language has two names for this split, and they must not be confused. A collection is **read-only** when the interface we hold offers no write operation. A collection is **immutable** when the object itself cannot change by any route. The first is a property of an interface, the second a property of an object. The lesson measures this difference, then asks what decides whether two collections count as equal. The shared question of this topic is: **what makes these two values equal?** There are four criteria. If the two values that come out equal are the same object, the criterion is **singleton**. If the twin is a separate object and is not equal, it is **identity**. If the twin is equal and the value that differs in one respect is not equal, it is **content**. If the different value comes out equal as well, it is **partial content**. Every measurement builds three values: `first`, its twin `twin` built separately by the same recipe, and `other`, which differs in one respect only. The `Criterion` class below compares the three with `===` and `==`, names the criterion and prints it as a line. The class is defined once and every measurement uses it; the rule sees the result, not the reason. ```kotlin // Criterion.kt — classifies the criterion that makes two values equal class Criterion(val label: String, first: Any?, twin: Any?, other: Any?) { val sameObject = first === twin val equalTwin = first == twin val equalOther = first == other val name: String = when { sameObject -> "singleton" !equalTwin -> "identity" !equalOther -> "content" else -> "partial-content" } fun report() { println("$label: same-object=$sameObject, twin=$equalTwin, other=$equalOther -> $name") } } fun summarize(checks: List) { for (name in listOf("singleton", "identity", "content", "partial-content")) { println("$name: ${checks.count { it.name == name }}") } } ``` This block has no output: it only defines the measuring tool and is compiled together with every block that follows. ## A Read-Only Interface, the Same Object The line `val view: List = editable` does not build a new list. The type on the left only says which operations are visible; the object on the right is the mutable list built with `mutableListOf`. So although no element can be added through `view`, an element added through `editable` shows up in `view`. For a real copy, `toList()` is used: the call builds a new list from the elements of that moment, and later changes do not reach it. The block below reads this from three questions: what does `view` show after the addition, what does `snapshot` show, and are the two the same object as `editable`? ```kotlin // Main.kt — a read-only interface is a view of the same object fun main() { val editable = mutableListOf(1, 2) val view: List = editable val snapshot = editable.toList() editable.add(3) println(view) println(snapshot) println(view === editable) println(snapshot === editable) println((view as MutableList).size) } ``` ``` [1, 2, 3] [1, 2] true false 3 ``` The first line shows that the addition is visible in `view`, and the second that `snapshot` stayed at the two elements from before the addition. The third line says that `view` is the same object as `editable`, and the fourth that the copy is a separate object. The last line gives a more uncomfortable result: `view`, whose type is read-only, can be cast to `MutableList`, and its size reads as `3`. So **a read-only type is not a guarantee of immutability**; it only states that no write can be made through that reference. If a function returns a `List` while handing out a mutable list internally as is, the caller may hold what it takes for its own list while the content shifts under it. The safe way is to hand out a copy with `toList()` when crossing the boundary. **CC1.** This measurement is for a list built with `mutableListOf`. Casting a list built with `listOf(...)` to `MutableList` and trying to change it, and the behavior of the other collection builders in this respect, were not measured separately. ## The Criterion: Content The question is what makes two lists equal. The first answer that comes to mind is the type: if one is a `MutableList` and the other a `List`, they differ. The measurement shows the opposite. The block below first compares a mutable and a read-only list with the same elements, then one built with `listOf` and one built with `arrayListOf`, using `==`. Then it classifies the same measurement with `Criterion`: `first` and `twin` are built separately by the same recipe (`mutableListOf(1, 2)`), and `other` is a list that differs only in its last element. ```kotlin // Main.kt — lists compare by content, not by type fun main() { println(mutableListOf(1, 2) == listOf(1, 2)) println(listOf(1, 2) == arrayListOf(1, 2)) val check = Criterion("list", mutableListOf(1, 2), mutableListOf(1, 2), listOf(1, 3)) check.report() } ``` ``` true true list: same-object=false, twin=true, other=false -> content ``` The first two lines show that lists of different types and implementations come out equal with the same elements. The third line names the criterion: it is not `singleton`, because the twin is a separate object; not `identity`, because the twin is equal; not `partial content`, because the different element does not come out equal. The remaining criterion is **content**. This is the criterion of the lesson: two lists are equal if they carry the same elements in the same order; which interface they are seen through or which class they come from does not change the result. This follows from structural equality (`==`) carrying the `equals` call down to the elements in collections. Referential equality (`===`), on the other hand, always comes out false for two separate lists and decides nothing here. **CC2.** This measurement is for `Int` lists with two elements. The equality of lists whose elements come from classes that do not define their own `equals` was not measured separately; that case is the subject of the next lesson. ## The Bounding Measurement The content criterion also includes the order information in a list: `listOf(1, 2)` and `listOf(2, 1)` are not equal even though they hold the same elements. If we ask the same question of a set and a map, we find the limit of the criterion. The block below prints five measurements at once. In the list, `other` is in reverse order. In the set and the map, `other` is also a collection that differs only in order; in the `map-value` measurement, though, `other` differs in one value. In the last measurement the type parameters of the two empty lists are deliberately kept different: `emptyList()` and `emptyList()`. ```kotlin // Main.kt — order is not a difference in sets and maps fun main() { val checks = listOf( Criterion("list", listOf(1, 2), listOf(1, 2), listOf(2, 1)), Criterion("set", setOf(1, 2), setOf(1, 2), setOf(2, 1)), Criterion("map", mapOf("a" to 1, "b" to 2), mapOf("a" to 1, "b" to 2), mapOf("b" to 2, "a" to 1)), Criterion("map-value", mapOf("a" to 1, "b" to 2), mapOf("a" to 1, "b" to 2), mapOf("a" to 1, "b" to 3)), Criterion("empty-list", emptyList(), emptyList(), emptyList()), ) for (check in checks) check.report() summarize(checks) } ``` ``` list: same-object=false, twin=true, other=false -> content set: same-object=false, twin=true, other=true -> partial-content map: same-object=false, twin=true, other=true -> partial-content map-value: same-object=false, twin=true, other=false -> content empty-list: same-object=true, twin=true, other=true -> singleton singleton: 1 identity: 0 content: 2 partial-content: 2 ``` The bounding measurement is this: **order is not a difference in sets and maps.** When the order changes in a list, equality breaks (`content`); the same change makes no difference in a set or a map (`partial-content`): the different value comes out equal as well. Set equality looks at the same group of elements, and order is not part of it; a map is compared by its key set and the value of each key, and the order in which the keys were written is outside that. The `map-value` line confirms the second point: when the order stays the same and one value changes, the map does not come out equal. The distribution of the four measurements splits 2/2 between two criteria; the fifth measurement shows something else. The result on the fifth line stands out in two ways. `emptyList()` and `emptyList()` are the same object, so the criterion is `singleton` and no comparison is needed at all. Moreover, because this empty list is a single shared object, two calls with different type parameters both return it; since the type parameter is erased at run time, `other` comes out equal to `first`. The type erasure of the previous lesson shows up here as a detail of collection equality. **CC3.** These measurements are for two-element collections and `emptyList`. The behavior when hash codes collide in larger sets, and sets whose elements do not define their own `hashCode`, were not measured separately. ## Map and Set Operations A map is used even more often than a list in daily work, but its read rule surprises in two places. Reading a missing key with `[]` returns `null`, so the result type is a nullable type (`Int?`). `getOrDefault` returns the value you give in the same situation. `getValue`, on the other hand, throws an exception (`NoSuchElementException`) for a missing key. The block below measures these three reads, the write operations and building a new map with the `+` operator together. `stock + ("banana" to 2)` does not change the existing map; it returns a separate map that contains the new key. The last two lines show a set built with `hashSetOf`: the iteration order of this set is not a guarantee, so the elements are printed sorted. ```kotlin // Main.kt — map reads fun main() { val stock = mutableMapOf("apple" to 3, "pear" to 5) println(stock["banana"]) println(stock.getOrDefault("banana", 0)) stock["apple"] = 4 stock.put("cherry", 1) println(stock.keys) println(stock.values.sum()) val copy = stock + ("banana" to 2) println(stock.size) println(copy.size) try { stock.getValue("banana") } catch (e: NoSuchElementException) { println(e::class.simpleName) } val tags = hashSetOf("b", "a", "b") println(tags.size) println(tags.sorted()) } ``` ``` null 0 [apple, pear, cherry] 10 3 4 NoSuchElementException 2 [a, b] ``` Reading it in order, the missing key returned `null`, and the given default returned `0`. `stock["apple"] = 4` changed the value of an existing key, and `put` added a new key; the keys stayed in the order `apple`, `pear`, `cherry`, and the values added up to `10` as `4 + 5 + 1`. The `copy` built with `+` carries four entries while `stock` stayed at three: the new map is separate. `getValue` threw the exception for the missing key and it was caught. The last two lines show that although `"b"` was added twice, the set has two elements and its sorted form is `[a, b]`. The practical rule that follows: for a key that may be missing, `[]` is used and the result is tied to a default with `?:` (the Elvis operator); for a key that should not be missing, `getValue` is used and the absence surfaces as an error. The choice between the two is also the contract of the map: who decides that the value read exists, the program or the data? **CC4.** These measurements are for a map built with `mutableMapOf` and a set built with `hashSetOf`. The iteration order of the map built with `mutableMapOf` coincided with insertion order in this measurement; this was not measured as a language guarantee, and no order was claimed for `hashMapOf`. ## Changing While Iterating One of the most common collection mistakes is removing an element from a list while iterating over the same list. The `for (x in list)` loop uses an iterator behind the scenes, and the iterator refuses to keep working when it notices that the collection changed by a route other than itself. The block below tries to remove the even numbers inside the loop in a four-element list; it prints the name of the thrown exception and the state of the list at that moment. Then the same job is done with `removeAll`. The last two lines show that a list and a set are not counted as equal even with the same elements, and that a set built from a list comes out equal regardless of order. ```kotlin // Main.kt — removing while iterating fun main() { val numbers = mutableListOf(1, 2, 3, 4) try { for (n in numbers) { if (n % 2 == 0) numbers.remove(n) } } catch (e: ConcurrentModificationException) { println(e::class.simpleName) } println(numbers) numbers.removeAll { it % 2 == 0 } println(numbers) println(listOf(1, 2) == setOf(1, 2)) println(listOf(2, 1).toSet() == setOf(1, 2)) } ``` ``` ConcurrentModificationException [1, 3, 4] [1, 3] false true ``` `2` was removed in the loop's second step and the list changed; the exception was thrown at the next `next()` call. That is why the list stayed in the state `[1, 3, 4]`; `4` was never checked. An even number still remaining in the list shows that the error is not only the exception but also a half-finished cleanup. `removeAll`, on the other hand, applies the condition to all the elements in a single pass and leaves `[1, 3]`. The rule is this: if a collection has to be cleaned by removing, the collection's own bulk operation such as `removeAll` or `retainAll` is used; no removal is made from the collection itself during iteration (the iterator's own `remove` method is the exception). The last two lines show that equality also depends on the type. A `List` and a `Set` with the same elements are not equal: list equality is defined only against another list, and set equality only against another set. So the list is converted to a set before the comparison; the converted `toSet()` comes out equal regardless of order. **CC5.** This measurement is for the `mutableListOf` list backed by `ArrayList`. Whether the exception is thrown when the removal is made at the second-to-last element of the list was not measured and is not written as a guarantee. ## The Cost of a Changing Element A set and a map place an element or a key by a number (the hash code). If the element is a mutable list and it is changed after it enters the set, the number changes but the set does not update the element's place. The result is an element that sits in the set but cannot be found when searched for. The block below adds a list to a set, adds an element to the list and searches the set in two ways: with the changed list itself and with a newly built list of the same content. The size is read in every case. ```kotlin // Main.kt — an element that changes after entering a set fun main() { val key = mutableListOf(1) val bag = hashSetOf(key) println(bag.contains(key)) key.add(2) println(bag.size) println(bag.contains(key)) println(bag.contains(mutableListOf(1, 2))) println(bag.any { it === key }) } ``` ``` true 1 false false true ``` Before the addition the search succeeds. After the addition the set size stays `1`, so the element was not removed; but the search fails both with the changed list and with a new list of the same content. The last line proves the element is still there: iterating over the set directly finds the same object. The element stays in the set, but the set can no longer reach it. This error is silent and throws no exception. The lesson is plain: values that will be set elements or map keys are chosen from types that do not change after they enter. `String`, numbers and data classes whose fields are all `val` and are themselves immutable are safe in this respect; `MutableList` is not. If a changing value is to become a key, a copy is taken first with `toList()` and the copy becomes the key. **CC6.** This measurement is for an `ArrayList` element inside a `HashSet`. The behavior of `LinkedHashSet` and tree-based sets in the same situation, and a changing element used as a map key, were not measured. ## Summary - The read-only `List`, `Set` and `Map` interfaces give no immutability guarantee; if a `MutableList` that points to the same object changes, the read-only view changes too. - `toList()` is used for a real copy; a function that crosses a boundary should not return a mutable collection as is, typed as `List`. - List equality looks at content and order, not at type. The criterion of this lesson: **content**. - The bounding measurement: order is not a difference in sets and maps (`partial-content`); the empty list is a singleton object and the type parameter does not affect equality. - A missing key in a map gives `null` with `[]` and an exception with `getValue`. ## Next Step This lesson measured the collection as a container of data. The next lesson moves on to the operations that produce new collections from the content of that container: `map`, `filter`, `fold`, `groupBy`. The same question comes back there too: if the same transformation is applied twice to the same list, what are the results equal by?