챕터 8 (Hashing)

채승 ㅣ 2023. 1. 4. 01:34

해싱 - 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)는 값을 저장하는 버킷 주소(인덱스)를 가짐
  • 특정 키를 검색하고자 할 경우, 해시된 키(이진 비트열)를 기준으로 디렉터리를 검색하여 버킷 주소(인덱스)를 얻는다.

 

  • 장점 :
    1. 데이터가 증가해도 검색의 성능 유지됨
    2. 메모리 또는 디스크의 낭비 줄임
    3. 연결이나 링크(Link)등을 사용하지 않아 접근시간이 일정
  • 단점
    1. 인덱스 테이블을 생성해야함
    2. Tree의 bucket을 쪼개거나 합치는 과정 중에 부하
    3. 버킷 주소(인덱스)를 통해 간접적으로 검색하는 것이므로 추가적인 검색 횟수가 필요
    4. 테이블의 크기를 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 버킷)을 필요로 한다.

 

  • 장점
    1. 파일의 크기가 크더라도 레코드를 접근하기 위해 디스크 접근이 두 번을 넘기지 않는다.
    2. 버킷 주소(인덱스) 테이블의 크기가 작으므로 저장공간이 절약된다.
  • 단점
    1. 버킷 주소(인덱스) 테이블을 생성해야 하는 부담이 있다.
    2. 각각의 버킷 주소(인덱스)가 실제의 버킷(Bucket)을 포인트하고 있으므로 데이터의 숫자가 적으면 오히려 디스크의 낭비가 발생할 수 있다.
    3. 버킷(Bucket)을 버킷 주소(인덱스)를 통해 간접적으로 검색하므로 추가적인 검색이 필요함

 

'자료 구조' 카테고리의 다른 글

챕터 6-3 (Shortest paths)  (0) 2023.01.02
챕터 6-2 (MST)  (0) 2023.01.02
챕터 6-1(Graphs)  (0) 2023.01.02
챕터 5 (TREE)  (0) 2022.12.31
챕터 4(LINKED LISTS)  (0) 2022.12.30