[자료구조] 해싱 (Hashing)

해싱 (Hashing)

• 검색 키 값을 입력하여 특정 알고리즘(산술 연산)을 통해 검색 자료의 위치(주소)를 계산하여 알 수 있게 하는 검색 방식
• 예시
  • 키 : 125
  • 산술 연산 : 125 MOD 100 = 25 → 25가 검색 자료의 주소가 된다.
• 검색 시간 복잡도 : $O(1)$

 

좋은 해싱 함수 조건

조건	설명
낮은 충돌 발생 빈도	충돌이 적게 발생할 수록 좋다.
높은 해시 테이블 사용률	해시 테이블을 고르게 분포시킬 수록 저장효율이 좋다.
빠른 해싱 함수 계산	해싱 함수가 계산 속도가 빠를 수록 해싱 검색에 걸리는 시간을 감소시킨다.

 

해싱 함수 종류

1. 나머지 함수

• 가장 일반적으로 사용되며 검색 키 값 K에 해시 테이블 크기 M으로 나눈 나머지를 해시 주소로 사용
• 예시
  • 검색 키 값 (K) : 125
  • 해시 테이블 크기 (M) : 100
  • 결과 : 125 MOD 100 = 25 

 

2. 접기 함수

• 검색 키의 비트 수가 해시 테이블 비트 수보다 클 때 사용
• 즉 K가 M보다 클 때 사용
• K를 M의 자릿수와 같은 크기로 분할하고 분할된 부분들을 이용해서 해시 테이블 주소로 만듬

접기 함수	설명
이동 접기 함수	- 분할된 부분들을 이동시켜서 오른쪽 끝자리가 일치하도록 맞춘 다음 더하는 방법 - K : 1234512345 (10자리) - M : 999 (3자리) - 123 + 451 + 234 + 5 = 813
경계 접기 함수	- 분할된 부분들 사이의 이웃한 부분을 거꾸로 더해서 계산 - 321(경계) + 451 + 432(경계) + 5 = 209 (원래 1209지만 앞의 1은 버려짐)

 

3. 중간 제곱 함수

• 검색 키를 제곱한 값 중 중간 부분을 주소로 이용
• 예시
  • K : 1234
  • 1234 * 1234 = 1522756
  • 가운데 4자리 2275를 주소 값으로 사용

 

4. 숫자 분석 방법

• 숫자로 이루어진 검색 키값의 각 자릿수의 분포(충돌 가능성)를 미리 분석하여 해시 주소로 사용
• 즉, 검색 키값의 각 자릿수 중에서 가장 충돌 발생 가능성이 큰 자릿수를 생략하고 가장 충돌 가능성이 낮은 자릿수만을 추출하여 주소로 사용
• 예시
  • K : 학번 20141050
  • 앞의 4자리는 입학 연도이므로 생략
  • 뒤의 4자리만 주소값으로 활용 : 1050

 

충돌 (Collision)

• 자료 저장을 위해 계산한 주소에 이미 자료가 있는 경우엔 충돌이 발생한다.
• 예시
  • 키가 25인 데이터가 먼저 테이블에 들어가 있는 상태에서 키가 125인 데이터가 도착하면 둘다 25가 주소가 되므로 충돌이 발생한다.

 

충돌 해결 방법

1. 개방 주소법 (Open Addressing)

• 해싱 함수로 얻은 주소에 데이터가 이미 있다면 다른 주소에 저장하도록 하는 방법
• 조사법 (Probing) 이라고도 불린다.

조사법	설명
선형 조사법	충돌이 발생하면 주소를 일정 상수만큼 증가시켜서 다시 조사
제곱 조사법	충돌 발생하면 주소를 조사 횟수의 제곱만큼 증가시켜서 다시 조사
이중 해싱	충돌이 발생할 경우 다른 해싱 함수를 이용하여 주소를 다시 조사

 

 

2. 체이닝 (Chaning)

• 한 주소에 여러 개의 데이터를 저장할 수 있도록 연결 리스트 기법을 이용하여 저장하는 방법