1. 해시 테이블(Hash Table)의 정의
- 개념: 키(Key)와 값(Value) 쌍의 데이터를 효율적으로 탐색하기 위해 설계된 자료구조.
- 작동 원리: 해시 함수(Hash Function) h에 키값을 입력하여 얻은 해시값 h(k)를 저장 위치(인덱스)로 지정하여 데이터를 관리하는 방식.
- 구성 요소: 데이터를 저장하는 각각의 공간을 슬롯(Slot) 또는 버킷(Bucket)이라고 지칭.
2. 직접 주소화 테이블(Direct-address Table)과의 비교
직접 주소화 방식의 한계를 극복하기 위해 해시 테이블을 활용.
| 구분 | 직접 주소화 테이블 | 해시 테이블 |
|---|---|---|
| 저장 방식 | 키 값 k를 그대로 인덱스로 사용함. | 해시 함수 h(k)의 결과값을 인덱스로 사용. |
| 공간 효율 | 키 범위만큼 공간이 필요하여 낭비가 심함. | 해시 함수를 통해 공간을 압축하여 효율적임. |
| 제약 사항 | 키가 정수가 아니면 구현이 곤란함. | 다양한 자료형의 키를 해시값으로 변환 가능. |
3. 해시 충돌(Collision)의 이해
서로 다른 키의 해시값이 동일하게 발생하는 현상.
- 원인: 키의 개수보다 해시 테이블의 크기가 작기 때문에 발생하는 논리적 필연성.
- 해결 방안:
- Separate Chaining: 충돌 발생 시 해당 슬롯을 연결 리스트(Linked List)로 이어 데이터 저장.
- Open Addressing: 빈 슬롯을 찾아 데이터를 저장하는 방식임 (Linear Probing 등).
- 설계 목표: 충돌을 최소화할 수 있는 효율적인 해시 함수 설계가 핵심.
4. 성능 및 효율성 분석
연산 속도는 매우 빠르나 메모리와의 트레이드오프(Trade-off)가 존재.
시간 복잡도 (Time Complexity)
- 평균: 저장, 삭제, 검색 모두 O(1)의 매우 빠른 속도 보장.
- 최악 (Worst Case): 모든 키가 동일한 해시값으로 충돌할 경우 O(n)으로 저하.
공간 효율성
- 데이터 저장 전 미리 슬롯(Bucket)을 확보해야 하므로 메모리 활용 면에서는 효율성이 다소 떨어짐.
- 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 생길 수 있음.
추가 정리
Q. 좋은 해시 함수(Good Hash Function)의 조건은?
- 고른 분포: 해시값이 특정 영역에 뭉치지 않고 전체 슬롯에 균등하게 퍼지도록 설계해야 함.
- 빠른 연산: 해시값 계산 자체에 걸리는 시간이 매우 짧아야 함.
Q. 해시 테이블 질문이 자주 나오는 이유?
- 실무 활용도: 실제 프로그래밍 언어의 Map, Dictionary 구현에 가장 많이 쓰이는 자료구조이기 때문.
- 지식 확장성: Array, Linked List, Tree 등 다른 자료구조와의 성능 비교가 용이.
핵심 정리
- 정의: 키를 해시값으로 변환하여 인덱스로 사용하는 Key-Value 기반 자료구조.
- 성능: 평균 O(1)의 시간 복잡도를 가지나 충돌 발생 시 성능 저하 위험이 존재.
- 포인트: 충돌 해결을 위한 Chaining과 Open Addressing의 차이를 명확히 인지하고, 좋은 해시 함수의 조건을 설명하는 것이 핵심.