Equatable, Hashable, Comparable protocols in Swift - Time & Space Complexity

Time Complexity: Equatable, Hashable, Comparable protocols

O(n)

Understanding Time Complexity

When using Equatable, Hashable, and Comparable protocols, we want to know how fast these operations run as data grows.

We ask: How does the time to compare or hash items change with more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Person: Equatable, Hashable, Comparable {
    let id: Int
    let name: String

    static func == (lhs: Person, rhs: Person) -> Bool {
        return lhs.id == rhs.id
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
    }

    static func < (lhs: Person, rhs: Person) -> Bool {
        return lhs.id < rhs.id
    }
}
    

This code defines how to check equality, create a hash, and compare two Person objects.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing or hashing the id property.
• How many times: Each comparison or hash runs once per call, but when used in collections, these operations repeat for many items.

How Execution Grows With Input

Each comparison or hash runs in constant time, but when checking many items, total time grows with the number of items.

Input Size (n)	Approx. Operations
10	10 comparisons or hashes
100	100 comparisons or hashes
1000	1000 comparisons or hashes

Pattern observation: The total work grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare or hash many items grows in a straight line as you add more items.

Common Mistake

[X] Wrong: "Comparing two objects always takes longer as the list grows."

[OK] Correct: Comparing two objects depends only on their properties, not the list size. The list size affects how many times you do comparisons, not the cost of one comparison.

Interview Connect

Understanding how these protocols work helps you explain how your code handles data efficiently, a skill useful in many coding challenges and real projects.

Self-Check

"What if the name property was a long string instead of a short one? How would that affect the time complexity of comparison?"

Practice

1.

Which protocol in Swift allows you to check if two instances of a type are equal using ==?

easy

A. Hashable

B. Codable

C. Comparable

D. Equatable

Solution

1. Step 1: Understand the purpose of Equatable

   Equatable protocol allows comparing two instances for equality using ==.

2. Step 2: Compare with other protocols

   Hashable is for hashing, Comparable is for ordering, Codable is for encoding/decoding.

3. Final Answer:

   Equatable -> Option D

4. Quick Check:

   Equality check = Equatable [OK]

Hint: Equality means Equatable protocol [OK]

Common Mistakes:

• Confusing Hashable with Equatable
• Thinking Comparable checks equality
• Mixing Codable with Equatable

2.

Which of the following is the correct way to declare a struct Person that conforms to Equatable and Hashable?

struct Person: ??? {
    var name: String
    var age: Int
}

easy

A. Equatable, Hashable

B. Comparable, Hashable

C. Equatable, Comparable

D. Codable, Hashable

Solution

1. Step 1: Identify needed protocols

   To compare equality and use in sets/dictionaries, use Equatable and Hashable.

2. Step 2: Check syntax for protocol conformance

   Protocols are listed separated by commas after colon in struct declaration.

3. Final Answer:

   Equatable, Hashable -> Option A

4. Quick Check:

   Equality + hashing = Equatable, Hashable [OK]

Hint: List protocols comma-separated after colon [OK]

Common Mistakes:

• Using Comparable instead of Equatable
• Forgetting commas between protocols
• Using Codable instead of Equatable

3.

What will be the output of the following Swift code?

struct Item: Comparable {
    var value: Int
    static func < (lhs: Item, rhs: Item) -> Bool {
        return lhs.value < rhs.value
    }
}

let items = [Item(value: 3), Item(value: 1), Item(value: 2)]
let sortedValues = items.sorted().map { $0.value }
print(sortedValues)

medium

A. [3, 2, 1]

B. [1, 2, 3]

C. [2, 3, 1]

D. Compilation error

Solution

1. Step 1: Understand Comparable conformance

   The < operator compares value properties to sort ascending.

2. Step 2: Analyze sorting and mapping

   Sorting the array orders items by value: 1, 2, 3. Mapping extracts values in this order.

3. Final Answer:

   [1, 2, 3] -> Option B

4. Quick Check:

   Sorted values ascending = [1, 2, 3] [OK]

Hint: Comparable sorts ascending by < operator [OK]

Common Mistakes:

• Assuming descending order by default
• Confusing map output with original array
• Forgetting to implement < operator

4.

Identify the error in this Swift struct that tries to conform to Hashable:

struct Book: Hashable {
    var title: String
    var pages: Int

    func hash(into hasher: inout Hasher) {
        hasher.combine(title)
    }
}

medium

A. Missing combine call for all properties in hash(into:)

B. Struct cannot conform to Hashable without Codable

C. Incorrect method signature for hash(into:)

D. Missing == operator implementation for Equatable

Solution

1. Step 1: Check Hashable requirements

   Hashable requires hashing all properties that affect equality.

2. Step 2: Analyze hash(into:) implementation

   Only title is combined; pages is missing, causing incorrect hashing.

3. Final Answer:

   Missing combine call for all properties in hash(into:) -> Option A

4. Quick Check:

   Hash all relevant properties [OK]

Hint: Hash all properties used in equality [OK]

Common Mistakes:

• Hashing only some properties
• Forgetting to implement == operator if needed
• Wrong method signature for hash(into:)

5.

You want to create a struct Player that can be stored in a Set, compared for equality, and sorted by score descending. Which protocols should Player conform to, and how should you implement the sorting?

hard

A. Conform to Equatable and Hashable; implement < to compare scores descending

B. Conform to Comparable only; implement < to compare scores ascending

C. Conform to Equatable, Hashable, Comparable; implement < to compare scores descending

D. Conform to Hashable only; sorting is automatic

Solution

1. Step 1: Identify needed protocols

   To store in Set and check equality, conform to Equatable and Hashable. To sort, conform to Comparable.

2. Step 2: Implement sorting logic

   Implement < operator to compare scores descending by reversing comparison.

3. Final Answer:

   Conform to Equatable, Hashable, Comparable; implement < for descending scores -> Option C

4. Quick Check:

   Set + equality + custom sort = Equatable, Hashable, Comparable [OK]

Hint: Use all three protocols; reverse < for descending sort [OK]

Common Mistakes:

• Forgetting Comparable for sorting
• Sorting ascending instead of descending
• Missing Equatable or Hashable for Set storage