🔑 해시 충돌(Hash Collision)과 해결 방법

오늘의 이야기

해시 자료 구조(Hash Data Structure)를 사용할 때 피할 수 없는 문제 중 하나가 해시 충돌(Hash Collision)입니다. 팀원들과 오전에 같이 커피 마시면서 해시 충돌 관련해서 이야기 했는데 내가 정말 아는걸까..? 하는 마음이 들어 이번 기회에 해시 충돌의 개념과 이를 해결하는 다양한 기법들을 정리해보겠습니다.

---

해시 충돌이란? 🤔

해시 충돌은 서로 다른 키가 동일한 해시 값을 갖는 현상을 의미합니다. 해시 함수는 무한한 입력 공간을 유한한 출력 공간(해시 테이블의 크기)으로 매핑하기 때문에, 충돌은 불가피합니다.

해시 충돌 예시

1. 해시 함수 h(x) = x % 5 를 사용한다고 가정할 때:
   • h(10) = 10 % 5 = 0
   • h(15) = 15 % 5 = 0
   • h(20) = 20 % 5 = 0
2. 서로 다른 값(10, 15, 20)이 같은 해시 값(0)을 가지므로 해시 충돌이 발생합니다.

해시 충돌을 해결하지 않으면, 해시 테이블에서 데이터를 올바르게 저장하거나 검색하는 데 문제가 발생할 수 있습니다.

---

해시 충돌 해결 방법 🛠️

해시 충돌을 해결하기 위해 일반적으로 개방 주소법(Open Addressing)과 분리 연결법(Separate Chaining)을 사용합니다.

1. 개방 주소법(Open Addressing) 🔄

개방 주소법은 충돌이 발생했을 때, 동일한 해시 테이블 내에서 다른 빈 버킷을 찾아 저장하는 방법입니다. 이 방식에는 다음과 같은 기법들이 있습니다:

📌 선형 탐사법(Linear Probing)

충돌이 발생하면 한 칸씩 이동하며 빈 공간을 찾는 방법입니다.

예제 코드 (Java):

public class LinearProbingHashTable {
    private static final int SIZE = 10;
    private Integer[] table = new Integer[SIZE];

    public void insert(int key) {
        int index = key % SIZE;
        while (table[index] != null) {
            index = (index + 1) % SIZE; // 다음 인덱스로 이동
        }
        table[index] = key;
    }
}

✔️ 장점: 구현이 간단하고 메모리 효율적
⚠️ 단점: 클러스터링(Clustering) 문제가 발생하여 연속된 빈 공간이 줄어들 수 있음

📌 제곱 탐사법(Quadratic Probing)

충돌이 발생하면 이동 거리를 제곱수로 증가시키며 빈 공간을 찾는 방법입니다.

탐사 방식 예시:

• 첫 번째 충돌: index + 1^2
• 두 번째 충돌: index + 2^2
• 세 번째 충돌: index + 3^2

✔️ 장점: 클러스터링 문제를 완화할 수 있음
⚠️ 단점: 테이블 크기가 소수(prime number)가 아니면 충돌이 해결되지 않을 수도 있음

📌 이중 해싱(Double Hashing)

충돌이 발생하면 보조 해시 함수(Secondary Hash Function)를 사용하여 새로운 해시 값을 계산해 빈 공간을 찾습니다.

해시 함수 예시:

int h1(int key) { return key % SIZE; }
int h2(int key) { return 7 - (key % 7); }

• 새로운 인덱스 = (h1(key) + i * h2(key)) % SIZE

✔️ 장점: 클러스터링 문제를 완전히 해결 가능
⚠️ 단점: 연산량이 많아질 수 있음

---

2. 분리 연결법(Separate Chaining) 🌐

분리 연결법은 각 버킷을 연결 리스트(Linked List)로 관리하여, 충돌이 발생하면 해당 버킷의 리스트에 새로운 요소를 추가하는 방식입니다.

예제 코드 (Java):

import java.util.LinkedList;

public class SeparateChainingHashTable {
    private static final int SIZE = 10;
    private LinkedList<Integer>[] table = new LinkedList[SIZE];

    public SeparateChainingHashTable() {
        for (int i = 0; i < SIZE; i++) {
            table[i] = new LinkedList<>();
        }
    }

    public void insert(int key) {
        int index = key % SIZE;
        table[index].add(key);
    }
}

✔️ 장점: 해시 테이블의 크기에 제한을 받지 않으며, 충돌 발생 시 탐색 시간이 일정
⚠️ 단점: 각 버킷이 리스트를 유지해야 하므로 메모리 사용량이 증가

---

✅ 개방 주소법 vs. 분리 연결법 비교

해결 방법	장점	단점
선형 탐사법	구현이 간단, 메모리 효율적	클러스터링 문제 발생 가능
제곱 탐사법	클러스터링 문제 완화 가능	테이블 크기 제약 존재
이중 해싱	클러스터링 문제 해결	연산량 증가 가능
분리 연결법	유연한 충돌 해결	메모리 사용량 증가

---

🚀 어떤 방법을 선택해야 할까?

• 해시 테이블이 크지 않고, 연산 속도가 중요하다면? → 개방 주소법 (특히 이중 해싱) 추천
• 충돌이 많이 발생할 가능성이 크고, 동적 확장이 필요하다면? → 분리 연결법 추천

---

마치며 🌟

해시 충돌은 해시 기반 데이터 구조를 사용할 때 피할 수 없는 문제지만, 적절한 충돌 해결 전략을 사용하면 성능을 최적화할 수 있습니다. 상황에 따라 개방 주소법(선형 탐사, 제곱 탐사, 이중 해싱) 또는 분리 연결법을 선택하여 적절히 활용해보세요! 🚀

---