해싱을 사용할 때 충돌이 발생하는 경우 다양한 방법으로 이를 해결할 수 있습니다. 아래는 대표적인 해시 충돌 해결 방법들입니다.
1. 선형 조사법 (Linear Probing)
설명: 선형 조사법은 충돌이 발생하면 다음 인덱스를 순차적으로 탐색하여 빈 공간을 찾는 기본적인 충돌 해결 방식입니다. 구현이 간단하고 직관적이지만, 데이터가 연속해서 저장되는 현상인 클러스터링(Clustering) 문제를 일으킬 수 있습니다. 클러스터링이 발생하면 추가 충돌이 빈번해지고 탐색 성능이 저하될 수 있습니다.
- 예시: 만약 해시 값이 3인 데이터가 이미 있다면, 인덱스를
(index = 3 + 1, 3 + 2, ...)순서로 증가시키며 빈 공간을 찾습니다. - 해결하려는 문제: 해시 충돌 해결.
- 한계: 연속된 인덱스에 데이터가 쌓여 클러스터링이 발생하며 성능이 저하될 수 있습니다.
2. 이차 조사법 (Quadratic Probing)
설명: 이차 조사법은 선형 조사법에서 발생하는 클러스터링 문제를 줄이기 위해 고안되었습니다. 충돌 시 이동하는 인덱스를 제곱수로 증가시켜 데이터를 분산시킵니다. 첫 번째 충돌에서는 1^2, 두 번째 충돌에서는 2^2만큼 인덱스를 이동합니다. 이러한 방식으로 연속된 데이터 집중을 방지합니다.
- 예시: 해시 값이 3일 경우, 첫 충돌 시
index = 3 + 1^2 = 4, 두 번째 충돌 시index = 3 + 2^2 = 7등으로 이동합니다. - 해결하려는 문제: 선형 조사법의 클러스터링 문제.
- 한계: 해시 테이블 크기가 작을 경우 이동 범위가 제한되며, 여전히 클러스터링이 발생할 수 있습니다.
3. 이중 해싱법 (Double Hashing)
설명: 이차 조사법 역시 고정된 이동 패턴을 사용하므로 클러스터링을 완벽히 해결하지 못합니다. 이를 보완하기 위해 이중 해싱법이 사용됩니다. 두 개의 해시 함수를 적용하여 충돌 시 각기 다른 이동 패턴을 부여하므로 탐색 경로가 다양해지고 클러스터링 현상이 줄어듭니다.
- 예시:
hash1(key) = key % table_size와hash2(key) = prime - (key % prime)을 사용하여(hash1(key) + i * hash2(key)) % table_size로 이동합니다. - 해결하려는 문제: 클러스터링 및 고정된 탐색 패턴으로 인한 성능 저하 문제.
- 한계: 두 개의 해시 함수가 필요하므로 연산이 추가되며, 선택한 해시 함수에 따라 성능 차이가 날 수 있습니다.
4. 체인법 (Chaining)
설명: 체인법은 각 인덱스에 연결 리스트(Linked List)를 사용하여 여러 데이터를 저장하는 방식으로 충돌을 해결합니다. 충돌이 발생할 경우, 해당 인덱스에 연결 리스트로 데이터를 추가하여 관리합니다. 이렇게 하면 빈 공간을 따로 탐색할 필요가 없으며, 해시 테이블의 크기보다 더 많은 데이터를 저장할 수 있어 오버플로우 문제도 줄일 수 있습니다.
- 예시: 해시 값이 5인 데이터가 여러 개라면
list[5]에 연결 리스트 형태로 데이터를 추가하여 저장합니다. - 해결하려는 문제: 불필요한 충돌 계산 및 오버플로우 문제.
- 한계: 연결 리스트를 탐색해야 하므로 데이터가 많아질수록 탐색 성능이 저하될 수 있습니다.
이와 같은 다양한 충돌 해결 방법들이 해시 테이블의 효율적인 사용을 위해 활용됩니다. 각 방법은 특정 상황에 따라 장단점이 있으며, 목적과 데이터 특성에 맞게 선택하여 사용하는 것이 중요합니다.
