[알고리즘] 12. 해시 테이블

해시 테이블

1) 해시 테이블 개념

 

• 저장과 검색의 복잡도

• 해시 테이블은 원소의 값에 의해 저장 위치가 결정되는 자료구조
• 단 한 번의 계산으로 저장 위치를 찾음
• 탐색 시간 복잡도:
- 배열: O(n)
- 이진 탐색 트리: 최악 O(n), 평균 O(log n)
- 균형 이진 탐색 트리 (예: 레드-블랙 트리): 최악 O(log n)
- B-트리: 최악 O(log n)
- 해시 테이블: 평균 O(1)

 

• 해싱(Hashing)

• 키 값을 통해 직접 주소를 계산하여 검색하는 방법
• 삽입과 삭제가 빈번한 자료에 적합
• 빠른 응답이 필요한 경우 유용

 

• 해시 테이블(Hash Table)

• 레코드를 저장하는 버킷들의 집합
• 키값을 해시 함수에 넣어 계산된 해시 주소를 기반으로 탐색

 

2) 해시 함수

해시 함수(Hash Function)

• 키 값에서 저장 주소를 계산하는 알고리즘
• 해시 함수 h(k)는 특정 k에 대한 테이블 주소를 계산

 

해시 함수의 성질

• 입력 원소가 균등하게 저장되어야 함
• 계산이 간단해야 함
• 대표적인 방법:
- 나누기 방법 (Division Method)
- 곱하기 방법 (Multiplication Method)
- 중간제곱법 (Mid-square)
- 접지법 (Folding)

 

대표적인 해시 함수 기법

• 나누기 방법(Division Method): 키값을 특정 수 m으로 나눈 나머지를 해시 주소로 사용
• 곱하기 방법(Multiplication Method): 입력값을 0~1 사이 소수로 변환 후 해시 테이블 크기 m을 곱해 주소 결정
• 중간제곱법(Mid-square): 키값을 제곱 후 중간 부분의 비트를 주소로 사용
• 접지법(Folding): 숫자를 접듯이 나눈 후 더하여 주소 생성

 

3) 해시 테이블의 충돌

충돌(Collision)

• 동일한 해시 주소에 두 개 이상의 원소가 저장되는 현상
• 충돌이 발생할 경우 해결 방법 필요

 

충돌 해결 방법

• 체이닝(Chaining): 같은 주소로 해싱된 원소를 연결 리스트로 관리
• 개방 주소법(Open Addressing): 테이블 내 빈 공간을 찾아 저장

 

개방 주소법 기법

• 선형 조사(Linear Probing): 충돌 발생 시 바로 다음 위치 탐색 (1차 군집 문제 발생 가능)
• 이차원 조사(Quadratic Probing): 충돌 시 제곱 단위로 이동 (2차 군집 문제 발생 가능)
• 더블 해싱(Double Hashing): 두 개의 해시 함수를 사용하여 충돌 방지

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.