[Swift] Hashable 프로토콜 이해하기

Hashable 프로토콜: Hashable의 중요성

1. 해시 값의 개념:

해시 값은 객체를 대표하는 유일한 정수 값입니다. 이 값은 객체의 내용에 기반하여 계산되며, 동일한 객체는 항상 같은 해시 값을 가져야 합니다. 해시 함수는 이러한 해시 값을 생성하는 데 사용됩니다.

2. 효율적인 데이터 액세스:

Dictionary의 키나 Set의 원소로 사용될 때, 객체의 해시 값은 해당 객체의 저장 위치를 결정하는 데 사용됩니다. 이로 인해 데이터의 검색, 삽입, 삭제 등의 연산이 매우 빠르게 이루어질 수 있습니다.

배열(Array)

• 배열에서의 검색은 선형 검색(linear search)를 사용합니다. 이는 최악의 경우 모든 요소를 확인해야 하므로, 시간 복잡도는 O(n) 입니다. 여기서 n은 배열의 요소 수입니다.
• 배열에서 특정 값의 존재 여부를 확인하거나, 특정 값을 찾을 때 모든 요소를 순차적으로 확인해야 합니다.

해시 기반 구조 (Dictionary와 Set)

• Dictionary와 Set은 내부적으로 해시 테이블을 사용합니다. 이들 구조에서의 요소 검색, 삽입, 삭제 연산의 평균 시간 복잡도는 O(1) 입니다. 즉, 요소의 수와 상관없이 일정한 시간 안에 연산을 완료합니다.
• 그러나 해시 충돌이 발생하는 경우, 이 시간 복잡도는 최악의 경우 O(n) 까지 증가할 수 있습니다. 이는 해시 테이블에서 동일한 해시 값을 갖는 여러 요소들이 충돌하여, 연쇄적으로 검색 시간이 길어질 수 있기 때문입니다.

3. 고유한 해시 값의 중요성:

서로 다른 객체가 같은 해시 값을 가지는 경우를 '해시 충돌'이라고 합니다. 이럴 경우, 컬렉션의 성능이 저하될 수 있기 때문에, 가능한 한 고유한 해시 값을 생성하는 것이 중요합니다.

4. 예시: Hashable 프로토콜의 구현 및 사용

struct Book: Hashable {
    var title: String
    var author: String

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

var bookCollection: Set<Book> = []

let book1 = Book(title: "1984", author: "George Orwell")
let book2 = Book(title: "Brave New World", author: "Aldous Huxley")

bookCollection.insert(book1)
bookCollection.insert(book2)

이 예시에서, Book 구조체는 Hashable 프로토콜을 준수합니다. hash(into:) 메서드를 통해 title과 author 프로퍼티의 조합으로 고유한 해시 값을 생성합니다. 이 해시 값은 Set에 Book 인스턴스를 저장할 때 사용되어, 각 책 객체의 유일성을 보장하고 빠른 접근을 가능하게 합니다.

Hashable과 Equatable의 관계

모든 Hashable 타입은 자동으로 Equatable을 준수합니다. (이전에 정리한 내용을 확인해주세요!) 즉, 해시 가능한 객체는 그 객체의 동등성 비교도 가능해야 합니다. 이는 Hashable이 Equatable의 모든 기능을 포함하고, 추가로 해시 값의 생성 기능을 제공한다는 것을 의미합니다.

실제 예시

struct Player: Equatable, Hashable {
    var id: Int
    var name: String

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

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

// 사용 예
let player1 = Player(id: 1, name: "Alice")
let player2 = Player(id: 2, name: "Bob")

// Equatable을 사용한 비교
print(player1 == player2) // false

// Hashable을 사용한 Set 저장
var playersSet: Set<Player> = []
playersSet.insert(player1)
playersSet.insert(player2)

 

이 예시에서 Player 구조체는 두 프로토콜을 모두 준수하며, 이를 통해 객체의 동등성 비교와 해시 컬렉션에서의 사용이 가능합니다.

결론

Hashable과 Equatable 프로토콜은 Swift에서 객체의 동등성 비교와 데이터 관리를 위해 필수적입니다. 이 두 프로토콜을 적절히 활용함으로써, 사용자 정의 타입의 효율적인 관리 및 처리가 가능해집니다. Swift의 타입 시스템과 컬렉션 관리 기능을 최대한 활용하기 위해서는 이들 프로토콜의 이해와 적용이 매우 중요합니다.