Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 134 ยท Collections

Sets

Learn Kotlin sets: setOf and mutableSetOf, removing duplicates, LinkedHashSet vs HashSet vs sorted sets, union, intersect, subtract, equality rules and common pitfalls, with runnable code.

A set is a collection of distinct elements. Adding the same element twice does nothing the second time. That one rule makes sets the right tool for jobs like "which unique words appear in this text?", "have I seen this id before?" and "which users are in both groups?". Sets are also fast at the question "is this element in here?", usually in constant time, whereas a list has to look at the elements one by one.

This lesson shows how to create sets, how the three kinds of set order their elements, the set operations (union, intersection, difference), and the equality rules that decide whether two elements count as the same. It follows Collections Overview and Lists.

Creating sets

Kotlin Sets drop duplicates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is [red, green, blue], 3, true, false, [3, 1, 2], [3, 1, 2] and []. toSet() converts any collection into a set, which is the shortest way to remove duplicates. If you want to stay with a List, distinct() does the same and gives the list back. Both keep the first occurrence of each element.

A set has no index: colors[0] does not compile. You can still loop over a set, ask for first(), or turn it into a list with toList() when you need positions.

Changing a mutable set

Kotlin Adding and removing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

You see new: to, new: be, new: or, new: not, again: to, again: be, then [to, be, or, not], [to, be, x, y] and 4. The trick if (seen.add(x)) is the idiomatic way to detect "first time seen": add returns true only if the element was not yet present. Deduplicating while processing a stream of values is one of the most common uses of a set.

Three kinds of set

The set interface says nothing about order, but the implementation does. This matters when you print, loop or compare:

Created with Implementation Iteration order Lookup cost
setOf, mutableSetOf, linkedSetOf LinkedHashSet insertion order O(1)
hashSetOf HashSet unspecified O(1)
sortedSetOf TreeSet (Java) sorted order O(log n)
Kotlin Comparing set orders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is [pear, apple, fig], [apple, fig, pear], [pear, fig, apple], then apple, pear, [apple, fig] and fig. The sorted set (the JDK's TreeSet) keeps its elements ordered at all times and offers range-style queries: headSet("g") returns everything before "g", and ceiling("b") returns the smallest element that is >= "b". Choose it when you need ordered iteration or range queries. Choose the default (insertion-ordered) set when you want predictable output with fast lookups, and hashSetOf only if you have measured a need, because the unspecified order makes printed output unstable between runs and versions.

Never write tests, examples or documentation that depend on the order of a HashSet. Its order can change when elements are added or when the JDK changes. If the order matters, say so by choosing LinkedHashSet or a sorted set.

Set operations

Sets model the mathematics you know from school. Kotlin gives you both infix words and operators:

Kotlin Union, intersection and difference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is [ana, bo, cy, di, ed], [cy, di], [ana, bo], [ed], [ana, bo, cy, di, ed], [ana, bo], [ana, bo, ed], true and false. union, intersect and subtract are infix functions that accept any collection and return a Set. + and - do the same job for sets. The "either but not both" (symmetric difference) example subtracts the intersection from the union; there is no dedicated function for it.

Set operations on big collections are fast because contains is O(1). If you find yourself writing list1.filter { it in list2 }, convert list2 to a set first: val lookup = list2.toSet(). A loop over n elements with a list lookup costs O(n ร— m); with a set it is O(n).

What counts as "the same element"

A set decides whether two elements are equal using equals and hashCode (HashSet and LinkedHashSet) or the comparison (TreeSet). For strings and numbers this just works. For your own classes, you must get it right:

Kotlin Plain classes versus data classes in a set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

This prints 2, 2, [DataPoint(x=1, y=2), DataPoint(x=2, y=1)], true and false. A plain class inherits identity-based equals from Any, so two PlainPoint(1, 2) objects are two different elements. A data class generates equals and hashCode from its properties, so equal data means equal elements. See Equality and Identity for the rules.

Do not mutate elements inside a set

If you change a property that is part of hashCode after the object is in a HashSet, the set can no longer find it:

Kotlin A mutated element gets lost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is true, false, 1 and true. The element is still in the set (the size is 1 and you can iterate to it) but it sits in the bucket for its old hash code, so contains looks in the wrong place. Keep set elements and map keys immutable, which is another reason to prefer val in data classes.

Typical uses

Kotlin Unique words and duplicate detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

The output is [and, bat, cat, hat, the], 8 words, 5 unique, false, true, 7 and null. toSortedSet() creates a sorted set from any collection. firstDuplicate stops at the first repeated value, which is more efficient than building the whole set when duplicates are common.

Ranges and sets

A range such as 1..5 is not a set, but you can ask a range for in quickly, and convert it with toSet() if you need set operations. Use in for ranges and sets alike: if (x in 1..5) is O(1) and needs no collection at all.

Pitfalls

  • Assuming an order. setOf returns a LinkedHashSet, so it keeps insertion order today, but its declared type is just Set. Use linkedSetOf or sortedSetOf when the order is part of your program's meaning.
  • Mutable elements. Covered above; changing a field used by hashCode loses the element.
  • Indexing. A Set has no get(index). If you need positions, use a List.
  • Sorted sets need comparable elements. A TreeSet of objects that are not Comparable fails at run time unless you give it a comparator.
  • Floating-point elements. 0.1 + 0.2 and 0.3 are different doubles; do not use floating-point values as set elements for exact membership.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does listOf(1, 2, 2, 3, 3, 3).toSet().size return?

    A set keeps only distinct elements: 1, 2 and 3.
  2. 2. What does mutableSetOf<Int>().add(5) return the first time you call it?

    add returns true when the element was new and false when it was already present.
  3. 3. Which function keeps its elements in sorted order?

    sortedSetOf creates a TreeSet. setOf and linkedSetOf keep insertion order, and hashSetOf has no defined order.
  4. 4. What is setOf(1, 2, 3) intersect setOf(2, 3, 4)?

    The intersection holds the elements present in both sets: 2 and 3.
  5. 5. Why do two PlainPoint(1, 2) objects count as two elements in a set while two DataPoint(1, 2) objects count as one?

    Sets rely on equals and hashCode. A plain class inherits identity-based versions; a data class generates value-based ones.

Summary

  • A set stores distinct elements and answers in quickly; toSet() and distinct() remove duplicates.
  • add on a mutable set returns whether the element was new, which is perfect for first-seen checks.
  • setOf and linkedSetOf keep insertion order, hashSetOf has no defined order, sortedSetOf keeps elements sorted.
  • union, intersect, subtract, + and - work like set algebra.
  • Element equality uses equals and hashCode; use data classes and keep elements immutable.
  • A set has no indexes; convert to a list when you need positions.

Next: Maps