Welcome to our exploration of Kotlin Sets! Sets in Kotlin are collections that hold only distinct values, ensuring that no element appears more than once. They are ideal when uniqueness is a requirement within your data collection.

In this lesson, you'll gain knowledge of creating and working with sets in Kotlin. This includes understanding both immutable and mutable sets and how sets improve performance in specific operations. Let's get started!

In Kotlin, you can create sets using setOf() for immutable sets and mutableSetOf() for sets that can change.

Kotlin
Copy to clipboard
1// Creating immutable and mutable sets
2fun main() {
3  val mySet = setOf(1, 2, 3, 4, 5, 5, 5)  // Duplicates are automatically removed
4  val myMutableSet = mutableSetOf(1, 2, 3, 4, 5, 5, 5)  // Similar behavior for mutable sets
5
6  println(mySet)  // Output: [1, 2, 3, 4, 5]
7  println(myMutableSet) // Output: [1, 2, 3, 4, 5]
8}

Kotlin provides various functions to manipulate these sets. Particularly for MutableSet, functions such as add(), remove(), and contains() are available:

Kotlin
Copy to clipboard
1fun main() {
2    val myMutableSet = mutableSetOf(1, 2, 3, 4, 5)
3
4    // Adding an element
5    myMutableSet.add(6)  // `myMutableSet` is now [1, 2, 3, 4, 5, 6]
6
7    println(myMutableSet.contains(1)) // Output: true, as `myMutableSet` includes an element 1
8
9    // Removing an element
10    myMutableSet.remove(1)  // `myMutableSet` becomes [2, 3, 4, 5, 6]
11
12    println(myMutableSet.contains(1)) // Output: false, as `myMutableSet` doesn't include 1 anymore
13
14    // Discarding an element (safe removal)
15    myMutableSet.remove(7)  // No changes - 7 doesn't exist in `myMutableSet`
16}

• add(): Adds an element to the MutableSet. If the element is already present, the set remains unchanged.
• contains(): Checks if a specific element is present in the set, returning true or false.
• remove(): Removes an element from the MutableSet; if the element isn't present, the set remains unchanged, indicating safe removal.

Kotlin has built-in operations for sets such as union(), intersect(), and subtract(), which can be utilized both as functions and operators.

Kotlin
Copy to clipboard
1fun main() {
2    val set1 = setOf(1, 2, 3, 4)
3    val set2 = setOf(3, 4, 5, 6)
4
5    // Set union
6    println(set1 union set2)
7    // Output: [1, 2, 3, 4, 5, 6]
8
9    // Set intersection
10    println(set1 intersect set2)
11    // Output: [3, 4]
12
13    // Set difference
14    println(set1 subtract set2)
15    // Output: [1, 2]
16}

• union(): Combines elements from both sets without duplicates, resulting in {1, 2, 3, 4, 5, 6} for set1 union set2.
• intersect(): Outputs elements found in both sets, leading to {3, 4} in this example.
• subtract(): Results in the unique elements from the first set, yielding {1, 2} for set1 subtract set2.

Sets in Kotlin are advantageous for performance, especially for membership tests, thanks to their underlying structure.

Kotlin
Copy to clipboard
1fun main() {
2    val mySet = (0..999999).toSet() // A set of 10^6 elements
3    val myList = (0..999999).toList() // A list with the same elements
4
5    // Measure time for set lookup
6    val startSet = System.currentTimeMillis()
7    println(mySet.contains(999999)) // Fast lookup due to set properties ~ 1ms
8    val endSet = System.currentTimeMillis()
9    println("Set lookup time: ${endSet - startSet} ms")
10
11    // Measure time for list lookup
12    val startList = System.currentTimeMillis()
13    println(myList.contains(999999)) // Slower lookup compared to set ~12ms
14    val endList = System.currentTimeMillis()
15    println("List lookup time: ${endList - startList} ms")
16}

Big-O Notation Comparison:

• Set Membership Test: Sets generally have a lookup time complexity of O(1) on average due to hash table implementation, allowing for constant-time complexity. This makes sets very efficient for checking the presence of an element.
• List Membership Test: Lists perform a sequential search with a time complexity of O(n), where the time increases linearly with the list size, making it much slower for membership checks, especially as the list grows larger.

The time measurement outputs depend on the environment and various factors such as processor speed, memory availability, and current system load. These external conditions can affect the precise time values you observe when running the membership test code.

Great job! You've learned about creating and manipulating sets in Kotlin, executing various operations, and appreciating the efficiency that sets introduce in handling unique elements. Keep experimenting to master these concepts, and happy coding in Kotlin!