해시 함수는 고정된 길이의 입력에 대해 해시 값을 반환하는 함수입니다. 그러나 서로 다른 입력에 대해 동일한 해시 값을 반환하는 현상, 즉 해시 충돌이 발생할 수 있습니다. 이는 해시 테이블과 같은 자료 구조에서 검색 속도를 떨어뜨릴 수 있으며 보안상의 문제를 야기할 수 있습니다.

해시 충돌의 원인

해시 충돌은 크게 두 가지 원인으로 발생합니다. 첫 번째는 해시 함수의 출력 범위가 제한되어 있어 서로 다른 입력에 대해 동일한 출력을 내는 경우이고, 두 번째는 서로 다른 입력이라도 해시 함수의 결과가 같은 값으로 매핑되는 경우입니다.

충돌 해결 방법

해시 충돌을 해결하기 위한 여러 가지 방법이 존재합니다.

1. 개별 체이닝 (Separate Chaining)

개별 체이닝은 각 버킷을 연결 리스트로 구현하는 방식으로, 동일한 해시 값을 갖는 항목들을 하나의 버킷에 모아두는 방법입니다. 이 방법은 간단하고 유연하며, 해시 테이블의 크기를 늘리지 않고도 충돌을 해결할 수 있습니다.

class Node {
    String key;
    String value;
    Node next;
}

class HashTable {
    private Node[] array;
    // ...
}

2. 개방 주소법 (Open Addressing)

개방 주소법은 충돌이 발생했을 때 다른 빈 버킷을 찾아 삽입하는 방식으로, 선형 탐사나 이차원 탐사 등의 방법을 사용하여 빈 공간을 찾습니다.

class HashTable {
    private String[] array;
    // ...
    private int linearProbing(int key) {
        int index = hash(key);
        while (array[index] != null) {
            index = (index + 1) % array.length;
        }
        return index;
    }
}

3. 이중 해싱 (Double Hashing)

이중 해싱은 해시 함수가 반환하는 충돌 지점을 계산하는 데 또 다른 해시 함수를 사용하는 방식입니다. 이는 개방 주소법과 유사하지만, 더 효율적으로 충돌을 해결할 수 있습니다.

class HashTable {
    private String[] array;
    // ...
    private int doubleHashing(int key, int attempt) {
        int hash1 = hash(key);
        int hash2 = primeNumber - (key % primeNumber); // primeNumber는 주어진 테이블 크기보다 작은 소수
        return (hash1 + attempt * hash2) % array.length;
    }
}

결론

해시 함수의 충돌은 해시 테이블 등에서 성능과 안정성에 영향을 미치는 중요한 문제입니다. 여러 가지 충돌 해결 기법 중에서는 사용 환경과 데이터에 따라 적절한 방법을 선택해야 합니다.