자료구조 | Hashing Search

WHY

다른 탐색 방법은 n이 증가할수록 필연적으로 탐색 시간이 오래 걸림

 

WHAT

hashing search는 탐색키간에 비교를 수행하는 것이 아니라, 

키에 산술적인 연산을 수행해서 정보에 접근한다. 

 

적용 사례에는 사전이 있다. 

 

identifier, hash function, hash table, hash code를 알아두자

 

HASH TABLE

identifier가 저장된 고정된 크기의 표

(고정되지 않은 경우 dynamic hashing이라고 한다.)

dynamic hashing이란, reconfigure the hash table size flexibly according to the frequency of key collision

 

row는 bucket

col는 slot이라고 부른다. 

 

Identifier density 명칭 밀도

n/T : 전체 identifier 중에서 해시 테이블에 저장된 identifier의 비율

n = hash table에 저장된 identifier의 수

T = 전체 identifier의 수

 

loading density 적재 밀도

n / ( b * s ) : 전체 hash table의 크기에서 identifier로 채워진 비율

n = hash table에 저장된 identifier의 수

b = bucket

s = slot

 

 

오버플로우 overflow

이미 꽉찬 bucket에 해싱되는 경우

 

 

충돌 collision

서로 다른 identifier s1, s2가 해시 테이블의 같은 버킷 주소로 매핑되는 경우

bucket의 slot 수가 1인 경우에 충돌과 오버플로우가 동시에 발생할 수 있다.

 

동의어 synonym

같은 bucket 주소에 저장된 서로 다른 identifier를 synonym이라고 한다. 

그리고 이때 s1, s2는 동의어이다. 

 

해시 함수

해시 함수의 조건

1. 계산하기 쉬워야 한다. 

2. 명칭 간의 충돌을 최소화하여야 한다. 

3. 편중된 분포를 방지하여야 한다.

 

이상적인 형태 : uniform hash function 균등 해시 함수

임의의 identifier x가 각 버킷 i에 적재될 확률이 1/b (# of buckets)인 경우

 

해시 함수의 종류

1. mid square 중간 제곱 해시 함수

identifer를 제곱한 결과값에서 일부를 해시 테이블 주소로 사용한다. 

 

2. division (modulo)

identifer를 특정한 값으로 나누어서 해시 테이블 주소로 사용한다.

주의 : 나누는 수 D에 따라 skewed distribution이 발생할 수 있다. 

D가 소수, 홀수인 경우, 비교적 명칭이 고르게 분포함,

 

3. folding hash function

identifier에 해당하는 비트 열을 해시 테이블 크기 만큼 여러번 접어서 주소값으로 사용한다.

1) shift folding

ex) x = 12320324111220 이고, hash table size == 세 자리 수이라면, 

123/203/241/112/20으로 나누어 이를 더해준다. (값은 699) 그리하여

699에 저장해줄 수도 있다. 

 

2) boundary folding

분할한 문자열에서 짝수번째 문자열을 뒤집에서 덧셈을 수행한 뒤에 k자리 문자열을 만들어서 주소로 사용한다. 

x = 123/203/241/112/20였다면, 볼드 표시를 한 203 112 문자열을 각각 302, 211으로 뒤집어서 덧셈을 수행한다. 

값은 897이 된다. 

 

 

4. digit analysis 키 분석 해시 함수

identifer의 내용을 미리 예측할 수 있는 경우에 유용하다. 

identifier의 내용을 분석해서 해시 테이블 주소에 사용할 키 값을 추출한다. 

예를 들면, 20010611처럼 앞 4자리가 연도를 나타내는 경우, skewed distribution을 방지하기 위해

이를 미리 제거해줄 수도 있다. 

 

 

 

구현

class Hashing:
    def __init__(self, size, hf):
        self.size = size
        self.table = [None]*size
        self.collision = []
    def hf(self, key):
        total = 0
        for s in key:
            total += ord(s)
        return total % self.size
    def add_table(self, sym):
        bucket = self.hf(sym)
        if self.table[bucket] is None:
            self.table[bucket] = sym
        else:
            self.collision.append(sym)
    def show_table(self):
        i = 0
        for item in self.table:
            print(i, item)
            i += 1
symbol = ['for', 'while', 'if', 'else', 'elif',\
    'def', 'class', 'self', 'return', 'range', 'list',\
        'tuple', 'ceil']
h = Hashing(26, 1)
print("Symbols = ", len(symbol))
for item in symbol:
    h.add_table(item)
h.show_table()
print("Hash function = ", h.hf)
print("Collision = ", h.collision)
print("collisions = ", len(h.collision))

 

오버플로우

이미 해시 테이블의 가득 찬 버킷에 또 다른 identifier가 매핑되는 현상

이를 해결하기 위해 overflow handling을 한다. 

 

처리하는 방법에는

* open addressing

linear probing, quadratic probing, rehashing,

* chaining

이 있다. 

 

linear probing 선형 탐색법

특정 버킷에서 오버 플로우가 발생하면, 다른 버킷의 slot에서 빈 칸을 찾는다.

 해시 테이블을 순환하면서 순차적으로 탐색함

 

case 1. 버킷이 비어있는 경우 -> insert 

case 2. 버킷에 같은 단어가 들어있는 경우 -> report 

case 3. 버킷이 다른 키를 가지고 있는 경우 -> overflow. 다음 버킷을 찾아 움직인다. 

case 4. 탐색 결과 다시 홈 버킷으로 돌아오게 된 경우 -> ERROR

 

선형 탐색법의 문제는 identifier들이 '클러스터'를 형성하게 된다는 것이다. 

그러면 선형 탐색 시간이 길어져 결국 O(n)이 될 수도 있다.

 

이를 해결하기 위해 (clustering / overflow)

Quadratic probing, random probing, rehashing, chaining 방법을 사용한다. 

 

* Linear probing

 

* Quadratic probing

identifier collision이 발생하면, 바로 다음 빈 버킷을 탐색하는 대신, 홈 버킷으로부터 제곱만큼 떨어진 버킷을 조사한다. 

home, home + i, home - i, home + i^2, home - i^2 순으로 탐새

클러스터 발생 확률이 낮으며, 평균 탐색 시간이 감소한다. 

 

* rehashing

다른 해시 함수를 통해서 새로운 버킷을 탐색한다. 

 

* chaining

오버 플로우를 근본적으로 해결하는 방식

각 버킷을 연결 리스트로 구현한다.

그러나, 버킷 내부에서는 순차 탐색을 하게 되어 결국 O(n)이 필요하다.