7.6 고급 탐색 구조: 해싱

7.6 고급 탐색 구조: 해싱

해싱이란?

해싱은 완전히 다른 방법을 사용한다. 비교하는 것이 아니라 키값에 산술적인 연산을 적용하여 레코드가 저장되어야 할 위치를 직접 계산하는 것이다. 따라서 탐색은 테이블에 있는 레코드를 하나씩 비교하는 것이 아니라 탐색키로부터 레코드가 있어야 할 위치를 계산하고, 그 위치에 레코드가 있는지를 확인만 하면 된다. 해싱에서 키값으로부터 레코드가 저장될 위치를 계산하는 함수를 해시함수(hash function)라고 한다. 또한 해시함수에 의해 계산된 위치에 레코드를 저장한 테이블을 해시 테이블(hash table)이라 한다.

예를 들어, 탐색키가 모두 1-1000 사이의 정수라고 가정. 가장 빠르게 탐색할 수 있는 방법은 1000개의 항목을 가지는 배열을 만드는 것. 자료의 삽입과 탐색키를 인덱스로 생각하고 그 위치에 저장하거나 읽어오면된다. 이 경우의 해시 함수는 h(key) = key가 된다. 연산은 명백하게 O(1)이다. 이것이 해싱의 기본 아이디어이지만 빠르게 탐색할 수 있지만 이를 위해 1000개의 우편함이 필요하다.

탐색키가 문자열이거나 실수, 또는 굉장히 큰 정수라면 문제가 발생한다. 메모리가 부족하면 보다 작은 배열을 사용해야하고, 탐색키를 더 이상 직접 배열의 인덱스로 사용할 수 없다. 대신에 탐색키를 작은 정수로 대응시키는 해시 함수가 필요하다. 해시 함수는 탐색키를 입력받아 해시 주소(hash address)를 계산하는데, 삽입, 삭제, 탐색 연산은 모두 이 주소로 이뤄진다.

해싱과 오버플로

해시 테이블은 M개의 버킷(bucket)으로 이뤄지는 테이블이고, 하나의 버킷은 여러개의 슬롯을 가지느데, 하나의 슬롯에는 하나의 렝코드가 저장된다. 단순화를 위해 슬롯이 하나라고 가정하자.

키값 key가 입력되면 해시 함수로 연산한 결과 h(key) 가 해시 주소가 되고 이를 인덱스로 사용하여 항목에 접근한다. 그런데 버킷이 충분치 않으면 경우에 따라 서로 다른 키가 해시 함수에 의해 같은 주소로 계산되는 상황이 발생. 이것을 충돌(collision)이라고 하고, 충돌을 일으키는 키들을 동의어(synonym)라 한다. 다음은 해싱의 예를 보여주는데, 각 탐색키에 대한 해시 함수의 계산결과는 다음과 같다.

충돌이 발생하면 어떻게 될까. 만약 버킷에 여러 슬롯이 있다면 서로 다른 슬롯에 저장하면 된다. 그러나 충돌이 슬롯 수보다 더 많이 발생할 수도 있다. 이러한 상황을 오버플로(overflow)라 하는데 해당 버킷에 더 이상 항목을 저장할 수 없다. 따라서 해싱에서 오버플로를 반드시 해결해야 한다.

이상적인 해싱은 충돌이 절대 일어나지 않는 경우. 해시 테이블의 크기를 충분히 크게 하면 가능하지만 메모리가 지나치게 많이 필요하다. 따라서 실제의 해싱에서는 테이블의 크기를 적절하게 줄이고, 해시 함수를 이용해서 주소를 계산한다. 이러한 실제의 해싱에서는 충돌과 오버플로가 빈번하게 발생. 이상적인 경우의 O(1)보다는 떨어진다.

선형 조사에 의한 오버플로 처리

선형조사법은 해싱 함수로 계산된 버킷에 빈슬롯이 없으면 그 다음 버킷에서 빈 슬롯이 있는지를 찾는 방법이다. 이때 비어 있는 공간을 찾는 것을 조사(probing)라고 한다. 선형 조사법은 해시 테이블의 k번재 위치인 ht[k]에서 충돌이 발생했다면 다음 위치인 ht[k+1]부터 순서대로 비어 있는지를 살피고 빈 공간이 있으면 저장한다.

이 과정은 비어있는 공간이 나올 때까지 계속된다. 만약 테이블의 끝에 도달하면 다시 테이블의 처음으로 간다. 만약 조사과정에서 처음 충돌이 발생한 공간으로 돌아왔다면 테이블이 가득 찬 상태이다.

삽입 연산

선형 조사법으로 해시 테이블에 키값인 레코드를 저장해보자. 테이블의 크기 M=13이고 해시 함수는 키값을 테이블의 크리로 나눈 나머지 연산 h(k) = k%M을 이용한다면 각 키에 대한 해시 주소는 다음과 같이 계산된다.

(1) 45, 27, 88, 9 까지의 삽입은 문제 없다. 해당 주소가 비었기 때문이다
(2) 71의 삽입에서 충돌이 발생한다. 선형 조사법에서는 다음의 비어있는 공간을 찾느다. 따라서 7 위치에 71을 저장한다.
(3) 60의 삽입은 문제 없다. 8의 위치에 저장
(4) 46 삽입에서 다시 충돌이 발생. 비어있는 공간으 찾아 여러번 움직여야 11의 위치를 찾을 수 있고 여기서 46을 저장
(5) 38은 충돌 없이 12위치에 저장. 마지막 24는 충돌이 발생. 그런데 뒤로 남은 버킷이 없기에 처음으로 돌아가 검사한다.

그림을 보면 한 번 충돌이 발생하 ㄴ위치에서 항목들이 집중되는 현상을 볼 수 있다. 이를 군집화(clustering)현상이라 한다. 선형 조사법은 간단하지만 오버플로가 자주 발생하면 군집화 현상에 따라 탐색의 효율이 크게 저하될 수 있다.

탐색 연산

탐색은 삽입과 비슷한 과정을 거친다. 키가 입력되면 해시주소를 계산하고 해당 주소에 같은 키의 레코드가 있으면 탐색은 성공. 만약에 없으면 우째! 삽입과 같은 방법으로 계속 찾아야 한다. 이 과정은 해당 키의 레코드를 찾거나, 레코드가 없는 버킷을 만나거나 모든 버킷을 다 검색할 때까지 진행. 예를 들어, 다음과 같이 46은 탐색 에 성공하지만 39의 경우 다음 버켓은 27이고 다음 버켓이 비었으므로 탐색은 실패로 끝난다.

삭제 연산

선형 조사법에서 항목이 삭제되면 탐색이 불가능해질 수가 있다. 앞의 예에서 60을 먼저 삭제했다고 하자. 이 상태에서 46을 탐색하려구. 문제는 60이 있던 위치가 이제 비어있기 때문에 46의 위치로 갈 수가 없다. 이 문제를 어떻게 해결할 수 있음?! 빈버킷을 두 가지로 분류해야 한다. 즉 한 번도 사용하지 않은 것과 사용되었다가 삭제되어 현재 비어있는 버킷으로 나누어야 한다. 탐색과정은 한 번도 사용이 안 된 버킷을 만나야만 중단.

이차 조사법(quadratic probing)

군집화 문제를 완화시키기 위한 방법으로 충돌이 발생하면 다음에 조사할 위치를 다음 식에 의해 결정하는 방법이다.

(k(k)+i*i)%M for i = 0,1,...,M-1

따라서 조사되는 위치는 h(k), h(k)+1, h(k)+4, h(k)+9 와 같이 움직인다. 물론 계산된 주소에선느 나머지 연산을 적용해야 한다. 이 방법은 군집화 현상을 완화시킬
있는데 물론 2차 집중 문제를 일으킬 수는 있지만 1차 집중처럼 심각한 것은아니다. 2차 집준의 이유는 동일한 위치로 사상되는 여러 탐색키들이 같은 순서에 의해 빈 버킷을 조사하기 때문이다. 이는 다음에 소개할 이중 해싱법으로 해결할 수 있다.

이중 해싱법(double hashing)

재해싱이라고도 불리는 이 방법은 충돌이 발생해 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법. 선형 조사법과 이차 조사법은 충돌이 발생하면 해시 함수 값에 각각 1또는 j^2를 더해서 다음 위치를 얻는다. 따라서 해시 함수 값이 같으면 다음 위치도 같게 된다. 이중 해싱법은 해시 함수 값이 같더라도 탐색키가 다르면 서로 다른 조사 순서를 갖도록 하여 2차 집중을 완화할 수 있다.

체이닝(chaining)에 의한 오버플로 처리

체이닝은 하나의 버킷에 여러 개의 레코드를 저장할 수 있도록 하는 방법으로, 버킷은 보통 연결 리스트로 구현한다. 체이닝을 이용해 크기가 7인 해시 테이블에 h(k) = k%7의 해시 함수를 이용해 8,1,9,6,13 삽입.

(1) 8저장 : h(8) = 8 % 7 = 1 저장
(2) 1저장 : h(1) = 1 % 7 = 1 충돌 => 새로운 노드 생성 및 저장
(3) 9저장 : h(2) = 9 % 7 = 2 저장
(4) 6저장 : h(6) = 6 % 7 = 6 저장
(5) 13저장 : h(13) = 13 % 7 = 6 충돌 => 새로운 노드 생성 및 저장

체이닝을 연결 리스트로 구현한다면 삽입하는 노드를 맨 끝이 아니라 맨 앞에 추가하는 것이 훨씬 더 효율적이다. 따라서 이 경우 1번 버킷 버킷에는 1-> 8의 순서로, 6번 버킷에는 13 -> 6 의 순서로 저장된다. 만약 파이썬의 리스트를 이용한다면 append() 연산을 이용해 리스트의 맨 뒤에 추가하는 것이 더 효율적일 것이다.

체이닝에서 항목을 탐색하거나 삽입하고자 하면 키값의 버킷에 해당하는 연결 리스트에서 독립적으로 탐색이나 삽입이 이뤄진다. 체이닝은 해시 테이블을 연결 리스트로 구성하므로 필요한 만큼의 메모리만 사용하게 되어 공간적 사용효율이 매우 우수하다. 또한 오버플로가 발생할 경우에도 해당 버킷에 할당된 연결 리스트만 처리하게 되므로 수행시간면에서도 효율적이다.

해시 함수

좋은 해시 함수는 충돌이 적어야 하고 주소가 테이블에서 고르게 분포되어야 하며, 계산이 빨라야 한다. 예를 들어, 영어 단어의 첫 문자만을 취하여 해시 주소를 만드는 것은 좋지 않다. (a로 시작하는 단어 vs z로 시작)

제산 함수

가장 일반적인 방법이 앞에서 사요한 것과 같이 나머지 연산을 이용하는 것이다. 테이블의 크기가 M일 때, 탐색키 k에 대하여 해시함수는 다음과 같다.

h(k) =k mod M

이때 가능하면 해시 테이블의 크기 M은 소수(prime number)를 선택한다. 즉, 1과 자기 자신만을 약수로 가지는 수라면 k % M이 ()dptj M-1을 골고루 사용하는 값을 만들어 낼 수 있기 때문이다.

폴딩 함수

탐색키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용된다. 예를 들어 탐색키가 32비트이고 해시 테이블의 인덱스가 16비트라고 가정. 만약 탐색키가 일부만을 사용한다면 많은 충돌이 발생. 보다 좋은 방법은 탐색키를 몇 개의 부분으로 나눠 더하거나 XOR와 같은 부울 연산을 이용하는 것. 이를 폴딩이라고 한다.

폴딩 함수에서 탐색키를 나누고 더하는 방법에는 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)이 대표적.

중간 제곱 함수

탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성하는 방법. 제곱한 값의 중간 비트들은 대개 탐색키의 모든 숫자들과 관련이 있다. 따라서 두 키값에서 몇 개의 자리가 같더라도 서로 다른 해싱 주소를 갖게 된다. 탐색키를 제곱한 값의 주간 비트들은 보통 비교적 고르게 분산된다.

비트 추출 방법

해시 테이블의 크기가 M=2^k일 때 탐색키를 이진수로 간주하여 임의의 위치 k개의 비트를 해시 주소로 사용하는 것이다. 이 방법은 간단하지만 탐색키의 일부 정보만을 사용하므로 해시 주소의 집중 현상이 일어날 가능성이 많다.

숫자 분석 방법

이 방법은 숫자로 구성된 키에서 각 위치마다 수의 특징을 미리 알고 있을 때 유용. 키의 각 위치에 있는 숫자 중에서 편중 되지 않느 수들을 해시 테이블의 크기에 적합한 만큼 조합해서 해시 주소로 사용. 학번에서 2020와 같은 숫자를 사용하지 않는 것!

탐색 키가 문자열인 경우

탐색키가 문자열인 경우 보통 각 문자에 정수를 대응시켜 바꾸게 된다. 예를 들면 a부터 z에 1부터 26을 할당할 수도. 각 문자의 아스키 코드나 유니코드를 사용.

def hashFn(key):
   sum = 0
   for c in key:
       sum = sum + ord(c) #아스키 코드 값을 sum에 더함 
   return sum % M

탐색 방법들의 성능 비교

해싱의 시간 복잡도는 O(1)이다. 그러나 충돌이 전혀 일어나지 않는 상황에서만이다. 따라서 실제로는 적재 밀도(loading density) 또는 적재 비율(loading factor)을 고려해야 한다.

α = 저장된 항목의 개수 / 해싱 테이블 버킷의 개수 = n / M

이상적인 경우 해싱이 가장 효율적인 방법이다. 물론 단점도 있다. 해싱은 그냐말로 순서가 없다. 정렬된 배열이나 이진탐색트리와 같이 어떤 항목의 이전 항목이나 다음 항목을 쉽게 찾을 수 없다. 또한 해시 테이블의 크기를 결정하는 것이 불명확하다. 즉 모든 키가 하나의 버킷으로 집중 되면 시간 복잡도는 O(n)이다.

7.7 맵의 응용: 나의 단어장

지금까지 공부한 탐색 기법들을 이용해 맵 ADT을 구현해보자. 맵을 구현할 수 있는 방법은 여러가지다.

• 리스트를 이용해 순차탐색
• 리스트를 정렬해 이진탐색
• 선형조사법으로 해시 맵
• 체이닝으로 해시 맵

이들 중에서 순차탐색 맵과 체이닝을 이용한 해시 맵을 구현해보자. 멥은 엔츠리의 집합이므로 엔트리 클래스가 필요하며 엔트리에는 키와 값이 필요하다.

class Entry:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        
    def __str__(self):
        return str("%s: %s" % (self.key, self.value))

리스트를 이용한 순차탐색 맵

순차탐색 맵 sequential map을 구현해보자. 데이터 멤버로 엔트리를 저장할 테이블이 필요하다.

class SequentialMap:                       #순차탐색 맵 
    def __init__(self):
        self.table = []                    #맵의 레코드 테이블
        
    def size(self): return len(self.table) #레코드의 개수 
    def display(self, msg):
        print(msg)
        for entry in self.table:            # 테이블의 모든 엔트리에 대해서
            print(" ", entry)               #출력(연산자 중복함수 사용)

이제 삽입연산을 해보자. 리스트가 정렬되이 있지 않기에 어디에나 넣을 수 있지만 젤 뒤에 넣는 것이 가장 효율적이다.

    def insert(self, key, value):           #삽입 연산
        self.table.append(Entry(key, value))# 리스트 맨 뒤에 추가 

탐색은 7.5 절에서 구현한 순차탐색 함수 sequential_search()를 호출하기만 하면 된다. 이 함수의 시간 복잡도는 O(n)이다.

    def search(self,key):
        pos = sequential_search(self.table, key, 0, self.size()-1)
        if pos is not None : return self.table[pos] 
        else : return None 

삭제를 위해서는 우선 삭제할 레코드의 위치를 찾아야 한다. 위치를 알면 파이썬 리스트의 pop함수를 이용해 해당 레코드를 리스트에서 제거한다.(O(n))

    def delete(self, key):                 #삭제연산: 항목 위치를 찾아서 pop
        for i in range(self.size()):
            if self.table[i].key == key:   #삭제할 위치를 먼저 찾고 
                self.table.pop(i)          # 리스트의 pop으로 삭제 
                return

체이닝을 이용한 해시 맵

체이닝은 연결 리스트를 이용하므로 노드가 필요하다. 6장의 내용을 불러왓. 체이닝을 이용한 해시맵 클래스를 HashChainMap이라 하자. 해싱에서는 테이블의 크기가 먼저 결정되어 있어야 한다. 해시맵 클래스의 생성자에서 테이블의 크기M을 매개변수로 전달받아 크기가 M인 해시 테이블을 준비한다. 이제 데이터 멤버는 table과 M이다.

#체이닝을 이용한 해시 맵 
class HashChainMap:
    def __init__(self,M): #테이블의 크기 M // def랑 init 띄어야 해염
        self.table = [None]*M   
        self.M  = M

엔트리의 키가 문자열이므로 해시 함수는 문자열의 모든 문자에 대한 ASCII 값을 더하고 이를 테이블 크기로 나머지 처리하는 다음 함수 사용하자.

   def hashFn(self, key):      #사용할 해시 함수 
        sum = 0
        for c in key:           #문자열의 모든 문자에 대해 
            sum = sum + ord(c)  #아스키 코드 값을 모두 더함 
        return sum % self.M 

삽입 연산은 주로를 먼저 계산하고 새로운 노드를 해당 연결 리스트의 맨 앞에 추가하는 방법을 사용할 수 있다. 이 연산의 시간 복잡도는 O(1)이다.

   def insert(self, key, value): #key, value 입력 
        idx = self.hashFn(key)  #해시 주소 계산 
        self.table[idx] = Node(Entry(key, value), self.table[idx])  #전단 삽입

이 코드의 마지막 줄이 복잡하면 다음과 같이 풀어서 기술할 수도 있다.

	  entry = Entry(key, value)   #(1)엔트리 생성 
    #     node = Node(entry)          #(2)엔트리로 노드를 생성 
    #     node.link = self.table[idx] #(3)노드의 링크필드 처리 
    #     self.table[idx] = node      #(4)테이블의 idx항목: node로 시작 

삭제를 위해서는 먼저 탐색 연산이 필요하다. 만약 계산된 주소의 연결리스트에 해당 레코드가 있다면 삭제하면 된다. 이때, 단순연결리스트를 사용하기 때문에 삭제할 노드의 선행 노드를 알아야 한다는 것에 주의.

    
    def search(self, key):
        idx = self.hashFn(key)
        node = self.table[idx]
        while node is not None: 
            if node.data.key == key:
                return node.data
            node = node.link
        return None 
    
    def delete(self,key):
        idx = self.hashFn(key)
        node = self.table[idx]
        before = None
        while node is not None: 
            if node.data.key == key:
                if before == None:
                    self.table[idx] = node.link
                else: 
                    before.link = node.link 
                return
            before = node          #before 갱신 
            node = node.link       #node 갱신

맵의 출력을 위한 코드의 예는 다음과 같다. 노드가 하나라도 있는 주소에 대해서만 출력 하도록 하였다.

    def display(self,msg):
        print(msg)
        for idx in range(len(self.table)):
            node = self.table[idx] 
            if node is not None:
                print("[%2d]->"%idx, end='')
                while node is not None:
                    print(node.data, end=' -> ')
                    node = node.link
                print()

파이썬 딕셔너리를 이용한 구현

마지막으로 파이썬에서 제공하는 맵 구조인 딕셔너리를 이용해 앞에서와 같은 실행 결과를 만들어보자. 맵을 위한 클래스를 만들 필요 없이 딕셔너리의 객체를 바로 생성해 사용하면 된다. 구현한 코드와 결과는 다음과 같다.

d = {}
d['data'] = '자료'
d['structure'] = '구조'
d['sequential_search'] ='선형 탐색'
d['game'] = '게임'

if d.get('game'):
    print("탐색:game-->", d['game']) #탐색

d.pop('game') #항목 삭제