해싱(배준호 대리님)

[자료구조 목차]

 

해싱 개념

- 키 값에서 레코드가 저장되어 있는 주소를 직접 계산한 후 산출된 주소로 바로 접근이 가능하게 하는 방법

 

해싱 동작원리

해싱 관련 주요 개념

용 어	주요 개념
직접파일 (Direct File)	해싱방법을 기초로 하여 만들어진 파일  레코드를 식별하기 위한 키 값과 저장 장치에 저장되어 있는 레코드 사이의 사상관계가 성립 되어야 함
해싱함수	주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 의미하며, 키 값을 레코드의 물리적 주소로 사상시키는 사상함수(mapping function)라고도 함
해쉬 필드 해쉬 키	Hash Field, Hash Key  해싱함수가 레코드 주소를 계산하기 위해 사용하는 레코드의 키 값을 말함  해시함수의 입력값해시 필드해시 주소해시함수의 결과값
해싱표 (Table)	Hashing Table  해시 키를 사용하여 계산된 주소임  n개의 버킷(bucket)으로 분할되며, 한 버킷은 s개의 슬롯(slot)으로 구성
버켓	Bucket 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역  크기는 같은 주소에 포함될 수 있는 레코드 수  여러 개의 슬롯으로 구성
슬롯 (slot)	한 개의 레코드를 저장 할 수 있는 공간
충돌	서로 다른 두개의 키 값이 동일한 주소같은 버킷로 산출된 현상
동거자	동일한 주소로 산출된 두 키 값
오버플로우	더 이상 빈자리가 없는 과잉인데또 다른 레코드가 버켓에 저장되도록 해싱
적재밀도	실제 사용중인 키 값 / 버킷개수 X 슬롯 개수

 

해시함수 적용 알고리즘

알고리즘	설 명
나눗셈법 (Division)	- h(key) = key % M ( M: 버킷의 크기, 소수) - 정수인 탐색키(입력값)를 버킷의 크기로 나눈 나머지를 해시 주소로 사용 - 적재율은 70 ~ 80%가 적당
폴딩법 (Folding)	- 키 값을 여러 방식으로 접어 값을 합산한 후 버킷(Bucket) 주소로 활용 - 키값(입력값)을 레코드의 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더하거나 배타적 논리합(XOR)을 취하여, 해쉬 테이블의 주소로 이용하는 방법.   이동 폴딩(Shift Folding) : 수를 더함   경계 폴딩(Boundary Folding) : 이웃한 부분의 수를 뒤집어서 더함
중간제곱 함수 (Mid Square)	- 키 값의 중간 N자리를 뽑아서 제곱한 후 상대 번지로 사용 - 예) h(265) = 70225(256 제곱)의 중간값 = 022 - 제곱한 중간값인 022의 비트값을 아래와 같이 표현하면, 비트로 표현이 가능 - 중간 4비트 혹은 6비트를 선택.
기수 변환 (Radix Conversion)	- 주어진 레코드 키를 특정한 진법의 수로 간주하고 키를 변환하여 홈 주소를 얻는 방법 - 예) 키의 항목이 10진수 [1234]로 되어 있을 경우에 7을 기수로 하여 변화시킬 때 상대주소는[466] - 1*7^3 + 2*7^2 + 3*7^1 + 4*7^0
자릿수 분석 (Digit Analysis)	- 레코드 키를 구성하는 수들이 각 자리 별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 홈 주소로 사용하는 방법 - 정적 파일인 경우에 유용하며, 삽입과 삭제가 빈번히 발생하는 경우에는 비효율
무작위 방법(Pseudo-Random)	- 난수 발생 프로그램을 이용하여 각 레코드 키의 홈 주소를 결정하는 방법 - 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로 사용.

 

정적해싱  - 버켓 주소의 집합을 고정시켜 처리하는 해싱 기법

 특징

- 현재의 파일 크기에 근거하여 해싱 함수 선택

- 미래의 특정 시점의 파일 크기를 예상하여 해싱 함수 선택

- 파일의 크기가 커짐에 따라 주기적으로 해싱 구조를 재구성 해야 함

 

동적해싱

- 데이터베이스가 확장 또는 축소되는데 이에 맞추어 해싱 함수를 동적으로 변경 시키는 해싱 기법(Overflow 발생시 2배수 확장)

- 키 값을 사용하여 이진 트리를 동적으로 변화시킴

 

 

해싱 충돌문제 해결방안

구분	해결방안	설명
Static Hashing	Direct Chaining	- 동일 hash table에서 linked list 구성 - Record 저장과 Pointer 보관 Hash Table만 두고, 동일 Bucket 주소 record(Synonym)을 Linked List로 구성하여 저장함
	Indirect Chaining	- Hash Table과는 별도로 Overflow 공간을 확보하여 Synonym을 Linked List로 구성
	Overflow 영역처리	- Link를 두지 않고, Overflow 영역에 저장 -> Hash Table 없는 Record는 모든 Overflow 영역에서 검색
Dynamic Hashing	Linear Method	- 주소 + 1로 빈곳을 찾아 계속 검색함
	Re-Hashing	- Overflow 발생하지 않을 때까지 여러 개의 Hash 함수 적용
	Random Method	- 난수로 후속 주소로 선택하는 방법