동적 해싱 방법_확장성 해싱(extendible hashing), 해시, hash, 충돌 해결 기법, 버킷, 모조키

▣ 동적 해싱 방법_확장성 해싱(extendible hashing), 해시, hash, 충돌 해결 기법

동적 해싱에서 가장 많이 사용하는 방식으로 깊이가 2인 트리구조 

 

- 동작 원리 : 사용할 수 있는 비트스트링을 모두 사용하지 않고 일부 비트스트링만 사용한 후 더 많은 버킷이 필요한 경우 비트스트링을 하나씩 추가

- 특징 : 버킷을 쪼개고 합치는 재구조화가 한 번에 하나의 버킷에서만 일어나므로 상대적으로 적은 오버헤드가 발생하며, 현재 필요치 않는 버킷을 절약할 수 있음

오버플로우 발생 시 버킷을 2개의 버킷으로 분할

 

주소테이블 (Address Table)	데이터 인덱스역할을 하며 버킷에 대한 주소 포인터를 저장
디렉터리	정수값 d(디렉터리 깊이, 전역 깊이 - global depth)를 포함하는 헤더와 버킷들을 지시하는 2^d개의 포인터로 구성
버킷(bucket)	각 버킷은 지역깊이(local depth), p를 표시, 각 버킷을 위한 버킷 깊이 값은 디렉터리를 위한 디렉터리 깊이 값보다 작거나 같은 값을 가질 수 있음 레코드들을 실제로 저장하는 공간
모조키(pseudokey)	확장성 해싱 함수를 통해 레코드의 키를 일정 길이의 비트스트링으로 변환한 것 모조키의 처음 d 비트를 디렉터리 접근에 사용함

 

 

 

확장성 해싱 함수에 의해서 키->모조키(00000~11111)로 변환함, 디렉터리와 버킷으로 조직됨,

전역 깊이(d): 해시 값의 처음 d개 비트 수 (d는 임의 설정)
디렉터리: 2^d개만큼 포인터 공간이 할당됨, 포인터는 버킷을 가리킴, 모든 포인터가 상이한 것은 아님
버킷 깊이-(지역깊이)(p): 모조키가 공통으로 가지는 처음 비트 스트링의 길이

Ex) 모조키가 (00011,00111,01011,01010), d=3 -> (000)따서 깊이(p) 3인 버킷, (001)따서 깊이 3인 버킷, (01)따서 깊이 2인 버킷 <앞자리가 01(2개)로 같은 레코드 공간>

 

d >= p+1인 경우 분할하는 방법 (디렉터리 깊이 3, 2^3 = 8개 포인터 구성)

만원인 버킷의 p를 확인 -> p=1 -> p+1=2 -> 2번째 비트에 따라 두 그룹으로 분할
-> (100,101,110,111)의 두 번째 비트는 0과 1 -> [100,101]과 [110,111]으로 분할

 

■ 해싱 방법 개요

- 해싱 함수 : f(키 값) -> 주소

- 충돌(collision) : 두 개의 상이한 레코드가 똑같은 버킷으로 해싱 되는 것

- 오버플로우(overflow) : 하나의 홈 주소로 충돌된 동거자들을 한 버킷에 모두 저장할 수 없는 경우

구분	정적해싱	동적 해싱
개념	버킷 주소의 집합을 고정시켜 처리하는 해싱 기법 현재 파일 크기에 근거하여 해시함수 선택	데이터 증감에 따라 해시함수가 동적으로 변환되는 방법 버킷의 수를 고정시키지 않고 필요할 때 늘리거나 줄임 해싱된 키를 버킷 주소(인덱스)로 사용하는 이진트리를 동적으로 변환 디렉토리는 각 버킷에 대응하는 비트 열 형태를 구분할 수 있도록 이진 트리 형태로 구성 동적 변환은 버킷 분해나 통합을 거쳐 다중 레벨을 구성 해싱 충돌 문제 대처 위해 제안 버킷을 포인터로 가리키는 버킷 주소(인덱스)테이블을 생성/유지해야 함 오버플로우 발생시 테이블의 크기를 2배수로 확장 동적으로 변하는 다중 레벨 인덱스를 관리
특집	파일 크기 증가에 따라 주기적 해싱 구조 재구성 필요 해시함수 충돌과 오버플로 현상 잦음	버킷의 재구조화가 한번에 하나의 버킷에서만 일어나므로 상대적으로 적은 오버헤드 발생, 현재 필요치 않은 버킷 절약 가능

 

■ 충돌 해결 기법

구분	내용
개방 주소 지정 (open addressing)	오버플로 된 동거자를 저장할 공간을 해시 테이블 내에서 찾아 해결함 구현이 단순하나 불필요한 버킷을 탐색 오버플로 발생시 해시 테이블 내 다음 저장 위치를 결정하는 방법 1) 선형조사(linear probing) : 홈 주소에서부터 차례로 조사하여 가장 가까운 빈 공간을 찾는 방법 2) 이중 해싱(double hashing) : 다른 해시함수를 한 번 더 적용하는 방법
체인 (chain)	오버플로 발생시 동일 버킷에 들어갈 데이터를 linked list로 연결 연결을 위한 공간 오버헤드 발생, 레코드들의 개수를 미리 예측 못할 때 이용

 

 

---

 2018년 72번

정답 : 2번

확장해싱에서는 재구조화 시 단일 버켓에서만 실행되므로 오버헤드가 적다.

---

 

2019년 67번

정답 : 3번

구분	내용
개방 주소 지정 (open addressing)	오버플로 된 동거자를 저장할 공간을 해시 테이블 내에서 찾아 해결함 구현이 단순하나 불필요한 버킷을 탐색 오버플로 발생시 해시 테이블 내 다음 저장 위치를 결정하는 방법 1) 선형조사(linear probing) : 홈 주소에서부터 차례로 조사하여 가장 가까운 빈 공간을 찾는 방법 2) 이중 해싱(double hashing) : 다른 해시함수를 한 번 더 적용하는 방법
체인 (chain)	오버플로 발생시 동일 버킷에 들어갈 데이터를 linked list로 연결 연결을 위한 공간 오버헤드 발생, 레코드들의 개수를 미리 예측 못할 때 이용

* 다중해싱은 일반적으로 충돌이 일어날 때 여러 해시 함수를 적용하는 방법

---

 

2020년 72번

정답 : 1번

1) 버킷 분할이 일어날 때, 기존 버킷에 저장할지 새로 할당된 버킷에 저장할지 결정 하는 방법은 버킷에 있는 다른 레코드들에 의존하는 것이 아니라, 그 레코드의 해싱된 비트스트링(모조키)의 값에 따라 결정됨

 

---

 

2021년 66번

정답 : 1번

디렉터리 전역 깊이 (가)는 3이며, 각 버킷의 지역 깊이는 디렉터리의 포인터가 가리키는 개수에 따라 결정

세번째 버킷은 '010', '011' 포인터가 가리키므로, 앞 2개 비트가 '01'로 시작하는 비트스트링(모조키)의

레코드들이 들어가게 되고 지역 깊이 (나)는 동일한 시작 비트 자리수인 2가 됨

(가) 3, (나) 2 로 정답은 1번