데이터베이스 KOCW
Hash Function(Youtube)
Hasing
Hash function
- key 값과 address를 mapping 해주는 함수로 많은 양의 데이터에 index를 부여하기 위해 사용된다.
- 이러한 key이 address에 성공적으로 mapping되면 hash table에 기록한다.
- 가장 간단한 hash 함수는 modular 함수(나머지를 계산하는 함수)로 데이터를 저장하는 저장공간의 크기로 key값을 나눈 나머지에 해당하는 주소에 저장하는 방법이다.
Collision
- 서로 다른 key에 대한 hash함수의 값이 같을 수 있다. 이것을 collision이라고 한다.
- collision을 처리하는 방법은 여러가지가 있다.
- open addressing
- linear probe : 이미 해당 주소를 다른 key가 차지하고 있다면 다음 주소에 저장하는 방법
- plus 3 rehash : 이미 해당 주소를 다른 key가 차지하고 있다면 주소+3에 저장하는 방법
- Quadratic probing : 이미 해당 주소를 다른 key가 차지하고 있다면 주소+실패횟수^2에 저장하는 방법
- double hasing : hash 함수 2개를 조합하여 주소를 얻는 방법으로 실패가 일어날때마다 2개의 함수를 조합하는 방법을 바꾸는 방법
- closed addressing : 하나의 주소에 여러가지 key를 가질 수 있는 방법. 하나의 예로 linked list로 연결
- open addressing
Hash 함수의 목표
- minimize collision
- resolve any collision
- easy to caculate
- uniform distritution of hash values
Extendible hasing
bucket hashing
- disk에 page 단위로 저장하는 것을 착안한 방법 (page를 bucket이라고 생각해도 됨)
- 하나의 주소(bucket)에 여러개의 레코드 저장가능
- 문제점 : bucket 역시 한정된 공간이기때문에 overflow가 발생
- 다음 bucket에 저장하는 방법 : I/O를 한번 더 요구해서 overhead가 큼
- linked list로 다른 bucket을 연결 : 위와 동일한 문제
Extendible hashing
- overflow를 flexible 하게 대처할 수 있는 hashing 방법
- 가장 이상적인 방법은 extendibility가 linear 하게 늘어나는 방법, (=overflow가 일어나면 단위 공간만큼 늘어나는 방법)
- 하지만 여기서 소개할 방법은 2배로 늘어남
Extendible hasing 예
- 각 key를 2진수로 변환하고 이것을 pseudo key라고 함
- pseudo key는 d비트 까지만 index로 사용, d(global depth)를 늘리면 key를 2배로 확장할 수 있다.(확장 가능한 key)
- 여기서 hash table과 같은 개념으로 directory라는 개념이 등장
- directory
- key와 포인터(bucket의 주소)를 mapping 해줌
- d(global depth)를 header에 유지
- 2^d개의 버킷들을 가리킬 수 있으며 disk에 저장됨
- bucket도 header에 p(버킷의 깊이)를 저장함, 이 p는 해당 버킷을 가리키는 key의 깊이를 나타냄
- 모든 p는 d보다 작거나 같음. 버킷의 깊이가 p라면 2^(d-p)만큼의 포인터가 해당 버킷을 가리킨다는 의미
- Insert
- Insert로 bucket이 넘치면 해당 bucket보다 p가 1 높은 bucket 2개를 만든다
- 이전의 bucket을 가리키던 포인터와 데이터를 키값에 따라 새로운 버킷에 분할
- 단, 새로운 버킷의 p 값이 d보다 크다면 d의 값을 1늘려 디렉토리를 확장한다.
- delete
- buddy bucket은 bucket의 깊이 p가 같고 p-1비트 까지의 키 값이 같은 버킷의 쌍
- delete연산으로 buddy bucket의 데이터의 양이 하나의 버킷에 담길 수 있다면 buddy bucket의 내용을 하나의 버킷에 합치고 p를 1 낮춘다.
