1. 해시 테이블
-
해시 함수: key에 대한 산술 연산(SHA-1 등의 알고리즘이 다양하게 존재)을 이용하여 해시 주소값(해시 테이블의 index)으로 만들어 주는 함수.
-
해시 테이블: 해시 함수로 key ➡️ 해시 주소값으로 변경하고, 이 해시 주소값을 이용해 해시 테이블에 접근하여 값을 가져오거나 저장할 수 있다.
(해시 테이블은 내부적으로 배열 형태로 되어 있다.)
해시 테이블 충돌 시
1) chaining (개방 해싱/open hashing)
충돌 시 연결 리스트(linked list)를 이용하여 데이터를 추가로 뒤에 연결시켜서 저장.
(해시 테이블 저장 공간 이외의 공간 활용)
2) linear probing (폐쇄 해싱/close hashing)
충돌 시 해당 해시 주소값부터 순회하여 가장 처음에 나오는 빈 공간에 저장.
(해시 테이블 저장 공간 내부에서 충돌 해결 -> 저장 공간 활용도가 높으나, 큰 저장 공간이 필요하다.)
- 일반 배열 순회 시 시간 복잡도: O(n)
- 해시 테이블 순회 시 시간 복잡도: O(1)
(key 값을 해시하여 바로 index에 접근)
해시테이블의 장점 & 단점
| advantages👍🏻 | disadvantages👎🏻 |
|---|---|
| 평균적으로 빠른 검색, 삽입, 삭제 속도 (O(1)) | 해시 충돌이 발생할 수 있음 |
| key 기반 접근으로 효율적인 데이터 관리 (key에 대한 data 중복 확인이 용이) | 순서가 보장되지 않음 (정렬 불가능) |
| 다양한 자료 구조의 기반이 됨 (딕셔너리 등) | 해시 함수에 따라 성능 좌우됨 |
| 메모리 사용이 효율적일 수 있음 | 충돌 해결 방식에 따라 구현이 복잡할 수 있음 |
++ 딕셔너리는 해시 테이블로 구현되어 있다!
++ 딕셔너리의 key는 반드시 Hashable이어야 한다!
2. Hashable 프로토콜의 정의
protocol Hashable: Equatable {
func hash(into hasher: inout Hasher)
}• ✅Equatable을 상속하므로, == 비교도 구현되어야 함
Equatable을 상속하는 이유❓: 항상 hashValue가 unique하지 않기 때문이다. (해시 충돌의 가능성이 있기 때문에 추가로 동일한지 확인하는 Equatable이 필요하다!)
• hash(into:) 메서드를 통해 해시 값을 계산함
3. struct에서의 Hashable
기본 자료형(Int, String 등)은 이미 Hashable 프로토콜을 채택하고 있어, 별도로 구현하지 않아도 해시 기반 컬렉션(Dictionary, Set 등)에 바로 사용할 수 있다.
struct의 경우❓
어떤 프로퍼티로 해시해야 할지 명확하지 않기 때문에 Hashable을 별도로 채택하여 준수하는 것이 필요하다.
사용 예시
struct User: Hashable {
let id: Int
let name: String
}
// User의 모든 프로퍼티가 Hashable이라서 자동으로 Hashable 준수됨
let user1 = User(id: 1, name: "Alice")
let user2 = User(id: 2, name: "Bob")
let userSet: Set<User> = [user1, user2]
print(userSet.contains(user1)) // true
// Set은 내부적으로 hashValue를 사용하므로, User를 요소로 사용 가능구조체 내부의 프로퍼티가 모두 Hashable 타입이라면(= 기본 자료형이라면) Swift가 자동으로 Hashable, Equatable 등을 준수하기 위한 코드를 자동으로 구현해줌! (자동 합성)
4. class에서의 Hashable
클래스는 자동 합성이 지원되지 않기 때문에 직접 구현해주어야 한다.
class Car: Hashable {
let vin: String // 차량 고유번호
init(vin: String) {
self.vin = vin
}
// Equatable 요구 사항
static func == (lhs: Car, rhs: Car) -> Bool {
return lhs.vin == rhs.vin
}
// Hashable 요구 사항
func hash(into hasher: inout Hasher) {
hasher.combine(vin)
}
}
let car1 = Car(vin: "123ABC")
let car2 = Car(vin: "123ABC")
let car3 = Car(vin: "XYZ789")
let carSet: Set<Car> = [car1, car3]
print(carSet.contains(car2)) // true — car2는 car1과 vin이 같으므로❗️ 즉, 클래스에서는 Hashable을 쓰려면 ==와 hash(into:) 모두 직접 구현해야 한다.
5. enum에서의 Hashable
1) 연관 값이 없는 열거형
Hashable을 명시적으로 채택하지 않아도 자동으로 Swift가 Hashable, Equatable을 암묵적으로 채택 및 구현해준다.
2) 연관 값이 있는 열거형 (단, 연관 값이 Hashable 타입)
Hashable을 명시적으로 채택해야 한다.
enum Status: Hashable { // Hashable 명시적으로 채택
case success(code: Int)
case failure(reason: String)
}
let status1 = Status.success(code: 200)
let status2 = Status.failure(reason: "Timeout")
let statusSet: Set<Status> = [status1, status2]
print(statusSet.contains(.failure(reason: "Timeout"))) // ✅ true3) 연관 값이 있는 열거형 (❌ 예외: 연관 값 중 하나라도 Hashable이 아닌 경우)
struct NotHashableStruct {
let value: Int
}
enum MyEnum {
case test(NotHashableStruct) // ❌ NotHashableStruct가 Hashable을 따르지 않음
}연관 값이 있고, 그 값이 Hashable을 따르지 않으면 자동 합성이 불가능해 직접 ==와 hash(into:)를 구현해야 한다.
< 💻example code >
struct NotHashableStruct {
let value: Int
}
enum MyEnum: Hashable {
case test(NotHashableStruct)
// ❗️NotHashableStruct가 Hashable을 따르지 않기 때문에, 그 안에 들어있는 value만 비교/해싱하는 방식으로 수동 처리
static func == (lhs: MyEnum, rhs: MyEnum) -> Bool {
switch (lhs, rhs) {
case let (.test(a), .test(b)):
return a.value == b.value
}
}
func hash(into hasher: inout Hasher) {
switch self {
case let .test(val):
hasher.combine(val.value)
}
}
}
``