# 99클럽 코테 스터디 9일차 TIL - 나만의 작은 서랍장 만들기: 해시맵 (LeetCode 706)

피터·2025년 4월 10일
0

오늘은 706. Design HashMap 문제를 풀었다. 이 문제는 컴퓨터가 기본으로 제공하는 편리한 서랍장(Swift의 Dictionary 같은 것)을 쓰지 않고, 나만의 규칙으로 물건(데이터)을 넣고 빼는 작은 서랍장(해시맵)을 직접 만들어보는 것이 목표였다.

처음엔 '해시맵? 그게 뭐지?' 싶었지만, 직접 만들어보니 어떻게 돌아가는지 조금 알 것 같았다.


🤔 해시맵? 그게 뭐길래 이렇게 어려웠을까?

솔직히, "라이브러리 쓰지 말고 직접 만들어봐!" 라는 말을 들었을 때 머리가 하얘졌다. '해시'라는 단어부터 낯설었기 때문이다.

그래서 단어 뜻부터 찾아보기 시작했다.

  • 해시(Hash): 데이터를 짧고 고유한 '꼬리표' 같은 값으로 바꾸는 기술. (마치 긴 이름을 짧은 별명으로 부르는 것처럼!)
  • Swift의 Hashable: 어떤 데이터든 이 '꼬리표'를 붙일 수 있게 만들어주는 약속.
  • 해시 테이블(Hash Table): 이 '꼬리표'를 이용해서 데이터를 아주 빠르게 찾을 수 있게 만든 특별한 저장 공간(자료구조). (우리가 만들 '작은 서랍장'이 바로 이것!)

개념 설명은 읽었지만, '그래서 이걸 어떻게 만든다는 거지?' 하는 의문은 계속 남았다. 특히 '충돌(Collision)' 이라는 게 발생할 수 있다는 점이 궁금했다. "충돌? 뭐가 부딪힌다는 걸까?"

결국 검색의 힘을 빌렸다. 찾아보니, 해시맵을 만드는 여러 방법이 있었고, 그중 충돌을 해결하는 방법들이 중요했다.

  • Separate Chaining (분리 연결법): 같은 꼬리표(해시 값)를 가진 데이터들을 한 줄로 쭉 엮어두는 방법. (마치 같은 번호표를 받은 사람들을 한 줄로 세우는 것처럼!)
  • Open Addressing (개방 주소법): 꼬리표가 가리킨 칸이 이미 차 있으면, 근처의 다른 빈칸을 찾아 넣는 방법.

이런 구체적인 방법들을 보고 나니, '아, 이런 식으로 만드는 거구나!' 하고 조금씩 감이 오기 시작했다.

그중에서 Separate Chaining 방식이 가장 이해하기 쉬웠다. "같은 번호표(해시 값)를 받은 데이터는 일단 그 번호 칸(버킷)에 모아두고, 거기서 다시 찾으면 되겠네!" 라는 생각이 들었다.


🔍 문제 살펴보기: 어떤 서랍장을 만들어야 할까?

문제에서 요구하는 기능은 간단했다.
1. MyHashMap 이라는 이름의 나만의 서랍장을 만든다.
2. put(열쇠, 물건): 특정 '열쇠' 번호에 '물건'을 넣는다. (만약 같은 열쇠 번호에 이미 물건이 있다면 새 물건으로 바꾼다.)
3. get(열쇠): 특정 '열쇠' 번호에 해당하는 '물건'을 꺼내온다. (물건이 없으면 -1을 알려준다.)
4. remove(열쇠): 특정 '열쇠' 번호의 '물건'을 서랍장에서 뺀다.

특별한 조건:

  • '열쇠'와 '물건' 번호는 0부터 1,000,000까지 쓸 수 있다. (꽤 큰 숫자까지!)
  • put, get, remove 기능은 전부 합쳐서 최대 10,000번 사용된다.

✅ 첫 번째 시도: Separate Chaining 방식으로 서랍장 만들기

가장 먼저 떠올린 방법은 위에서 이해했던 Separate Chaining (분리 연결법) 이었다.

만드는 방법:
1. 먼저, 서랍 칸(buckets) 을 여러 개 준비한다. (예: 1000개 정도) 이 서랍 칸들이 들어있는 전체를 배열로 만들었다.
2. '꼬리표' 만드는 규칙(해시 함수)을 정한다. 여기서는 간단하게 열쇠 번호 % 서랍 칸 개수 로 정했다. 어떤 열쇠든 이걸 계산하면 몇 번 서랍 칸에 넣을지 번호가 나온다.
3. 같은 서랍 칸에 여러 물건이 들어갈 수 있으니, 각 서랍 칸 안에는 (열쇠, 물건) 짝꿍 리스트를 넣어둘 수 있게 만들었다. (Swift에서는 배열 안에 배열을 넣는 방식으로 구현했다: [[(key: Int, value: Int)]])

/// Separate Chaining 방식으로 만든 서랍장
class MyHashMap_Chaining {
    // 서랍 칸 개수를 정한다 (소수를 쓰면 좋다고 해서 10007개로!)
    private let size = 10007 
    // 각 서랍 칸은 (열쇠, 물건) 짝꿍 리스트를 담을 수 있다
    private var buckets: [[(key: Int, value: Int)]]

    // 서랍장 초기화: 모든 칸을 빈 리스트로 채워둔다
    init() {
        buckets = Array(repeating: [], count: size)
    }

    // 꼬리표 만드는 규칙 (해시 함수): 열쇠 번호를 서랍 칸 개수로 나눈 나머지
    private func hash(_ key: Int) -> Int {
        return key % size 
    }

    // 물건 넣기 (put)
    func put(_ key: Int, _ value: Int) {
        // 1. 어떤 서랍 칸에 넣을지 계산한다
        let index = hash(key)
        // 2. 해당 서랍 칸을 확인한다
        for i in 0..<buckets[index].count {
            // 3. 혹시 같은 열쇠 번호가 이미 있는지 찾아본다
            if buckets[index][i].key == key {
                // 4. 있다면 새 물건으로 바꿔치기 하고 끝낸다!
                buckets[index][i].value = value 
                return
            }
        }
        // 5. 같은 열쇠가 없었다면, 서랍 칸 리스트 맨 뒤에 (열쇠, 물건) 짝꿍을 새로 추가한다
        buckets[index].append((key, value))
    }

    // 물건 꺼내기 (get)
    func get(_ key: Int) -> Int {
        // 1. 어떤 서랍 칸을 봐야 할지 계산한다
        let index = hash(key)
        // 2. 해당 서랍 칸의 (열쇠, 물건) 짝꿍 리스트를 하나씩 살펴본다
        for pair in buckets[index] {
            // 3. 내가 찾는 열쇠 번호와 같은 짝꿍을 찾으면
            if pair.key == key {
                // 4. 그 짝꿍의 물건을 꺼내준다!
                return pair.value 
            }
        }
        // 5. 서랍 칸을 다 뒤져도 못 찾았다면, -1을 알려준다 (없다는 뜻)
        return -1 
    }

    // 물건 빼기 (remove)
    func remove(_ key: Int) {
        // 1. 어떤 서랍 칸을 봐야 할지 계산한다
        let index = hash(key)
        // 2. 해당 서랍 칸의 리스트에서, 주어진 열쇠 번호와 같은 짝꿍을 찾아서 없애버린다
        //    (Swift의 removeAll 기능을 사용하면 편리하다)
        buckets[index].removeAll { $0.key == key } 
    }
}

🤔 잠깐만, 열쇠 번호가 100만까지인데 서랍 칸은 1000개? 괜찮을까?

코드를 짜고 보니 궁금한 점이 생겼다. 열쇠 번호는 0부터 1,000,000까지 엄청 많은데, 서랍 칸(buckets)은 고작 1000개 (또는 10007개) 정도밖에 안 만들었다. 이러면 서로 다른 열쇠인데도 같은 서랍 칸 번호(꼬리표)를 받게 되는 경우(충돌) 가 너무 많지 않을까?

맞는 걱정이었다. 서랍 칸이 적으면 여러 열쇠가 한 칸에 몰릴 확률이 높다. 마치 인기 있는 맛집에 사람들이 줄을 길게 서는 것처럼, get, put, remove를 할 때마다 그 칸에 있는 긴 리스트를 처음부터 훑어봐야 해서 시간이 오래 걸릴 수 있다. 운이 나쁘면 모든 열쇠가 한 칸에 다 들어가서, 찾는 데 (O(n)) 시간이 걸릴 수도 있다. (원래 해시맵은 (O(1)) 속도를 기대하는데!)


✅ 두 번째 시도: 그냥 큰 서랍장 하나를 통째로 쓰자! (Direct Addressing)

문제 조건을 다시 자세히 봤다.

  • 열쇠 번호는 0부터 1,000,000 까지다. (딱 정해진 범위!)
  • 음수(-) 번호 열쇠는 없다.
  • 서랍장을 사용하는 횟수는 최대 10,000번이다.

이런 경우에는 아주 간단하고 빠른 방법이 있었다. 바로 Direct Addressing (직접 주소 지정) 방식이다.

핵심 아이디어:

  • "꼬리표 만드는 규칙(해시 함수)" 같은 거 없이, 열쇠 번호 자체를 그냥 서랍 칸 번호로 쓰자!
  • 0번부터 1,000,000번까지, 총 1,000,001개의 서랍 칸을 가진 아주 아주 큰 배열을 하나 만든다.
  • 각 서랍 칸에는 물건 번호를 직접 저장한다. (물건이 없다는 표시는 -1로 하기로 약속!)
/// Direct Addressing 방식으로 만든 서랍장 (엄청 큰 배열 하나!)
class MyHashMap_Direct {
    // 0번부터 1,000,000번까지의 서랍 칸을 가진 배열
    private var map: [Int] 
    // 총 서랍 칸 개수 (최대 열쇠 번호 + 1)
    private let capacity = 1_000_001 

    // 서랍장 초기화: 모든 칸을 -1 (비어있음)로 채운다
    init() {
        map = Array(repeating: -1, count: capacity) 
    }

    // 물건 넣기 (put): 그냥 해당 열쇠 번호 칸에 물건을 넣는다!
    func put(_ key: Int, _ value: Int) {
        // (문제 조건상 열쇠 번호는 항상 0 ~ 1,000,000 이므로 사실 아래 범위 확인은 필요 없다)
        if key >= 0 && key < capacity { 
            map[key] = value 
        }
    }

    // 물건 꺼내기 (get): 그냥 해당 열쇠 번호 칸에 있는 걸 꺼낸다!
    func get(_ key: Int) -> Int {
        if key >= 0 && key < capacity {
            // 물건이 있으면 그 번호가, 없으면 초기값 -1이 나올 것이다.
            return map[key] 
        }
        return -1 // 혹시 이상한 열쇠 번호가 들어오면 -1
    }

    // 물건 빼기 (remove): 그냥 해당 열쇠 번호 칸을 다시 -1 (비어있음)로 만든다!
    func remove(_ key: Int) {
        if key >= 0 && key < capacity {
            map[key] = -1
        }
    }
}

장점:

  • 만들기가 훨씬 쉬웠다!
  • 꼬리표가 겹치는 충돌 걱정이 전혀 없었다.
  • 물건을 넣고 빼고 찾는 모든 작업이 언제나 가장 빠른 속도((O(1))) 로 이루어졌다.

단점:

  • 메모리를 많이 사용한다. 1,000,001개의 정수(Int)를 저장할 공간이 필요하다. (대략 8MB 정도) 처음부터 이만큼 큰 공간을 확보해야 한다.
  • 만약 열쇠 번호 범위가 훨씬 더 크거나 음수 번호를 써야 했다면 이 방법은 쓰기 어려웠을 것이다.

하지만 이번 문제에서는 최대 열쇠 번호가 백만이고, 사용하는 횟수도 적어서 8MB 정도 메모리는 괜찮았다. 그래서 이 Direct Addressing 방식이 오히려 더 좋은 해결책이 될 수 있었다!


💡 잠깐! 처음 방식(Separate Chaining)에서 서랍 칸 개수는 왜 미리 정했을까?

Separate Chaining 방식으로 만들 때, 서랍 칸 개수(size)를 왜 처음부터 딱 정해놓고 시작했는지 궁금할 수 있다.

  1. 꼬리표 계산기(해시 함수)는 전체 칸 수를 알아야 한다: 열쇠 번호 % 서랍 칸 개수 계산을 하려면, 당연히 '서랍 칸 개수'가 얼마인지 정해져 있어야 항상 같은 열쇠에 대해 같은 칸 번호를 알려줄 수 있다. 만약 서랍 칸 개수가 중간에 바뀌면, 같은 열쇠라도 다른 칸 번호를 받게 되어 엉망이 될 수 있다.

  2. 성능 예측과 충돌 관리: 서랍 칸 개수는 서랍장의 성능과 관련이 깊다. 칸이 너무 적으면 한 칸에 물건이 너무 많이 쌓여서 느려지고((O(n)) 처럼), 칸이 너무 많으면 비어있는 칸이 많아서 메모리가 아깝다. 그래서 보통은 사용할 데이터 양을 예상해서 적절한 칸 수를 미리 정한다. (전문가들은 보통 '로드 팩터'라는 것을 0.7 정도로 유지하려고 한다.)

  3. 서랍장 크기 바꾸는 건 귀찮아서: 사실 실제 Dictionary 같은 것들은 데이터가 많아지면 내부적으로 서랍장 크기(배열 크기)를 더 크게 늘리는 '리사이징' 작업을 한다. 그런데 이건 꽤 복잡한 작업이다 (모든 물건을 새 서랍장으로 옮겨 담아야 함!). 이렇게 직접 만들 때는 보통 그런 복잡한 기능 없이, 처음 정한 크기 안에서만 해결하도록 만드는 것이 간단했다.

팁: 서랍 칸 개수를 정할 때 소수(Prime Number) (예: 10007)를 쓰는 경우가 많다. 이유는 좀 어렵지만, 특정 패턴을 가진 열쇠들이 들어왔을 때 한쪽 칸으로만 쏠리는 현상을 줄여주는 효과가 있다고 한다.


✨ 오늘 배운 점 정리

  • 해시맵을 만들 때 '충돌'을 어떻게 해결할지 정하는 것이 중요했다. (Separate Chaining 방식 등)
  • 문제의 '특별한 조건' (열쇠 번호 범위 등)을 잘 활용하면 훨씬 쉽고 빠른 방법(Direct Addressing)을 찾을 수도 있다는 것을 알았다.
  • '꼬리표 만드는 규칙(해시 함수)'과 '서랍 칸 개수(버킷 크기)'가 해시맵 성능에 얼마나 중요한지 느꼈다.
  • 우리가 평소에 편리하게 쓰는 Dictionary 같은 것들이 실제로는 이런 고민들을 통해 만들어졌다는 것을 생각해보는 좋은 기회였다. 직접 만들어보니 그 원리를 조금 더 깊게 이해할 수 있었다!

profile
iOS 개발자입니다.

0개의 댓글