고급 해싱과 충돌 해결: Open Addressing과 Separate Chaining

해싱(Hashing)은 데이터를 효율적으로 저장하고 검색하기 위해 필수적인 기법 중 하나입니다. 해시 테이블은 데이터를 키-값(Key-Value) 형태로 저장하며, 빠른 데이터 접근 속도를 자랑합니다. 하지만 해시 테이블에서는 해시 충돌(Hash Collision)이 발생할 수 있으며, 이를 해결하는 다양한 방법이 존재합니다. 이번 글에서는 Open Addressing과 Separate Chaining이라는 충돌 해결 기법에 대해 심도 있게 다룹니다.

해싱의 기본 개념

해시 함수(Hash Function):

• 데이터를 고정된 크기의 해시값으로 변환하는 함수.
• 예: 문자열 "hello"를 정수 12345로 변환.

해시 테이블(Hash Table):

• 배열 형태의 데이터 구조로, 해시값을 인덱스로 활용.
• 데이터 저장 및 검색 시 평균 시간 복잡도는 O(1).

해시 충돌이란?

• 해시 함수가 서로 다른 키에 대해 동일한 해시값을 생성할 때 발생합니다.
• 예: "key1"과 "key2"의 해시값이 동일하다면, 동일한 위치를 공유하려고 하면서 충돌이 발생.

충돌 해결 방법

1. Open Addressing (개방 주소법)

Open Addressing은 충돌이 발생할 경우, 해시 테이블 내 다른 빈 공간을 찾아 데이터를 저장하는 방식입니다.

Open Addressing의 주요 방식

• Linear Probing (선형 조사): 충돌 발생 시 한 칸씩 순차적으로 이동하여 빈 공간 탐색.
• 장점: 구현이 간단.
• 단점: 클러스터링 문제 발생(연속된 빈 공간 부족).

def linear_probing_insert(hash_table, key, value):
    index = hash(key) % len(hash_table)
    while hash_table[index] is not None:
        index = (index + 1) % len(hash_table)
    hash_table[index] = (key, value)

• Quadratic Probing (이차 조사): 이동 거리가 1, 4, 9, … 순으로 증가.
• 장점: 클러스터링 문제 완화.
• 단점: 빈 공간이 없을 때 탐색 실패 가능성 증가.

• Double Hashing (이중 해싱): 두 개의 해시 함수를 사용해 이동 거리 결정.
• 장점: 충돌 분산 효과가 뛰어남.
• 단점: 구현 복잡도 증가.

Open Addressing의 특징

• 충돌 시 테이블 내에서 해결.
• 데이터 크기가 커질수록 성능 저하.
• 테이블의 부하율(Load Factor)이 낮을수록 효과적.

2. Separate Chaining (분리 연결법)

Separate Chaining은 해시 테이블의 각 슬롯을 리스트 또는 연결 리스트로 관리하여 충돌을 해결합니다.

Separate Chaining의 작동 원리

• 해시값이 동일한 데이터를 연결 리스트에 저장.
• 검색 시 해당 슬롯의 리스트를 순회하여 키를 찾음.

Separate Chaining의 구현

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def insert(self, key, value):
        index = hash(key) % self.size
        self.table[index].append((key, value))

    def get(self, key):
        index = hash(key) % self.size
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# 예제 사용
hash_table = HashTable(10)
hash_table.insert("apple", 100)
hash_table.insert("banana", 200)
print(hash_table.get("apple"))  # 100 출력

Separate Chaining의 특징

• 충돌 시 테이블 밖에서 해결.
• 테이블이 꽉 차더라도 데이터 저장 가능.
• 부하율 증가에 따른 성능 저하가 상대적으로 적음.

Open Addressing vs Separate Chaining

특성	Open Addressing	Separate Chaining
충돌 처리 위치	테이블 내부	테이블 외부 (리스트 활용)
메모리 사용량	고정된 테이블 크기	추가 메모리 사용
부하율 증가 시 성능	성능 급격히 저하	성능 저하가 완만
구현 난이도	상대적으로 간단	복잡한 구조 관리 필요
데이터 저장 용량	테이블 크기 제한 있음	이론적으로 무제한 저장 가능

실무 활용

• Open Addressing: 메모리가 제한적인 경우 사용. 정적인 데이터 저장에서 유리.
• Separate Chaining: 동적인 데이터 크기를 처리해야 하는 경우 사용. 부하율이 높은 환경에서 더 적합.

충돌 해결 방법 선택 가이드

• 테이블 크기: 고정된 크기라면 Open Addressing, 유연성이 필요하다면 Separate Chaining.
• 부하율 관리: 부하율이 높다면 Separate Chaining이 더 효율적.
• 메모리 사용 제한: 메모리가 제한적이면 Open Addressing.
• 복잡도: Open Addressing은 간단한 구현이 필요할 때 유리.

결론

해시 충돌은 해시 테이블 사용에서 불가피하게 발생하는 문제이며, 이를 해결하기 위해 Open Addressing과 Separate Chaining이 활용됩니다. Open Addressing은 메모리 사용량이 적은 대신 부하율 관리가 중요하며, Separate Chaining은 유연성과 성능 유지가 강점입니다.