[Swift] (자료구조) 해쉬 / Hash

Swift의 Hash (해시)와 관련 자료구조

Swift는 Hashable 프로토콜과 이를 기반으로 하는 자료구조를 통해 해시 개념을 구현합니다. Swift의 해시 구조는 효율적인 데이터 검색, 삽입, 삭제를 위해 사용되며, 주로 Set과 Dictionary에서 활용됩니다.

---

1. Swift의 해시(Hash) 개념

Hashable 프로토콜

• Swift에서 해시 가능한 객체는 Hashable 프로토콜을 준수해야 합니다.
• Hashable은 객체를 고유의 해시 값(Hash Value)으로 변환할 수 있도록 지원합니다.
• 사용 목적:
  • 객체를 딕셔너리(Dictionary)의 키로 사용하거나, 집합(Set)에서 중복 제거와 비교를 수행.
• 핵심 메서드:
  • hash(into:):
    • 객체의 해시 값을 계산.
  • ==:
    • 두 객체의 동등성을 비교.

struct Person: Hashable {
    let name: String
    let age: Int
}

let person1 = Person(name: "Alice", age: 25)
let person2 = Person(name: "Bob", age: 30)

// Dictionary에서 키로 사용 가능
let dictionary: [Person: String] = [person1: "Developer", person2: "Designer"]
print(dictionary[person1]!) // "Developer"

---

2. Swift 자료구조에서의 해시 활용

2.1. Dictionary

• 정의: 키-값 쌍으로 데이터를 저장하는 자료구조.
• 구현:
  • 내부적으로 해시 테이블을 사용하여 데이터의 빠른 검색, 삽입, 삭제를 지원.
• 시간 복잡도:
  • 평균: O(1) (검색, 삽입, 삭제 모두).
  • 최악: O(n) (충돌이 심할 경우).

var dictionary: [String: Int] = ["Alice": 25, "Bob": 30]
dictionary["Charlie"] = 35
print(dictionary["Alice"]!) // 25

2.2. Set

• 정의: 고유한 값만 저장하는 집합 자료구조.
• 구현:
  • 내부적으로 해시 테이블을 사용하여 중복 데이터를 방지하고 빠른 검색을 지원.
• 시간 복잡도:
  • 평균: O(1) (삽입, 삭제, 검색).
  • 최악: O(n) (충돌이 심할 경우).

var names: Set<String> = ["Alice", "Bob", "Charlie"]
names.insert("Alice") // 중복된 값은 추가되지 않음
print(names) // ["Alice", "Bob", "Charlie"]

---

3. 해시 함수와 Hashable의 구현

3.1. 기본 제공 해시 함수

• Swift는 기본 데이터 타입(Int, String 등)에 대해 최적화된 해시 함수를 제공합니다.
• 사용자 정의 타입은 Hashable 프로토콜을 준수하여 해시 값을 정의해야 합니다.

3.2. 사용자 정의 해시 함수

Hashable을 구현할 때 hash(into:) 메서드를 사용하여 고유한 해시 값을 생성할 수 있습니다.

struct Coordinate: Hashable {
    let x: Int
    let y: Int

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

    static func == (lhs: Coordinate, rhs: Coordinate) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }
}

let point1 = Coordinate(x: 3, y: 5)
let point2 = Coordinate(x: 3, y: 5)

print(point1 == point2) // true

---

4. 해시 충돌 해결

Swift의 Dictionary와 Set은 해시 충돌 발생 시 체이닝(Chaining) 기법을 사용합니다.

• 동일한 해시 값을 가지는 객체는 연결 리스트로 관리.
• 평균적으로 여전히 O(1)의 성능을 유지하지만, 충돌이 많아지면 O(n)으로 성능 저하 가능.

---

5. 해시 테이블(Hash Table)의 개념

해시 테이블은 데이터를 키-값(Key-Value) 쌍으로 저장하는 자료구조입니다. 데이터의 키를 특정 해시 함수(Hash Function)를 사용하여 해시 값으로 변환하고, 이 값을 인덱스로 활용하여 데이터를 저장하거나 검색합니다.

• 장점:
  • 빠른 검색, 삽입, 삭제 속도: 평균 시간 복잡도 O(1).
  • 데이터의 키를 기반으로 빠르게 접근 가능.
• 단점:
  • 해시 충돌 발생 가능.
  • 메모리 효율성이 떨어질 수 있음.

---

해시 테이블의 주요 구성 요소

1. 키(Key):
   • 저장하거나 검색할 데이터의 식별자.
   • 예: 사용자 ID, 이름 등.
2. 값(Value):
   • 키와 매핑된 실제 데이터.
   • 예: 사용자 정보.
3. 해시 함수(Hash Function):
   • 키를 고정된 크기의 해시 값으로 변환.
   • 해시 값은 배열의 인덱스로 사용.
   • 좋은 해시 함수는 충돌을 최소화해야 함.
4. 버킷(Bucket):
   • 동일한 해시 값을 가지는 데이터가 저장되는 공간.

---

해시 충돌(Hash Collision)

해시 충돌은 서로 다른 키가 동일한 해시 값을 가지는 경우 발생합니다. 이는 해시 함수가 입력 공간을 출력 공간으로 완벽히 매핑하지 못하기 때문입니다.

• 예: 키 apple과 peach가 동일한 해시 값으로 매핑된다면, 동일한 버킷에 저장되면서 충돌 발생.

---

충돌 해결 방법

해시 테이블은 충돌을 처리하기 위한 다양한 기법을 제공합니다. 주요 방법은 다음과 같습니다:

1. 개별 체이닝 (Separate Chaining)

• 방법:
  • 충돌이 발생하면 동일한 해시 값에 여러 데이터를 연결 리스트(Linked List) 형태로 저장.
• 장점:
  • 해시 테이블의 크기가 작아도 동작 가능.
  • 충돌 시에도 추가 데이터를 쉽게 저장.
• 단점:
  • 충돌이 많아지면 리스트가 길어져 검색 속도가 O(n)으로 감소.
• 예시:

Hash Index: 0  -> [Key1: Value1] -> [Key2: Value2]

2. 선형 탐사 (Linear Probing)

• 방법:
  • 충돌이 발생하면 인덱스를 한 칸씩 이동하며 빈 공간을 찾음.
• 장점:
  • 추가 메모리 사용이 없음.
• 단점:
  • 클러스터링 문제: 충돌이 연속적으로 발생하면 테이블 사용률이 낮아짐.
• 예시:

Hash Index: 0  -> [Key1: Value1]
             1  -> [Key2: Value2]

3. 이차 탐사 (Quadratic Probing)

• 방법:
  • 선형 탐사와 비슷하지만, 이동 거리를 제곱수로 증가시켜 충돌을 분산.
• 장점:
  • 클러스터링 문제 완화.
• 단점:
  • 특정 조건에서 사용 가능한 빈 공간을 찾지 못할 수 있음.
• 예시:

Hash Index: 0  -> [Key1: Value1]
             1  -> [Empty]
             4  -> [Key2: Value2]

4. 이중 해싱 (Double Hashing)

• 방법:
  • 충돌이 발생하면 두 번째 해시 함수를 사용하여 새로운 인덱스를 계산.
• 장점:
  • 탐사 횟수를 줄이고 충돌을 효과적으로 분산.
• 단점:
  • 두 개의 해시 함수를 설계해야 함.
• 예시:

Hash Index = (Hash1(Key) + i * Hash2(Key)) % TableSize

5. Cuckoo Hashing

• 방법:
  • 충돌이 발생하면 기존 값을 다른 위치로 이동(강제 재배치)하여 빈 공간을 확보.
• 장점:
  • 최악의 경우에도 검색 시간은 O(1).
• 단점:
  • 충돌이 과도하면 테이블 전체를 재구성해야 할 수 있음.

---

해시 테이블의 시간 복잡도

작업평균 시간 복잡도최악 시간 복잡도

검색(Search)	O(1)	O(n) (충돌 심할 경우)
삽입(Insert)	O(1)	O(n) (충돌 심할 경우)
삭제(Delete)	O(1)	O(n) (충돌 심할 경우)

---

해시 테이블 사용 사례

1. 데이터베이스 인덱싱:
   • 키를 기반으로 데이터를 빠르게 검색.
2. 캐싱(Cache):
   • 자주 사용하는 데이터를 키-값 형태로 저장.
3. 집합(Set) 구현:
   • 값의 중복 여부를 빠르게 판단.
4. 맵(Map) 구현:
   • 키-값 쌍으로 데이터를 저장하고 검색.

---

해시 테이블 설계 시 고려 사항

1. 해시 함수 선택:
   • 균등하게 분포된 해시 값을 생성하여 충돌을 최소화.
   • 단순한 모듈로 연산을 피하고 복잡성을 고려.
2. 테이블 크기:
   • 충돌을 줄이기 위해 테이블 크기를 적절히 설정.
   • 일반적으로 소수를 사용하는 것이 좋음.
3. 적재율(Load Factor):
   • 적재율이 높아질수록 충돌 확률 증가.
   • 일반적으로 0.5~0.75를 유지.
4. 재해시(Rehashing):
   • 적재율이 일정 수준을 초과하면 테이블 크기를 늘리고 데이터를 재배치.