9. Hashing(해싱)

해싱 

해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다.

[이름, 속성] 쌍의 집합으로 되어 있다

 

---

해싱 함수(Hashing Function)

데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.

 

중간 제곱(mid-square) 함수

식별자를 제곱한 후에 그 결과의 중간에 적당한 수의 비트를 취하여 버켓주소로 한다. 

비트 수는 버켓의 크기에 따라 결정된다. (r 비트는 2r 버켓 크기)

​

제산(division) 함수

hD(x)= x % D

버켓의 범위는 0에서 (D-1)까지 이며, D는 20보다 작은 소수로 나누어지지 않으면 충분하다고 실험적으로 입증되었다.

​

접지(folding) 함수

식별자 x를 여러 부분으로 나눈 후 나누어진 부분들을 더해서 x에 대한 주소를 얻는다.

​

숫자 분석 함수

식별자 x를 어떤 기수 r을 이용하여 숫자로 바꾼 다음, 필요한 부분의 숫자들을 추출하여 주소로 사용한다.

이 함수는 테이블에 있는 모든 식별자들을 미리 알고 있는 정적 파일과 같은 경우에 유용하다.

​

 

---

 

정적해싱에서 오버플로우 처리

 

개방 주소법

  오버플로우 발생 시 주변 빈 버켓에 식별자를 저장함.

 

폐쇄 주소법(체인법)

  오버플로우 발생 시 연결리스트에 저장함. 버켓마다 빈 연결리스트를 초기화함.