오늘은 706. Design HashMap 문제를 풀었다. 이 문제는 컴퓨터가 기본으로 제공하는 편리한 서랍장(Swift의 Dictionary
같은 것)을 쓰지 않고, 나만의 규칙으로 물건(데이터)을 넣고 빼는 작은 서랍장(해시맵)을 직접 만들어보는 것이 목표였다.
처음엔 '해시맵? 그게 뭐지?' 싶었지만, 직접 만들어보니 어떻게 돌아가는지 조금 알 것 같았다.
솔직히, "라이브러리 쓰지 말고 직접 만들어봐!" 라는 말을 들었을 때 머리가 하얘졌다. '해시'라는 단어부터 낯설었기 때문이다.
그래서 단어 뜻부터 찾아보기 시작했다.
Hashable
: 어떤 데이터든 이 '꼬리표'를 붙일 수 있게 만들어주는 약속.개념 설명은 읽었지만, '그래서 이걸 어떻게 만든다는 거지?' 하는 의문은 계속 남았다. 특히 '충돌(Collision)' 이라는 게 발생할 수 있다는 점이 궁금했다. "충돌? 뭐가 부딪힌다는 걸까?"
결국 검색의 힘을 빌렸다. 찾아보니, 해시맵을 만드는 여러 방법이 있었고, 그중 충돌을 해결하는 방법들이 중요했다.
이런 구체적인 방법들을 보고 나니, '아, 이런 식으로 만드는 거구나!' 하고 조금씩 감이 오기 시작했다.
그중에서 Separate Chaining 방식이 가장 이해하기 쉬웠다. "같은 번호표(해시 값)를 받은 데이터는 일단 그 번호 칸(버킷)에 모아두고, 거기서 다시 찾으면 되겠네!" 라는 생각이 들었다.
문제에서 요구하는 기능은 간단했다.
1. MyHashMap
이라는 이름의 나만의 서랍장을 만든다.
2. put(열쇠, 물건)
: 특정 '열쇠' 번호에 '물건'을 넣는다. (만약 같은 열쇠 번호에 이미 물건이 있다면 새 물건으로 바꾼다.)
3. get(열쇠)
: 특정 '열쇠' 번호에 해당하는 '물건'을 꺼내온다. (물건이 없으면 -1을 알려준다.)
4. remove(열쇠)
: 특정 '열쇠' 번호의 '물건'을 서랍장에서 뺀다.
특별한 조건:
put
, get
, remove
기능은 전부 합쳐서 최대 10,000번 사용된다.가장 먼저 떠올린 방법은 위에서 이해했던 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 }
}
}
코드를 짜고 보니 궁금한 점이 생겼다. 열쇠 번호는 0부터 1,000,000까지 엄청 많은데, 서랍 칸(buckets
)은 고작 1000개 (또는 10007개) 정도밖에 안 만들었다. 이러면 서로 다른 열쇠인데도 같은 서랍 칸 번호(꼬리표)를 받게 되는 경우(충돌) 가 너무 많지 않을까?
맞는 걱정이었다. 서랍 칸이 적으면 여러 열쇠가 한 칸에 몰릴 확률이 높다. 마치 인기 있는 맛집에 사람들이 줄을 길게 서는 것처럼, get
, put
, remove
를 할 때마다 그 칸에 있는 긴 리스트를 처음부터 훑어봐야 해서 시간이 오래 걸릴 수 있다. 운이 나쁘면 모든 열쇠가 한 칸에 다 들어가서, 찾는 데 (O(n)) 시간이 걸릴 수도 있다. (원래 해시맵은 (O(1)) 속도를 기대하는데!)
문제 조건을 다시 자세히 봤다.
이런 경우에는 아주 간단하고 빠른 방법이 있었다. 바로 Direct Addressing (직접 주소 지정) 방식이다.
핵심 아이디어:
/// 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
}
}
}
장점:
단점:
하지만 이번 문제에서는 최대 열쇠 번호가 백만이고, 사용하는 횟수도 적어서 8MB 정도 메모리는 괜찮았다. 그래서 이 Direct Addressing 방식이 오히려 더 좋은 해결책이 될 수 있었다!
Separate Chaining 방식으로 만들 때, 서랍 칸 개수(size
)를 왜 처음부터 딱 정해놓고 시작했는지 궁금할 수 있다.
꼬리표 계산기(해시 함수)는 전체 칸 수를 알아야 한다: 열쇠 번호 % 서랍 칸 개수
계산을 하려면, 당연히 '서랍 칸 개수'가 얼마인지 정해져 있어야 항상 같은 열쇠에 대해 같은 칸 번호를 알려줄 수 있다. 만약 서랍 칸 개수가 중간에 바뀌면, 같은 열쇠라도 다른 칸 번호를 받게 되어 엉망이 될 수 있다.
성능 예측과 충돌 관리: 서랍 칸 개수는 서랍장의 성능과 관련이 깊다. 칸이 너무 적으면 한 칸에 물건이 너무 많이 쌓여서 느려지고((O(n)) 처럼), 칸이 너무 많으면 비어있는 칸이 많아서 메모리가 아깝다. 그래서 보통은 사용할 데이터 양을 예상해서 적절한 칸 수를 미리 정한다. (전문가들은 보통 '로드 팩터'라는 것을 0.7 정도로 유지하려고 한다.)
서랍장 크기 바꾸는 건 귀찮아서: 사실 실제 Dictionary
같은 것들은 데이터가 많아지면 내부적으로 서랍장 크기(배열 크기)를 더 크게 늘리는 '리사이징' 작업을 한다. 그런데 이건 꽤 복잡한 작업이다 (모든 물건을 새 서랍장으로 옮겨 담아야 함!). 이렇게 직접 만들 때는 보통 그런 복잡한 기능 없이, 처음 정한 크기 안에서만 해결하도록 만드는 것이 간단했다.
팁: 서랍 칸 개수를 정할 때 소수(Prime Number) (예: 10007)를 쓰는 경우가 많다. 이유는 좀 어렵지만, 특정 패턴을 가진 열쇠들이 들어왔을 때 한쪽 칸으로만 쏠리는 현상을 줄여주는 효과가 있다고 한다.
Dictionary
같은 것들이 실제로는 이런 고민들을 통해 만들어졌다는 것을 생각해보는 좋은 기회였다. 직접 만들어보니 그 원리를 조금 더 깊게 이해할 수 있었다!