[자료구조] 25 해싱 탐색

앞에서 이진 탐색, 보간 탐색은 탐색 키가 발견될 때까지 저장된 값들과 반복적인 비교 수행 

이런 경우 n이 높아질 수록 시간 소요가 많다

 

📌해싱 탐색(Hashing Search)

탐색 키 간의 비교 없이 탐색 키에 직접 산술 연산 적용

탐색 키 정보가 저장되어 있는 테이블 상의 위치 계산 => 주소를 통해 접근 

ex)Dictionary

👉 탐색하려는 명칭 x에 해시 함수를 적용하면 이 명칭의 정보가 저장된 해시 테이블의 버켓 주소가 반환 된다

 

📌해싱 탐색 시간 : O(1) => 상수만큼 걸린다

 

📌해시테이블(Hash table)

명칭 identifier 들이 저장된 고정된 크기의 표 

👉 행 row = 버켓 bucket 

👉 열 column = 슬롯 slot 

행이 b개 열이 s개 있다면 b*s개의 명칭을 적재할 수 있다

 

✔️명칭 밀도 (Identifier density : ID)

전체 명칭의 개수(T) 중 해시 테이블에 적재된 명칭 개수(n)의 비율 

👉 ID = n/T

 

✔️적재 밀도 (Loading density of factor : LD)

해시 테이블의 크기에 대해 적재된 명칭 개수(n)의 비율

👉 LD = n/b*s

 

✔️동의어

해시 체이블의 동일한 버켓 주소로 매핑된 서로 다른 명칭들을 말한다 

f(i1) = f(i2) 이면 i1 != i2 이지만 동의어이다

 

✔️오버플로우

명칭 i가 이미 꽉찬 버켓(full bucket)

 

✔️충돌

서로 다른 명칭 i1,i2가 해시 테이블의 같은 버켓 주소로 매핑되면 collision 충돌 발생 

 

❗️해시 함수는 계산이 쉬워야 함, 명칭 간 충돌 최소화 

=> 이 조건을 만족하는 해시 함수의 종류에는?❓

👇👇

✔️중간 제곱 해시 함수(mid-square)

자주 사용되는 해시 함수, 명칭을 제곱한 결과 값에서 중간의 일부분을 해시 테이블 주소로 사용 

해시 테이블에 2^r개의 버켓 존재? => r개의 비트 추출

ex) f(10010100,3) = 101 => s^3 = 8버켓

 

✔️나눗셈 해시 함수(Division)

명칭을 특정 수로 나눈 나머지를 해시 테이블 주소로 사용 

f(x) = x%D

나누는 수 D는 선택시 짝수로 정할 경우 편중 분포 현상 발생 (Skewed Distribution)

소수 로 정할 경우 명칭 고르게 분포

 

✔️폴딩 해시 함수(Folding)

명칭에 해당하는 비트 열을 여러번 접어서 주소 값으로 사용 

if) x = 12345678987

👉이동 폴딩 (Shift folding)

k자리수로 분할한 뒤 순서대로 더한 결과 값을 오른쪽에서 k만큼 추출,

if) k=3이라면 

123+456+789+87 = 455 ,

오른쪽에서 3만큼 추출하면 455

 

👉경계 폴딩 (Boundary folding)

k자리수로 분할한 뒤 짝수 번째 문자열을 뒤집어서 덧셈 수행,

if) k=3이라면

123+654+789+78=644

 

✔️키 분석 해시 함수 

편중 분포를 유발 할 수 있다고 생각되는 부분을 제거하고 진행하는 것

if) x= 20201008

년도4자리/월2자리/일2자리 라고 하면 월과 일때문에 편중 분포가 일어날 확률이 있으므로 그냥 아예 일어나지 않도록 

뒤에서부터 3자리를 이용해 진행하는 것

 

 

 

✔️오버 플로우 처리방법

🗝선형 탐색(Linear Probing)

특정 버켓에서 오버플로우 발생시 원래의 홈 버켓에서부터 비어 있는 다음 버켓을 찾을때까지 해시 테이블 순환하며 순차 탐색

선형 탐색에 의한 명칭 삽입 처리 시 발생할 수 있는 4가지 경우

👇👇👇

1. 탐색된 버켓이 삽입하려는 명칭(x) 이미 갖고 있는 경우 

중복된 명칭으로 보고 => 오류 처리 혹 필요시 해당 명칭의 특정 필드 값 갱신

2. 탐색된 버켓이 비어 있는 경우

해당 버켓에 명칭 저장

3. 탐색된 버켓에 x 말고 다른 명칭 포함하고 있는 경우

다음 버켓 탐색 진행

4. 탐색 결과 홈 버켓으로 다시 돌아온 경우

전체 버켓이 full인 상태 => 오류 보고 후 종료

 

🗝이차 탐색(Queadratic Probing)

충동 시 바로 다음 빈 버켓을 찾는게 아니라 홈 버켓으로부터 제곱만큼 떨어진 버켓 조사 

 

🗝재해싱(Rehashing)

버켓 오버플로우 발생 시 또 다른 해시 함수를 통해 새로운 버켓 재 탐색, 반복 반복

모든 해시 함수 다 사용해도 못 찾았다? => 오류 보고

 

🗝해시 체인(Hash chain)

각 버켓을 연결 리스트로 구현하여 특정 버켓에 충돌되는 명칭들을 연결 리스트로 관리 

근본적으로 오버플로우 방지 

👉시간 탐색 : 원래 해싱 탐색 시간 O(1) + 연결 리스트 탐색 시간 O(n) 

각 연결 리스트에는 버켓의 헤드 노드 존재

자료구조 개념 및 구현 <유석종 저자> 참고

❗️위와 같이 연결되어 있는 구조라 애초에 오버플로우가 발생할 수가 없다