해싱(Hashing)

주어진 키 값을 이용하여 목표 레코드 주소를 직접적으로 계산하는 방법

• 키 값에 연산(해시함수)을 적용하여 도출된 결과 값이 찾고자 하는 레코드가 있는 위치 주소가 됨

*해시 함수: 해시 함수 h(k)는 어떤 k에 대한 테이블 주소를 계산하기 위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 의미

해시 구성 요소

구성 요소	원문	설명
해시 테이블	Hash Table	한 개 이상의 버킷들로 구성, 신속한 저장과 탐색을 목적으로 만들어진 자료구조
버킷	Bucket	데이터 저장공간, 동일한 하나의 주소를 가지는 파일의 한 구역, 다수의 슬롯을 가질 수 있음
슬롯	Slot	한 개의 레코드 또는 데이터를 저장할 수 있는 공간
해시 함수	Hash Function	키 값을 해시주소로 반환하는 함수(제산법, 홀딩법, 제곱법, 기수변환법, 숫자분석법, 무작위법 등)
충돌	Collision	서로 다른 키가 같은 주소로 해싱되는 현상, 충돌이 발생한 경우 동거자 처리를 함, 다만, 비어있는 슬롯이 없는 경우 오버플로우가 발생
동거자	Synonym	서로 다른 키값을 가지지만 해시 함수에 의해 같은 버킷에 저장되는 값

오버플로우가 일어나면 별개의 버킷을 할당하여 처리할 수밖에 없다.

이것은 결국 또 한 번의 디스크 입출력을 필요하게 만들기 때문에 해싱 기법에서는 이 충돌로 인한 오버플로우를 어떻게 처리하느냐가 중요하다.

• 단순히 버킷 크기를 크게 한다면 오버플로는 감소하지만, 저장 공간 효율 또한 감소, 버킷 내 레코드 탐색 시간이 증가한다.

어떤 키값이 들어오더라도 균일하게 버킷에 레코드를 저장할 방법이 필요한데 현실적으로 불가능

맵핑 함수를 잘 만들어도 편향될수 있음

확장성 해싱(extendible hashing)

• 충돌에 대처하기 위해 제안된 기법

• 오버플로우가 일어난 버킷 안의 엔트리들만 재조정하고, 동적으로 해시 테이블의 크기를 변화시키면서 전체적인 성능을 높일 수 있음

• 입력되는 레코드의 수에 따라 버킷의 수가 변함

• 모조 키(pseudokey)

  • 해싱 함수를 통해 일정 길이의 비트 스트링으로 나온 값
  • 현재의 depth에 따라 키로 취급할 비트를 정함

• 전역 깊이(d)

  • 해시 값의 처음 d개 비트 수

• 디렉토리

  • 버킷들을 가리키는 2^d개의 포인터로 구성

• 버킷

  • 현재 버킷 깊이 p를 가짐
    • p(<=d): 지역 깊이(local depth)

확장성 해싱 삽입

8, 12, 7, 6, 5, 11 데이터를 차례로 삽입

이 수들의 이진수는 각각 1000, 1100, 0111, 0110, 0101, 1011

디렉토리 깊이 비트만큼의 최우측 비트를 모조키로

각 버킷의 크기(=슬롯의 수)는 2

초기 디렉토리 깊이 1
8삽입
8(1000)을 삽입하면 최우측 1비트가 0이므로 0번 디렉토리가 가리키는 버킷에 삽입

12 삽입
12(1100)의 최우측 1비트가 0이므로 0번 디렉토리가 가리키는 버킷에 삽입

7 삽입
7(0111)의 최우측 1비트가 1이므로 1번 디렉토리가 가리키는 버킷에 삽입

6 삽입
6의 최우측 1비트가 0이므로 0번 디렉토리에 삽입되면 오버플로우 발생

디렉토리의 크기를 증가시키고, 오버플로가 발생한 버킷에 대해서만
오버플로 버킷의 레코드들과 새로 저장할 레코드를 오버플로우 버킷과 새로 할당한 버킷에 분산
기존 버킷과 새로 할당된 버킷의 깊이 값 p는 모두 (p+1)로 설정

5 삽입
5(0101)이고 현재 디렉토리 depth가 2이므로 01디렉토리가 가리키는 버킷에 삽입

11 삽입
11(1011)은 11 디렉토리가 가리키는 곳으로 삽입되면서 오버플로 발생
하지만, 현재 같은 곳을 가리키는 디렉토리의 비트로 데이터를 분류할 수 있다면 굳이 디렉토리를 늘릴 필요가 없음

7은 0111, 5는 0101, 11은 1011이므로 7과 11은 이진수 11로 분류할 수 있고, 5는 01로 분류할 수 있으므로 버킷만 하나 할당하고 디렉토리를 늘리지 않음
오버플로 버킷과 새로 할당된 버킷의 깊이 값 p는 모두 (p+1)로 설정

디렉토리 오버플로우→ d < p+1 인 경우 디렉토리 크기를 증가 시킴(d+1)

삭제

• 삭제할 레코드를 찾아 삭제
• 한 버킷에 하나만 있는 레코드를 삭제하는 경우

  • 버디버킷을 검사하여, 두 버디에 있는 레코드들이 하나의 버킷으로 들어갈 수 있으면 합병하고 빈 버킷은 반환

    *버디 버킷: 두 버킷이 똑같은 버킷 깊이 p를 가지고 있고 저장된 레코드 모조 키들의 p-1 비트들이 모두 같은 버킷으로 원래 하나의 버킷에서 분할된 두 버킷

• 버킷의 새로운 깊이 값은 p-1
• 모든 버킷들의 깊이(p)가 디렉토리 깊이(d)보다 작게 되면 디렉토리 깊이(d)를 1감소
• 디렉토리의 엔트리 수가 반으로 감소하기 때문에 모든 포인터들을 적절히 재조정

확장형 해싱의 장단점

장점

파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번을 넘기지 않음

버켓 주소 테이블의 크기가 작으므로 저장 공간이 절약됨

단점

버켓 주소 테이블을 생성해야 하는 부담이 있음

버켓을 버켓 주소를 통해 간접적으로 검색하므로 추가적인 검색이 필요함

데이터의 숫자가 적으면 오히려 디스크의 낭비일 수 있음

참고

https://blog.naver.com/whwo161/221075172430
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sdug12051205&logNo=221575587063