[자료구조] 해시 테이블(Hash Table) 개념과 충돌 해결 기법(체이닝, 개방 주소법) 완전 정리

컴퓨터공학과 자료구조/알고리즘 중간·기말고사나 개발자 기술 면접에서 "탐색 속도가 가장 빠른 자료구조"를 물어볼 때 무조건 등장하는 주제가 있습니다. 바로 해시 테이블(Hash Table)입니다.

"어떻게 $O(1)$의 속도로 데이터를 빠르게 찾을 수 있을까?"

"서로 다른 키(Key)가 같은 주소로 매핑되는 '해시 충돌'이 발생하면 어떻게 해결해야 할까?"

해시 테이블의 작동 원리부터 해시 함수, 그리고 시험 단골 계산/서술형 문제로 출제되는 체이닝(Chaining)과 개방 주소법(Open Addressing)의 주요 기법들까지 완벽하게 정리해 드립니다!

1. 해시 테이블(Hash Table)이란?

해시 테이블은 Key(키)와 Value(값)를 쌍으로 저장하여, Key를 통해 데이터를 빠르게 검색, 삽입, 삭제할 수 있는 자료구조입니다.

• 평균 시간 복잡도: $O(1)$
• 핵심 원리: Key 값을 해시 함수(Hash Function)에 대입하여 나온 해시 코드(Hash Code) / 인덱스(Index)에 직접 접근하여 데이터를 바로 찾습니다.

2. 해시 충돌(Hash Collision)과 해결 기법

해시 함수가 서로 다른 두 개 이상의 Key에 대해 동일한 인덱스를 반환하는 현상을 해시 충돌(Hash Collision)이라고 합니다. 비둘기집의 원리에 의해 해시 테이블에서는 충돌이 불가피하게 발생하며, 이를 해결하는 방법이 시험의 핵심 포인트입니다.

해시 충돌 해결 기법의 두 가지 핵심 축 (체이닝 vs 개방 주소법). 출처: Gate Vidyalay

1️⃣ 체이닝 (Separate Chaining - 분리 체이닝)

• 개념: 충돌이 발생하면 연결 리스트(Linked List)를 활용하여 충돌된 데이터들을 슬롯 뒤에 계속 연결하는 방식입니다.
• 특징:
  • 해시 테이블의 크기 제약을 받지 않고 추가적인 메모리를 사용하여 계속 데이터를 저장할 수 있습니다.
  • 한 슬롯에 데이터가 과도하게 몰리면 해당 슬롯 탐색 시간이 $O(N)$까지 증가할 수 있습니다. (Java 8 이상에서는 요소가 많아지면 연결 리스트 대신 Red-Black Tree를 사용하여 $O(\log N)$으로 개선)

2️⃣ 개방 주소법 (Open Addressing)

• 개념: 충돌이 발생하면 연결 리스트를 쓰지 않고, 해시 테이블 내부의 다른 비어있는(Empty) 슬롯을 찾아 데이터를 저장하는 방식입니다.
• 주요 탐색 기법 (Probing):
  1. 선형 조사법 (Linear Probing): 충돌 발생 시 고정된 폭(예: +1, +2, +3...)만큼 순차적으로 뒤쪽 슬롯을 탐색합니다.
     • 단점: 특정 영역에 데이터가 밀집되는 Primary Clustering(1차 군집화) 현상 발생.
  2. 이차 조사법 (Quadratic Probing): 충돌 발생 시 보폭을 2차 함수 형태($1^2, 2^2, 3^2...$)로 넓혀가며 탐색합니다.
     • 단점: 동일한 해시 값을 갖는 데이터끼리 모이는 Secondary Clustering(2차 군집화) 현상 발생.
  3. 이중 해싱 (Double Hashing): 충돌 시 이동할 보폭을 구하기 위해 2번째 해시 함수를 별도로 사용하는 방식입니다. 군집화 현상을 가장 효과적으로 방지합니다.

3. 한눈에 비교하는 체이닝 vs 개방 주소법 (★시험 요약표)

구분	분리 체이닝 (Separate Chaining)	개방 주소법 (Open Addressing)
메모리 구조	외부 메모리 사용 (연결 리스트)	해시 테이블 내부 버킷만 사용
테이블 확장	크기 제한 없이 계속 확장 가능	테이블 크기 이상 저장 불가
삭제 연산	연결 리스트 노드 삭제로 구현 간단	삭제된 공간에 Dummy 값 지정 필요
성능 영향	로드 팩터(Load Factor)가 1 이상이어도 동작	로드 팩터가 커지면 성능 급격히 저하

💡 로드 팩터 (Load Factor $\alpha$):

$\alpha = \frac{\text{전체 저장된 키 개수}}{\text{해시 테이블 전체 크기}}$

개방 주소법에서는 로드 팩터가 일정 수준(보통 0.7~0.8) 이상이 되면 해시 테이블의 크기를 재할당(Rehashing)해야 합니다.

4. 시험 단골 출제 유형 체크

1. Q. 해시 테이블의 평균 탐색 시간 복잡도는?
2. 👉 $O(1)$ 입니다. (최악의 경우 모든 데이터가 한 슬롯에 몰리면 $O(N)$)
3. Q. 선형 조사법(Linear Probing)에서 특정 해시 영역 근처에 데이터가 뭉치는 현상을 무엇이라 하는가?
4. 👉 1차 군집화 (Primary Clustering) 현상입니다.
5. Q. 충돌 해결 기법 중 이중 해싱(Double Hashing)의 목적은?
6. 👉 충돌 발생 시 이동하는 탐색 보폭을 다르게 하여 군집화(Clustering) 현상을 방지하기 위함입니다.