해시 충돌 해결
서로 다른 키가 같은 해시값을 가질 때 이를 처리하는 방법
왜 충돌이 발생하나?
해시 함수: key % 10
"apple" → hash=3
"banana" → hash=7
"cherry" → hash=3 ← 충돌!
무한한 키 → 유한한 버킷
→ 비둘기집 원리로 반드시 충돌
1. 체이닝 (Chaining)
[0] → null
[1] → null
[2] → null
[3] → [apple] → [cherry] → null
[4] → null
...
[7] → [banana] → null
같은 버킷에 연결리스트로 연결
| 장점 | 단점 |
|---|
| 구현 간단 | 포인터 메모리 추가 |
| 삭제 쉬움 | 캐시 지역성 나쁨 |
| 적재율 1 초과 가능 | 최악 O(N) (한 버킷에 몰림) |
2. 개방 주소법 (Open Addressing)
충돌 시 다른 빈 슬롯을 찾음
[선형 탐사] h(k)+1, +2, +3...
[0] null
[1] null
[2] null
[3] apple ← 원래 자리
[4] cherry ← 충돌! 다음 칸으로
[5] null
| 방식 | 탐사 순서 | 특징 |
|---|
| 선형 탐사 | +1, +2, +3 | 클러스터링 |
| 이차 탐사 | +1, +4, +9 | 클러스터링 완화 |
| 이중 해싱 | h2(k) 간격 | 가장 균등 |
체이닝 vs 개방 주소법
| 구분 | 체이닝 | 개방 주소법 |
|---|
| 메모리 | 추가 필요 | 테이블 내부 |
| 적재율 | 1 초과 가능 | 1 미만 유지 |
| 캐시 | 나쁨 | 좋음 |
| 삭제 | 쉬움 | 복잡 (tombstone) |
| 구현 | Java HashMap | Python dict |
적재율과 리해싱
적재율 = 저장된 수 / 버킷 수
적재율 0.75 초과 → 리해싱!
버킷 수 2배로 확장
모든 키 재배치 (O(N))
Java HashMap: 0.75에서 리해싱
Python dict: 약 0.66에서 리해싱
좋은 해시 함수 조건
| 조건 | 설명 |
|---|
| 균등 분포 | 버킷에 골고루 |
| 빠른 계산 | O(1) |
| 결정적 | 같은 입력 → 같은 출력 |
| 눈사태 효과 | 입력 1비트 변경 → 출력 크게 변경 |
Q.해시 충돌이란 무엇이고 왜 발생하나요?
서로 다른 키가 같은 버킷 번호를 받는 것입니다. 버킷 수가 유한하므로 반드시 생깁니다.
해시 값을 버킷 수로 나눈 나머지로 자리를 정한다
hash("apple") % 16 = 3
hash("grape") % 16 = 3 <- 같은 자리
키의 가능한 수는 사실상 무한하고 버킷은 유한하므로 충돌을 없애는 것은 불가능합니다. 좋은 해시 함수의 목표는 충돌을 없애는 것이 아니라 고르게 흩어 한 자리에 몰리지 않게 하는 것입니다.
생일 문제로 보면 충돌은 생각보다 빨리 옵니다. 버킷이 365개면 23개만 넣어도 충돌 확률이 50%를 넘습니다.
흔한 실수: 해시 함수를 바꾸면 충돌이 사라진다고 답하는 것. 분포는 좋아지지만 존재 자체는 없앨 수 없어서, 자료구조는 충돌을 처리하는 방법을 반드시 갖고 있어야 합니다.
Q.체이닝과 개방 주소법의 차이를 설명해주세요.
충돌한 항목을 어디에 두는지가 다릅니다.
| 항목 | 체이닝 | 개방 주소법 |
|---|
| 저장 위치 | 버킷에 연결 구조로 매단다 | 빈 다른 자리를 찾아 넣는다 |
| 적재율 | 1을 넘어도 동작한다 | 1을 넘을 수 없다 |
| 삭제 | 항목을 떼어내면 끝 | 삭제 표식을 남겨야 한다 |
| 캐시 지역성 | 노드가 흩어져 나쁘다 | 연속 배열이라 좋다 |
| 메모리 | 포인터가 추가로 든다 | 추가 포인터가 없다 |
삭제가 잦으면 체이닝이 유리합니다. 개방 주소법은 지운 자리에 표식을 남겨야 하고(그냥 비우면 탐사가 중간에 끊긴다), 그 표식이 쌓이면 탐사 거리가 길어져 성능이 떨어집니다.
흔한 실수: 개방 주소법이 항상 빠르다고 답하는 것. 적재율이 0.7을 넘으면 탐사가 급격히 길어집니다. 체이닝은 완만하게 나빠집니다.
Q.적재율(Load Factor)과 리해싱의 관계는?
적재율은 항목 수를 버킷 수로 나눈 값입니다. 이 값이 임계치를 넘으면 버킷을 늘리고 전부 다시 배치합니다.
적재율은 항목 수를 버킷 수로 나눈 값입니다.
| 상태 | 값 |
|---|
| 버킷 16, 항목 12 | 적재율 0.75 |
| 임계치 0.75 에 닿으면 | 버킷을 32로 늘린다 |
| 그 다음 | 모든 키를 새 버킷 수로 다시 계산해 옮긴다. 이것이 리해싱이고 O(n) |
리해싱이 필요한 이유는 자리 계산에 버킷 수가 들어가기 때문입니다. 버킷이 바뀌면 모든 키의 자리가 바뀝니다.
적재율을 낮게 두면 충돌이 줄지만 메모리가 낭비되고, 높게 두면 반대입니다. 0.75가 흔한 절충값입니다.
흔한 실수: 리해싱 때문에 삽입이 O(n)이라고 답하는 것. 드물게 일어나고 버킷이 배수로 늘어나므로 분할상환하면 O(1)입니다. 크기를 미리 알면 처음부터 지정해 리해싱을 없애는 것이 좋습니다.
Q.Java HashMap의 내부 구현을 설명해주세요
버킷 배열과 체이닝을 쓰고, 한 버킷이 길어지면 트리로 바꿉니다.
| 항목 | 내용 |
|---|
| 기본 용량 | 16. 항상 2의 거듭제곱으로 유지한다 |
| 자리 계산 | 해시의 상위 비트를 하위와 섞은 뒤 (용량 - 1)과 비트 연산 |
| 적재율 임계치 | 0.75. 넘으면 용량을 2배로 늘리고 재배치 |
| 충돌 처리 | 같은 버킷에 연결 리스트로 잇는다 |
| 트리 전환 | 한 버킷이 8개를 넘고 전체 용량이 64 이상이면 레드블랙 트리로 |
트리 전환이 있는 이유는 해시 충돌 공격 때문입니다. 공격자가 같은 버킷으로 몰리는 키를 대량으로 보내면 조회가 O(n)으로 떨어집니다. 트리로 바꾸면 최악이 O(log n)으로 묶입니다.
용량을 2의 거듭제곱으로 두는 이유는 나머지 연산을 비트 연산으로 대체할 수 있어서입니다.
흔한 실수: 생성자에 넣은 값이 그대로 용량이 된다고 답하는 것. 2의 거듭제곱으로 올림되므로 1000을 넣으면 1024가 됩니다.
Q.해시맵의 시간복잡도가 O(1)이 아닌 경우는?
평균이 O(1)이고, 한 버킷에 몰리면 O(n)까지 떨어집니다.
| 상황 | 복잡도 | 원인 |
|---|
| 정상 분포 | O(1) | 버킷당 항목이 상수 개 |
| 해시 함수가 나쁨 | O(n) | 특정 버킷에 몰린다 |
| 충돌 공격 | O(n) | 같은 버킷을 노린 키를 대량 삽입 |
| 트리 전환 후 | O(log n) | Java 등이 최악을 이렇게 묶는다 |
| 리사이징 순간 | O(n) | 전체 재배치. 분할상환하면 O(1) |
키의 hashCode 를 잘못 구현한 경우도 흔합니다. 항상 같은 값을 반환하면 모든 키가 한 버킷으로 갑니다.
흔한 실수: O(1)을 "항상 한 번에 찾는다"로 이해하는 것. 해시 계산과 버킷 접근, 그 안에서의 비교까지 포함해 입력 크기와 무관한 상수 시간이라는 뜻입니다. 분포가 무너지면 그 전제가 깨집니다.
먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.
읽었으면 문제로 확인해보세요
자료구조 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.