자료구조 해시테이블 충돌 처리

해시 테이블(Hash Table)은 평균 O(1)의 탐색 속도를 보장하지만, 서로 다른 키가 동일한 해시 값을 가질 때 발생하는 ‘충돌(Collision)’을 해결하는 전략이 필수적이다.

체이닝 (Chaining)

각 버킷(Bucket)을 연결 리스트(Linked List)로 구성하여 충돌이 발생하면 리스트 뒤에 데이터를 추가하는 방식이다.

import java.util.LinkedList;

class HashTable {
    private class Node {
        String key;
        String value;
        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    private LinkedList<Node>[] table;
    private int size;

    public HashTable(int size) {
        this.size = size;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int hash(String key) {
        return Math.abs(key.hashCode() % size);
    }

    public void put(String key, String value) {
        int idx = hash(key);
        for (Node node : table[idx]) {
            if (node.key.equals(key)) {
                node.value = value; // 값 갱신
                return;
            }
        }
        table[idx].add(new Node(key, value)); // 충돌 시 리스트에 추가
    }

    public String get(String key) {
        int idx = hash(key);
        for (Node node : table[idx]) {
            if (node.key.equals(key)) return node.value;
        }
        return null;
    }
}

개방 주소법 (Open Addressing)

충돌 발생 시 빈 버킷을 찾아 데이터를 저장하는 방식이다.

• 선형 조사 (Linear Probing): 충돌 지점부터 다음 칸을 순차적으로 탐색한다.
  (index + 1, index + 2 …)
• 이차 조사 (Quadratic Probing): 제곱수 간격으로 탐색하여 데이터 밀집 현상을 완화한다.
  (index + 1^2, index + 2^2 …)
• 이중 해싱 (Double Hashing): 2차 해시 함수를 사용하여 탐색 간격을 결정함으로써 군집화를 방지한다.

비교 및 요약

• 체이닝은 테이블이 꽉 차지 않아도 리스트를 통해 데이터를 무한히 수용할 수 있지만, 리스트가 길어지면 성능이 O(N)으로 저하될 수 있다.
• 개방 주소법은 추가 메모리 공간을 사용하지 않지만, 데이터가 밀집되는 클러스터링(Clustering) 현상이 발생하기 쉽다.

해시 테이블의 효율성은 우수한 해시 함수 설계와 부하율(Load Factor) 관리에 달려 있다.

데이터가 일정 수준 이상 차오르면 테이블 크기를 늘리는 리해싱(Rehashing) 과정을 통해 성능을 유지하는 것 같다.

웨이호프