Start learning free

LESSON 264 OF 415 · HASH TABLE

Hash Set in Swift: Using Set

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 arrays of hashable values or your own types that conform to Hashable.

In Swift, the Hash Set is implemented as a Set type.

Creation:

To create a new empty Set that holds String values, you use the following syntax:

var mySet = Set<String>()

Creating an empty Set takes O(1) time.

Constructing from a sequence

The Set initializer can also take any sequence, such as an array. If you pass a sequence to the Set initializer, all the unique elements of the object will be added to the new set:

let elements = ["b", "c", "c", "d"]
var mySet = Set(elements)

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

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

Adding elements:

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

let elements = ["b", "c", "c", "d"]
var mySet = Set(elements)

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

// Adding an existing element
mySet.insert("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.

let elements = ["b", "c", "c", "d"]
var mySet = Set(elements)

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:

let elements = ["b", "c", "c", "d"]
var mySet = Set(elements)

// 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 element 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 with in:

let elements = ["b", "c", "c", "d"]
var mySet = Set(elements)

for val in mySet {
    print(val)
}

// This prints b, c and d, each on its own line, in an unspecified order
// (a Set has no fixed order and it can change between runs)

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

    SWIFT · HASH TABLE

    Hash Set in Swift, explained

    What a hash set is

    A hash set stores unique values. Adding a value that is already there changes nothing, and asking whether a value is present is fast: constant time on average, no matter how many values the set holds. That makes a set the right tool when you need to remove duplicates or answer "have I seen this before?" many times.

    In Swift the hash set is the Set type. Its elements must be Hashable, which covers Int, String, Bool, Double and your own types that adopt the protocol. Arrays of hashable elements are hashable too.

    Creating a set

    An empty set needs its element type spelled out, because Swift can't guess it:

    var mySet = Set<String>()

    You can also build a set from any sequence, and the duplicates are dropped:

    let elements = ["b", "c", "c", "d"]
var mySet = Set(elements)
print(mySet.count)

    3

    Creating an empty set is O(1). Building one from a sequence of n elements is O(n). A set literal needs a type annotation, because a bare literal in square brackets is an array: let a: Set = [1, 2, 3].

    Adding, checking and removing

    insert adds a value, contains checks for one, and remove deletes one. All three take O(1) time on average.

    var fruits = Set(["apples", "bananas"])

let first = fruits.insert("oranges")
print(first.inserted)

let again = fruits.insert("apples")
print(again.inserted)

print(fruits.contains("apples"))
print(fruits.contains("pears"))

print(fruits.remove("bananas") as Any)
print(fruits.remove("pears") as Any)

    true
false
true
false
Optional("bananas")
nil

    Both insert and remove return a result, and Swift lets you ignore it. insert returns a tuple whose inserted field says whether the value was new. remove returns the removed element as an optional, or nil when the value wasn't there. Neither raises an error for a duplicate or a missing value, so removing something that isn't in the set is safe.

    Iterating, and the order problem

    A for-in loop visits every element in O(n) time:

    for fruit in fruits {
    print(fruit)
}

    A set has no meaningful order, and Swift deliberately varies it: the same program can visit the elements in a different order each time it runs. Never rely on the order of iteration. When you need a predictable order, for printing or comparing, call sorted() first, which returns an array:

    let ids = Set([3, 1, 2])
print(ids.sorted())

    [1, 2, 3]

    A set uses O(n) space for n elements. Sets also support the usual set algebra: with a = [1, 2, 3] and b = [3, 4], a.union(b) holds 1, 2, 3 and 4, a.intersection(b) holds only 3, and a.subtracting(b) holds 1 and 2.

    The exercise, step by step

    1. Start with data that has a duplicate. fruitsArray is a let array holding "apples", "bananas" and "apples". Swift infers [String].
    2. Build the set. var fruits = Set<String>(fruitsArray) keeps one "apples". It is a var because the next steps change it.
    3. Insert a new fruit. fruits.insert("oranges") grows the set to three elements.
    4. Check membership with if fruits.contains("apples") and print We have apples.
    5. Remove one with fruits.remove("bananas"). The returned optional is ignored.
    6. Loop over the set with for fruit in fruits and print each one. It shows only apples and oranges: the duplicate collapsed and the banana is gone, in whichever order Swift visits them.

    The full program

    let fruitsArray = ["apples", "bananas", "apples"]

var fruits = Set<String>(fruitsArray)

fruits.insert("oranges")

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

fruits.remove("bananas")

for fruit in fruits {
    print(fruit)
}

    Gotchas

    • Sets are value types. Assigning a set to another variable copies it, and insert and remove change the set, so the variable must be var. Calling insert on a let set is a compile error.
    • No indexing. You can't write fruits[0]. A set has no positions; use contains to ask about a value.
    • Array lookup is slower. array.contains(x) scans the array in O(n), while set.contains(x) is O(1) on average.

    Key takeaways

    • Set holds unique, hashable values with no defined order.
    • insert, contains and remove run in constant time on average.
    • Building a set from an array removes its duplicates in O(n).
    • Use sorted() whenever the order of the output matters.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free