Start learning free

LESSON 240 OF 348 · HASH TABLE

Hash Sets in Kotlin: HashSet, toHashSet and hashSetOf

Lesson Read the full explanation

Hash Sets are collections of unique items i.e no element can be repeated.

Hash Sets were designed to give us a way of adding and looking for unique values in a collection in a quick manner.

The values in a Hash Set can be either simple primitives like strings or integers as well as more complex object types like object literals or arrays.

In Java, the Hash Set is implemented as a HashSet object.

Creation:

To create a new empty HashSet that holds Strings, you use the following syntax:

val mySet = hashSetOf<String>()

Creating an empty Set takes O(1) time.

Constructing from iterable

The Set constructor also accepts an optional iterable object. If you pass an iterable object to the Set constructor, all the unique elements of the object will be added to the new set:

val elements = listOf("b", "c", "c", "d")
val mySet = elements.toHashSet()

// mySet contains {"b", "c", "d"}

This takes O(n) time, where n is the number of elements in the iterable object.

Adding elements:

To add an element to the set, you use the add() method:

val elements = listOf("b", "c", "c", "d")
val mySet = elements.toHashSet()

// Adding new elements
mySet.add("x")

// Adding an existing element
mySet.add("d") // nothing happens

// mySet contains {"b", "c", "d", "x"}

The Set first checks if that element already exists and if so, it does nothing and also doesn't raise an error.

Adding an element to a Set takes O(1) time.

Checking if a value exists:

To check if a Set has a specific element, you use the contains() method which returns true if the set contains the element, otherwise, it returns false.

val elements = listOf("b", "c", "c", "d")
val mySet = elements.toHashSet()

var exists = mySet.contains("c") // exists is true

exists = mySet.contains("x") // exists becomes false

Checking if a value exists in a Set takes O(1) time.

Removing elements:

To delete a specified element from a set, you use the remove() method:

val elements = listOf("b", "c", "c", "d")
val mySet = elements.toHashSet()

// Deleting elements
mySet.remove("c")

// Deleting a non-existent element
mySet.remove("z") // does nothing

// mySet contains {"b", "d"}

The Set first checks if that key exists and if not, it does nothing and also doesn't raise an error, so it's safe to delete non-existing elements.

Removing an element from a Set takes O(1) time.

Iterating over the Set values:

If we want to iterate over values of the Set, we can use the for loop along with the : operator:

val elements = listOf("b", "c", "c", "d")
val mySet = elements.toHashSet()

for (value in mySet) {
    println(value)
}

// This will print the following:
// b
// c
// d

Iterating over a Set takes O(n) time.

Space Complexity

A Set uses O(n) space, where n is the number of elements existing in the Set.

Assignment
Follow the Coding Tutorial and let's play with some Hash Sets.

Hint
Look at the examples above if you get stuck.

STEP 1 OF 6
    Ctrl + Enter to check

    KOTLIN · HASH TABLE

    Hash Set in Kotlin, explained

    What a hash set is

    A set is a collection that holds each value at most once. A hash set is a set built on hashing, which makes three operations fast: adding a value, checking whether a value is present and removing a value. Each takes constant time on average, no matter how many elements the set holds. That is the reason to reach for one whenever a problem asks "have I seen this before?" or "which values are unique?".

    In Kotlin the hash set is HashSet, which is the Java class of the same name made available under the name HashSet in every Kotlin file. The elements can be numbers, strings or objects, as long as their type has a sensible equals and hashCode; the standard types all do.

    Creating a hash set

    There are three common ways. All of them give you a HashSet you can change:

    val a = HashSet<String>()          // empty, you name the element type
val b = hashSetOf<String>()        // the same, as a helper function
val c = hashSetOf("x", "y", "x")   // holds "x" and "y"

    To build a set from data you already have, call toHashSet() on an array or a list. Duplicates are dropped as the elements go in:

    val elements = listOf("b", "c", "c", "d")
val mySet = elements.toHashSet()
println(mySet.size)   // 3

    Building from a collection of n elements takes O(n) time. Kotlin also has toSet(), but its result is typed as a read-only Set: it has no add or remove, so code that tries to change it doesn't compile. Use toHashSet() when you need to change the set afterwards.

    Adding, checking and removing

    val mySet = hashSetOf("b", "c", "d")

println(mySet.add("x"))        // true: it was new
println(mySet.add("d"))        // false: it was already there
println(mySet.contains("c"))   // true
println("z" in mySet)          // false, same as contains
println(mySet.remove("c"))     // true: it was removed
println(mySet.remove("z"))     // false: nothing to remove

    Three details are worth knowing:

    • add returns a Boolean: true when the value was new, false when the set already had it. Adding a duplicate is not an error and changes nothing, so code often calls add without checking first.
    • remove works the same way: it returns whether something was removed, and removing a missing value is safe.
    • in is the idiomatic spelling of contains. !in checks for absence.

    Looping over a set

    A set is iterable, so a for loop with in visits each element once:

    for (value in mySet) {
    println(value)
}

    A loop over a set takes O(n) time, and the set itself uses O(n) space. The important gotcha is the order. A hash set does not promise any order: elements may come out in a different order than you added them, and you shouldn't write code that depends on a particular one. If you need insertion order, Kotlin's linkedSetOf and mutableSetOf keep it, but those are a different kind of set.

    The exercise, step by step

    The lesson walks through every operation on a small list of fruit.

    1. Start with data that has a duplicate. fruitsArray is declared with val and arrayOf, holding "apples", "bananas" and "apples".
    2. Convert it to a set. fruits is fruitsArray.toHashSet(). The second "apples" is dropped, leaving two elements.
    3. Add a value. fruits.add("oranges") grows the set, because "oranges" wasn't there.
    4. Check membership. An if with fruits.contains("apples") prints We have apples when the check is true.
    5. Remove a value. fruits.remove("bananas") takes it out.
    6. Loop and print. A for (fruit in fruits) loop prints what is left, which shows that the duplicate and the removed fruit are gone.

    The complete solution:

    val fruitsArray = arrayOf("apples", "bananas", "apples")

val fruits = fruitsArray.toHashSet()

fruits.add("oranges")

if (fruits.contains("apples")) {
    println("We have apples")
}

fruits.remove("bananas")

for (fruit in fruits) {
    println(fruit)
}

    It prints We have apples, followed by apples and oranges on separate lines. The order of those last two lines is up to the hash set.

    Common mistakes

    • Expecting a fixed order. Don't compare the printed output of a hash set to a fixed list unless you sort it first.
    • Using toSet() and then calling add. The read-only Set type has no such method, so the compiler rejects the call. Use toHashSet().
    • Forgetting the element type on an empty set. hashSetOf() with no arguments can't infer the type, so write hashSetOf<String>() or declare the variable's type.
    • Treating val as "frozen". val fruits only stops you from pointing the variable at a different set. You can still add to and remove from the set it refers to.
    • Putting mutable objects in a set. If an element's contents change after it is added, its hash changes and the set can no longer find it.

    Key takeaways

    • A hash set stores unique values and gives average constant-time add, contains and remove.
    • Create one with HashSet<T>(), hashSetOf or toHashSet().
    • add and remove return a Boolean and are safe to call with duplicates or missing values.
    • Iteration is O(n) and the order is unspecified.
    • The set uses O(n) space.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free