Collection Types

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.

// 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<Criterion>) {
    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<Int> = 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?

// Main.kt — a read-only interface is a view of the same object
fun main() {
    val editable = mutableListOf(1, 2)
    val view: List<Int> = editable
    val snapshot = editable.toList()
    editable.add(3)
    println(view)
    println(snapshot)
    println(view === editable)
    println(snapshot === editable)
    println((view as MutableList<Int>).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.

// 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<Int>() and emptyList<String>().

// 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<Int>(), emptyList<Int>(), emptyList<String>()),
    )
    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<Int>() and emptyList<String>() 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.

// 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.

// 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.

// 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?