Chapter 8. Hashing

1. Introduction

1. 개념
   - 자료를 입력할 때부터 검색시간을 고려하여 작성하는 자료구조
   - 빠른 검색을 위한 자료관리 기법

2. 해시 함수 (hash funciton)
   - 탐색 키(key) 를 입력받아 해시 주소(hash addr)를 생성
   - 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 됨
   (예) 영어사전에서는 단어가 탐색 키가 되고 이 단어를 해싱 함수를 이용하여 적절한 정수 i로 반환한 다음, 배열 요소 ht[i]에 단어의 정의를 저장

3. 해시 테이블 구조
   - 해시테이블 ht는 M개의 버킷(bucket)으로 이루어져있는 테이블
    ht[0].... ht[M-1] 의 원소를 갖는다.
   - 하나의 버킷은 s개의 슬롯(slot)을 가짐
   - 충돌(collision) : 서로 다른 두개의 탐색키 k1과 k2에 대하여 h(k1) = h(k2)인 경우
    → 이러한 충돌이 버킷에 할당된 슬롯 수보다 많이 발생하게 되면 버킷에 더 이상  항목을 저장할 수 없게 되는 오버플로우(overflow) 발생
   

   

4. 이상적인 해싱
   (생략. 필요시 넣겠다!)

5. 좋은 해시 함수의 조건
   - 충돌이 적어야 함
   - 해시 함수값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 함
   - 계산이 빨라야 함
   

6. 충돌 해결책
   (1) 선형 조사법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
   (2) 체이닝 : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경

2. Static Hashing (정적 해싱)
   (1) 해시 테이블(hash table)
    - 사전의 쌍들이 해시 테이블(hash table)이라는 ht 테이블에 저장
    - 해시 테이블은 ht[0], ht[1], … ht[b-1]과 같이 b 개의 버킷(bucket)으로 분할
    -  각 버킷은 s개의 사전 쌍(또는 사전 쌍들에 대한 포인터)를 포함
    - 한 버킷은 s개의 slot으로 구성되고, 한 슬롯은 하나의 사전 쌍을 저장
    - 키 값이 k인 한 쌍의 주소/위치는 해시 함수 h에 의해 결정
    - 해시 함수는 키 값을 버킷으로 사상(mapping)함
    - 어떤 키 값 k에 대해, h(k)는 0 ~ (b-1) 사이의 정수가 됨 (b … 버킷 개수)
    - h(k)를 k의 해시(hash) 또는 홈 주소(home address)라고 함
   
   ** [밀도]
      정의 : 해시 테이블의 키 밀도 (Key Density)는 n/T
                (n : 테이블에 있는 쌍의 수, T : 가능한 키의 총 개수)
   ** [테이블 적재 밀도(loading density)] / [적재 인수(loading factor)] a = n/(s*b)
       s - slot, b - bucket
   
    - 대개 키 밀도 n/T는 매우 작고, 키의 개수와 비슷한 해시 테이블의 버킷 수 b도 T보다 훨씬작음
    - 그렇기 때문에 해시 함수 h는 여러 같은 키들을 같이 버킷에 사상(mapping) 시킴
    - 이 때, 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 경우 k1과 k2를 h에 대한 동거자(synonym)라 함
    - 이상적인 조건 하에서는 사전 쌍들이 모두 해당 홈버킷에 저장됨
    - 이러한 경우 오버 플로(overflow)라 하며, 충돌(collision)은 새로운 쌍의 삽입 시에 비어있는
      자리가 없을 경우를 말함.
    - 각 버킷에 하나의 슬롯만 있다면(즉, s = 1), 충돌과 오버플로우는 동시에 발생
   
    - 해시테이블 예시 (skip)
   

1. 해시 함수
      : 해시함수는 키를 해시 테이블 내의 버킷으로 사상시킴
      : 해시 함수는 계산이 쉽고 충돌이 적어야 함
      : 해시 함수는 임의의 입력에 대해 해시 테이블을 편중하게 사용하지 않아야 함
       → k가 키 공간에서 임의로 선택된 키라면 h(k)=i가 될 확률은 모든 버킷 i에 대해
      1/b가 되는 것이 이상적이다. 이런 함수를 균일 해시 함수(uniform hash function)라 한다.
   

2. 해시 함수의 종류
   (1) 계산함수
     h(k) = k mod M
     - 해시 테이블 크기 M 은 주로 소수(prime number)
     - 나누기(division) 함수는 실제로 가장 많이 쓰이는 해시 함수로 키 값이 음이 아닌 정수라 가정
     - 홈 버킷은 모듈(%) 연산자에 의해 결정됨. 즉, 키 k를 어떤 정해진 임의의 수 D로 나눈 나머지를 홈 버킷으로 사용함
         h(k) = k % D
     - 버킷 주소의 범위는 0 ~ (D-1) 이고, 해시 테이블에는 적어도 b = D 개의 버킷이 있어야함
   
   
   (2) 중간 제곱 함수 ***
     - 탐색 키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성
     - 중간 제곱 함수는 키를 제곱한 후에 그 결과의 중간에 있는 적절한 수의 비트를 취해
       홈 버킷을 정함
     - 키는 정수라고 가정
     - 제곱 수의 중간 비트는 대개 그 키의 모든 비트에 의존하기 때문에 서로 다른 해싱주소를
        갖게 될 확률이 높음
   
   (3) 접지 함수
     - hash_index = (short) (key ^ (key >> 16))
     - 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)
     - 숫자로 된 키 k를 몇 부분으로 나누면 마지막 부분을  제외하고는 길이가 같아짐
     - 나눠진 각 부분들을 더하여 k에 대한 해싱 주소를 만듬
     - <shift folding : 이동 폴딩 / 이동 접지> : 마지막을 제외한 모든 부분들을 이동시켜
       최하위 비트가 마지막 부분의 자리와 일치하도록 맞춘 뒤, 서로 다른 부분들을
       더하여 h(k)를 얻는 방법.  
     - <boundary folding : 경계 폴딩 / 경계 접지> : 키의 각 부분들을 종이 접듯이 경계에서
       겹치게 한 다음, 같은 자리에 위치한 수들을 더하여 h(k)를 얻는 방법.
     - 접지 함수 예(skip)
   
   (4) 숫자 분석(digital analysis) 함수
     - 키의 각각의 위치에 있는 숫자  중에서 편중되지 않은 수들을 해시 테이블의 크기에
       적합한 만큼  조합하여 해시 주소로 사용
     - 테이블에 있는 모든 키를 미리 알고 있는 정적(static) file 과 같은 경우에 유용
     - 각 키를 어떤 기수(진법) r을 이용해 하나의 숫자로 바꾼 뒤 이 기수를 이용해  각 키의
      숫자들을 검사함
     - 가장 편향된(skewed) 분산을 가진 숫자를 생략해서 남은 숫자만으로 해서 해시테이블의
      주소를 결정 함
   

3. 오버플로 처리
   (1) 개방 주소 (open address)
     -  키 값이 k인 새로운 쌍 하나를 삽입 할  때, ht[h(k) + i] % b 의 순서에 따라
        해시 테이블을 검색
     - h는 해시 함수, b 는 버킷의 수,  0 i  b-1
     - 다 채워지지않은 버킷을 만나면, 검색이 끝나고 새로운 쌍이 그 버킷으로 삽입
     - 빈 자리가 있는 버킷이 없다면 해시 테이블의 크기를 늘려야 함
     - 해시 테이블의 크기를 다시 정할 때 해시 함수도 바뀜
     - 모든 사전 엔트리들은 새로 커진 테이블에 다시 사상(mapping) 되야 함
     - 선형 개방 주소법 예 (skip)
   
     ㄱ. 선형 조사법 (linear probing)   overflow !
       - 충돌이 ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어있는지 조사
       - 만약 비어있지 않다면 ht[k+2]를 살펴봄
       - 이런 방식으로 비어있는 공간이 나올 때까지 계속되는 조사 방법
       - 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 감
       - 만약 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 참
       - 조사되는 위치
         → h(k), h(k)+1, h(k)+2 …
   
     ㄴ. 이차 조사법 (quadratic probing)  
   
     ㄷ. 재해싱 (rehasing) / 이중해시법(double hashing)  overflow !
        - 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와
          다른 별개의 해시 함수를 이용하는 방법
        →  step = C-(k mod C)
        → h(k), h(k)+step, h(k)+2*step, ...
   
     ㄹ. 임의 조사법 (random probing)
   
   (2) 체인법 (chainning) overflow !
     - 오버 플로우 문제를 연결 리스트로 해결
     - 각 버킷에 고정된 슬롯을 할당하는 것이 아니라, 각 버킷에 삽입과 삭제가
       용이한 연결리스트를 할당
     - 버킷 내에서는 원하는 항목을 찾을 때는 연결 리스트를 순차 탐색
   
    [ - ]
     - 서로 다른 해시 값을 모두 비교하기 때문에 선형 조사법이 효율이 좋지 않음
     - 각 버킷에 대해 기 버킷에 대한 모든 동거자들을 키 리스트로 구성
     - 배열 ht[0: b-1]을 이용
     - ht[i]는 버킷 i에 연결된 체인 중 첫번째 노드를 가리킴
     - 체인법 예(skip)
      

3. Dynamic Hashing (동적 해싱)

1. 정적 해싱의 문제점
   - 미리 정해진 크기에 맞게 해시 테이블을 작성하므로 디스크 공간 낭비가 심함
   - 정한 적재 밀도를 넘어가게 되면 해시테이블과 함수를 주기적으로 다시 작성해야함
   - 해시 테이블과 함수를 작성하는 도중에는 연산이 불가능
   

2. 오직 하나의 버킷 안에 있는 엔트리들에 대해서만 홈 버킷을 변경
   

3. 하나의 연산에 대해 좋은 성능을 유지할 수 있는 해시 테이블을 제공하는 것이 목적
   

4. 디렉토리를 사용하는 동적 해싱
   - 버킷들에 대한 포인터를 저장하고 있는 디렉토리 d를 이용
   - 디렉토리 크기는 h(k, u)의 u 비트 수에 의해 바뀜
    (예) h(k,2)의 디렉토리 크기는 2^2= 4. 이때, 2를 디렉토리 깊이(depth)라고 함
   - 예(skip)
   

5. 디렉토리를 사용하지 않는 동적 해싱
   - 버킷 포인터 대신 버킷 배열 ht 사용
   - 배열의 크기는 매우 커서 동적으로 늘릴 필요가 없다고 가정
   - 활성화 된 버킷의 정보를 나타낼 q와 r 변수 (0 q  2r)를 이용하여 버킷 정보얻음
    > 항상 0부터 2r+q-1까지의 버킷만 활성화 됨
    > 나머지 버킷은 오버플로 버킷 (overflow bucket)
    > 0부터 q-1까지의 활성버킷은 h(k, r+1)을 이용하여 인덱싱
    > 나머지는 h(k, r)을 이용해 인덱싱
   - 예 (skip)
   

4. Bloom Filters

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.