기술사 학습노트 | imt-log

기술사 학습노트› 알고리즘› 해시 테이블

Algorithm · 한장정리

[기술사토픽] 해시 테이블(Hash Table) 완벽 정리 - 한장정리

해시함수 생성기법, 충돌 해결(개방주소법·체이닝), 적재율까지 기술사 핵심 학습노트

해시테이블HashTable해시함수해시충돌개방주소법체이닝선형조사법이중해싱정보관리기술사알고리즘

Ⅰ.개요

해시 테이블(Hash Table)은 해시 함수(Hash Function)를 이용해 키(Key)를 테이블의 주소(인덱스)로 변환하여 데이터를 저장·검색하는 자료구조이다. 평균 탐색 시간이 O(1)로, 대용량 데이터의 빠른 탐색에 최적화되어 있다.

구성 요소	설명
키(Key)	탐색 기준이 되는 입력 값
해시 함수	키를 테이블 인덱스로 변환하는 함수 h(k)
해시 테이블	데이터를 저장하는 배열(버킷 배열)
버킷(Bucket)	해시 테이블의 각 슬롯(저장 공간)
적재율(Load Factor)	α = 저장된 항목 수 / 테이블 크기 (0 < α ≤ 1)

시험 포인트

해시 테이블의 평균 탐색·삽입·삭제: O(1). 최악(충돌 집중): O(n). 적재율(α)이 높을수록 충돌 확률 증가 → 일반적으로 α ≤ 0.75 유지 권장.

Ⅱ.해시 함수 생성 기법

좋은 해시 함수는 키를 균등하게 분포시켜 충돌을 최소화해야 한다.

기법	방법	특징
나눗셈법(Division)	h(k) = k mod m (m: 테이블 크기)	단순, m은 소수 권장
곱셈법(Multiplication)	h(k) = ⌊m × (k×A mod 1)⌋, A≈0.618	m이 2의 거듭제곱에도 균등 분포
중간 제곱법	키를 제곱한 후 중간 비트 추출	키가 숫자일 때 유효
폴딩법(Folding)	키를 일정 길이로 분할 후 합산	긴 키 처리에 적합
문자열 해싱	각 문자의 ASCII 가중합 (예: djb2, SHA)	문자열 키에 적용

Ⅲ.충돌 해결 기법

해시 충돌(Hash Collision)은 서로 다른 키가 동일한 해시 주소에 매핑될 때 발생한다. 해결 방법은 개방 주소법(Open Addressing)과 폐쇄 주소법(Chaining)으로 나뉜다.

개방 주소법 (Open Addressing)

기법	탐사 방식	장단점
선형 조사법	h(k)+1, h(k)+2, … 순서로 빈 슬롯 탐색	구현 단순, 1차 군집화(Clustering) 발생
이차 조사법	h(k)+1², h(k)+2², … 간격으로 탐색	1차 군집화 완화, 2차 군집화 가능
이중 해싱	두 번째 해시함수로 간격 결정	군집화 최소화, 구현 복잡

폐쇄 주소법 (Chaining)

기법	설명	특징
체이닝(Chaining)	각 버킷을 연결 리스트로 구성, 충돌 시 리스트에 추가	적재율 제한 없음, 추가 포인터 메모리 필요

시험 포인트

개방 주소법 vs 체이닝: 개방 주소법은 추가 메모리 불필요하나 적재율 높을수록 성능 급감. 체이닝은 적재율 제한이 없고 삭제가 간단하나 포인터 오버헤드 존재. 이중 해싱이 군집화 방지에 가장 효과적이다.

Ⅳ.결론

Conclusion

해시 테이블은 평균 O(1)의 탐색·삽입·삭제를 제공하는 고성능 자료구조이다. 성능의 핵심은 균등 분포를 보장하는 해시 함수 설계와 충돌 최소화이다. 개방 주소법은 캐시 효율이 높고 체이닝은 유연성이 높으므로, 데이터 특성과 적재율에 따라 충돌 해결 기법을 선택해야 한다. 현대 언어의 HashMap, Dictionary 등은 모두 해시 테이블 기반으로 구현된다.

블로그: 기술사 학습노트 · imt-log.tistory.com

← 알고리즘 목록