[CS] Swift로 HashMap 구현하기

안녕하세요, 루피입니다.

 

오늘은 자료구조 중 HashMap의 내부 동작을 더 깊이 이해하기 위해, Swift로 직접 구현한 과정을 공유하려 합니다. 바로 시작합니다.

---

1. Map과 HashMap이란?

• Map: Key와 Value의 쌍으로 데이터를 저장하는 추상적인 자료구조입니다. 
• HashMap: Map이라는 추상적인 개념을 해시 테이블을 사용해 실제로 구현한 구체적인 자료구조입니다.

---

2. HashMap의 특징

• 빠른 속도: 키를 해시 함수로 변환해 내부 배열(버킷)의 인덱스를 계산하므로, 데이터 검색/삽입/삭제가 평균적으로 O(1)의 시간 복잡도를 가집니다.
• 순서 미보장: 데이터를 저장한 순서와 조회하는 순서가 다를 수 있습니다.
• Key의 유일성: Key의 중복을 허용하지 않습니다. 동일한 Key로 새로운 값을 저장하면 기존 값이 덮어씌워집니다. 반면 Value는 중복될 수 있습니다.
• 성능 의존성: 해시 함수의 품질과 해시 충돌 처리 방식에 따라 실제 성능이 크게 달라질 수 있습니다.

---

3. 버킷과 해시 충돌

• 버킷(Bucket): 해시맵 내부에서 데이터를 실제로 저장하는 배열의 각 칸을 의미합니다. 예를 들어 버킷 사이즈가 16이라면, 0부터 15까지 총 16개의 공간에 데이터를 분산해서 저장합니다.
• 해시 충돌 : 서로 다른 Key가 해시 함수를 통해 계산했을 때, 같은 인덱스(버킷)로 배정되는 현상입니다. 해시맵은 이 충돌을 어떻게 효율적으로 처리하느냐가 성능의 관건입니다. 이번 구현에서는 체이닝(Chaining) 방식을 사용합니다.

---

4. 왜 HashMap을 사용할까?

트리(Tree) 기반의 Map도 있는데 왜 HashMap을 주로 사용할까요?

• 장점 (vs 트리 기반 Map): 트리 기반 Map은 데이터가 정렬된 상태로 저장되며 삽입/검색/삭제가 O(logN)의 시간 복잡도를 가집니다. 반면 HashMap은 순서를 포기한 대신 해시 함수를 통해 인덱스에 직접 접근하므로 평균 O(1)의 압도적인 속도를 보여줍니다. 데이터 양이 많아질수록 이 속도 차이는 더 커집니다.
• 단점: 순서를 보장할 수 없고, 해시 충돌이 발생할 수 있으며, 해시 테이블 유지를 위해 트리 기반 Map보다 일반적으로 메모리를 더 많이 사용합니다.

---

5. Swift로 HashMap 구현하기

이제 직접 코드를 보며 내부 구조를 파악해 보겠습니다.

1) 기본 구조

struct HashMap<Key: Hashable, Value> {
    private var buckets: [[(key: Key, value: Value)]]
    private var itemCount: Int
    private let bucketSize: Int

    public init(bucketSize: Int = 5) {
        self.bucketSize = max(1, bucketSize)
        self.buckets = Array(repeating: [], count: self.bucketSize)
        self.itemCount = 0
    }
}

• struct HashMap<Key: Hashable, Value>: 제네릭을 사용해 어떤 타입의 Key와 Value도 받을 수 있게 합니다. 단, Key는 Hashable 프로토콜을 반드시 채택해야 합니다. 그래야 Swift가 제공하는 .hashValue를 통해 해시값을 쉽게 얻을 수 있습니다.(만약 Hashable을 채택하지 않는다면, 해시 함수를 직접 구현해야합니다)
• buckets: [[(key: Key, value: Value)]]: 데이터를 저장할 버킷 배열입니다. 배열 안의 배열 [[]] 형태인 것이 핵심입니다. 이는 해시 충돌을 해결하기 위한 체이닝(Chaining) 기법으로, 같은 인덱스에 여러 데이터가 충돌하면 그 위치에 배열(리스트)을 만들어 차례로 연결해 저장합니다.
• itemCount: 저장된 총 아이템 수를 추적합니다.
• init(bucketSize:): 지정된 크기만큼의 버킷(빈 배열)들을 생성하여 buckets 배열을 초기화합니다.

2) 인덱스 계산

private func getIndex(forKey key: Key) -> Int { 
	return abs(key.hashValue % bucketSize) 
    }

• key.hashValue: Hashable 프로토콜을 통해 얻은 키의 해시값입니다.
• % bucketSize: 해시값을 버킷의 크기로 나눈 나머지를 구합니다. 이를 통해 해시값이 버킷 크기를 벗어나지 않는 유효한 인덱스로 변환됩니다.
• abs(): hashValue가 음수일 경우를 대비해 절대값을 취해 항상 0 이상의 인덱스를 반환하도록 보장합니다.

3) 주요 기능 (API) 구현

// 값을 저장하거나 덮어쓰기
public mutating func put(_ key: Key, _ value: Value) {
    let idx = getIndex(forKey: key)
    // 1. 해당 버킷에서 이미 키가 존재하는지 확인
    if let i = buckets[idx].firstIndex(where: { $0.key == key }) {
        // 2. 존재하면 값을 덮어쓴다 (Update)
        buckets[idx][i].value = value
    } else {
        // 3. 존재하지 않으면 버킷 리스트에 새로운 (키, 값)을 추가 (Insert)
        buckets[idx].append((key, value))
        itemCount += 1
    }
}

// 값 조회
public func get(_ key: Key) -> Value? {
    let idx = getIndex(forKey: key)
    // 해당 버킷 리스트에서 키가 일치하는 첫 번째 요소의 값을 반환
    return buckets[idx].first(where: { $0.key == key })?.value
}

// 값 삭제
public mutating func remove(_ key: Key) {
    let idx = getIndex(forKey: key)
    // 해당 버킷 리스트에서 키가 일치하는 요소의 인덱스를 찾아
    if let i = buckets[idx].firstIndex(where: { $0.key == key }) {
        // 해당 요소를 삭제
        buckets[idx].remove(at: i)
        itemCount -= 1
    }
}

• put: 키에 해당하는 인덱스를 찾고, 해당 버킷(리스트)에 이미 키가 존재하는지 확인합니다. 존재하면 값을 업데이트하고, 없다면 리스트의 끝에 새로운 데이터를 추가합니다.
• get: 키에 해당하는 인덱스를 찾고, 해당 버킷(리스트)을 순회하며 키가 일치하는 데이터를 찾아 그 값을 반환합니다.
• remove: get과 유사하게 키를 찾아, 해당 데이터를 버킷 리스트에서 제거합니다.

이 외 containsKey, isEmpty, size, keys, clear 등의 보조 기능들도 위 로직들을 응용하여 구현할 수 있습니다.

---

오늘도 화이팅입니다!