해싱 - Hashing
- Key를 Address로 변환해 data 저장 및 검색
- 예시
- Keys of data: 12, 4, 23, 7, 3
- Hash function: H(K) = K mod 7
- 기술
- Hash table
- Bucket
- Hash address, bucket address
- 해싱의 필요 요소
- Hash function - key에 address를 부여하는 함수
- Collision resolution method - 충돌 시 해결 방법
- 시간 복잡도
- 이상적인 경우 O(1), 그러나 잘 되지 않음
- 이상적인 경우란, 메모리 등의 제한뿐만 아니라 key의 형식 등에도 규칙이 있어야함
충돌 - Collision
- 서로 다른 Key가 같은 address 주소를 Hash function을 통해 갖게 되는 경우
- 예시
- Keys of data: 12, 4, 23, 7, 3, 9
- Hash function: H(K) = K mod 7
- 시간 복잡도
- 충돌을 처리해야 하므로 O(1)이 될 수 없음
Hashing Techniques
Hash functions
- Division // 나눗셈의 나머지로 처리한다.
- Mid-sqaure // 제곱한 후 중간의 몇개의 숫자를 사용한다.
- Folding // 마지막 부분을 제한 모든 부분의 길이가 동일하게 나누고, 이 부분들을 연산하여 구한다.
- Boundary Folding // Folding과 동일하게 나눈뒤, 몇몇 부분을 역순으로 정렬해 더한 값을 사용한다.
- Digit analysis // 숫자의 배치를 분석해 구한다.
- Radix-Exchange // 다른 진법으로 간주하고 계산한 key를 원래 진법으로 다시 되돌려 주소를 계산한다.
- Pseudo-Random // 난수를 생성해 이용한다.
충돌 해결 방법 (or bucket overflow handling)
- Open addressing
- Linear probing // 다음 칸에 저장
- 장점 : 동적 메모리를 사용할 필요 없음
- 단점 : 바로 addressing이 불가능함
- Double hashing // Linear probling처럼 바로 다음 칸이 아닌 2번째 해시 함수를 불러와 몇 개 뒤의 칸에 저장할지 계산한다.
- etc.
- Chaining // 연결리스트와 비슷한 구조
- 장점 : 메모리 낭비가 없고, 탐색을 연결리스트에서 별개로 진행하므로 효율적이다.
- 단점 : 한 주소에 쏠릴 경우 오히려 더 느려진다.
universal hasing
- 임의의 키값이 임의의 해시값에 매핑될 확률 : 1/m (m은 해시 테이블의 크기)
- 해시함수 들의 집합 H중 무작위 하나의 함수를 통해 해싱을 진행한다.
- 예시
- 소수 m의 크기를 가진 해시테이블은 만든다.
- 키값을 r +1개로 쪼갠다
- 0부터 m−1 사이의 정수 중 하나를 r+1번 만큼 반복해 뽑는다.
- 이를 a=[a0,a1,…,ar]로 둔다. a의 경우의 수는 m^r+1가지가 된다.
- 해시함수를 다음과 같의 정의한다. ha(x)=Σr,i=0 (ai ki mod m)
- a가 m^r+1가지이므로 해시함수의 집합 H의 원소 수 또한 m^r+1개이다.
동적 해싱 (Dynamic Hashing)
- 데이터의 증감에 따라 배열의 크기를 동적으로 조절
- 오버플로우 발생시 테이블의 크기를 2배로 확장
- 해싱된 키(Key)를 인덱스로 사용하는 Binary Tree를 동적으로 변환하여 사용.
- 오버플로우(Overflow)가 발생한 버킷(Bucket)을 2개의 버킷(Bucket)으로 분할한다.
- 분할법은 해시된 키(Key)의 다음 유효 비트가 0인 키(Key)를 한 버킷(Bucket)에 두고 1인 키(Key)를 다른 버킷(Bucket)에 둔다.
- 부가적인 접근 구조(Directory)는 각 버킷에 대응하는 비트 열 형태를 구분할 수 있도록 Binary Tree형태로 구성한다.
- 레벨 i에 있는 노드는 해시된 키의 i번째 비트가 0에 해당하는 왼쪽 포인터와 1에 해당하는 오른쪽 포인터를 가짐
- 리프 노드(Leaf Node)는 값을 저장하는 버킷 주소(인덱스)를 가짐
- 특정 키를 검색하고자 할 경우, 해시된 키(이진 비트열)를 기준으로 디렉터리를 검색하여 버킷 주소(인덱스)를 얻는다.
- 장점 :
- 데이터가 증가해도 검색의 성능 유지됨
- 메모리 또는 디스크의 낭비 줄임
- 연결이나 링크(Link)등을 사용하지 않아 접근시간이 일정
- 단점 :
- 인덱스 테이블을 생성해야함
- Tree의 bucket을 쪼개거나 합치는 과정 중에 부하
- 버킷 주소(인덱스)를 통해 간접적으로 검색하는 것이므로 추가적인 검색 횟수가 필요
- 테이블의 크기를 2배로 늘리는 과정에서 시간이 많이 듦
확장 해싱 (Extendible Hashing)
- 트리의 깊이가 2인 동적 해싱 기법
- 일부 비트열만을 사용한 후 더 많은 버킷(Bucket)이 필요한 경우 비트열을 하나씩 추가
- 해싱 구조의 재구성이 한 번에 하나의 버킷(Bucket)에서만 발생 => 상대적으로 부하 적음
- 부가적인 접근 구조(Directory)를 저장하며, 해시 함수 적용 결과인 이진수 표현을 기반함
- 디렉터리 : 2d(d : 전역 깊이)개의 버킷 주소(인덱스)를 갖는 배열
- 해시된 키의 처음 d개 비트를 디렉터리 배열의 인덱스 값으로 결정하는데 사용
- 2d개의 디렉터리(Directory) 엔트리는 서로 다른 버킷 주소를 유지할 필요 X
- 지역 깊이 d' :각 버킷내의 해시된 키가 기반으로 하는 비트의 수
- 처음 d'(d' : 지역 깊이)개의 비트 값이 갖는 키가 하나의 버킷에 저장될 수 있으면 여러 디렉터리 엔트리가 같은 버킷 주소를 유지함
- 지역 깊이 d'과 전역 깊이 d가 같은 버킷에서 오버플로우가 발생할 경우, 디렉터리 배열의 엔트리 수는 2배가 됨
- 어떤 키를 삭제한 후, 모든 버킷에 대해 d > d'인 경우 디렉터리(Directory) 배열내의 엔트리 수는 절반이 된다.
- 대부분의 키(Key)의 검색은 2개의 블록 접근(디렉터리 or 버킷)을 필요로 한다.
- 장점
- 파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번을 넘기지 않는다.
- 버킷 주소(인덱스) 테이블의 크기가 작으므로 저장공간이 절약된다.
- 단점
- 버킷 주소(인덱스) 테이블을 생성해야 하는 부담이 있다.
- 각각의 버킷 주소(인덱스)가 실제의 버킷(Bucket)을 포인트하고 있으므로 데이터의 숫자가 적으면 오히려 디스크의 낭비가 발생할 수 있다.
- 버킷(Bucket)을 버킷 주소(인덱스)를 통해 간접적으로 검색하므로 추가적인 검색이 필요함
