해시 테이블

해시 테이블¶

해시 테이블이 어떻게 작동하고, 왜 성능이 그렇게 좋은지를 알아보기 위해 간단한 맵 구현부터 시작해서 해시 테이블가지 차차 진행해 보도록 한다.

나는 파이썬으로 일일이 구현해서 설명하지만, 실생활에서는 코드를 이렇게 쓰지 않는다. 그냥 사전을 사용하면 된다! 따라서 이 장의 나머지 부분에서 여러분은, 사전이라는 것이 존재하지 않으며 키를 값에 매핑하는 자료형을 구현하려고 한다고 상상하면 되겠다. 여러분이 구현해야 할 연산은 다음과 같다.

add(k, v):

키 k에서 값 v를 매핑하는 새 항목을 추가한다. 파이썬 사전 d에서 이러한 연산은 d[k] = v라고 쓴다.

get(target):

키인 target에 대응하는 값을 검색해서 반환한다. 파이썬 사전 d에서 이러한 연산은 d[target] 또는 d.get(target)이라고 쓴다.

지금 단계에서는 각 키가 한 번씩만 등장한다고 가정하겠다. 이 인터페이스를 가장 단순하게 구현하는 방법은 튜플로 된 리스트를 사용하는 것으로, 각 튜플은 키-값 쌍이 된다.

In [1]:

class LinearMap(object):
    
    def __init__(self):
        self.items = []
        
    def add(self, k, v):
        self.items.append((k, v))
        
    def get(self, k):
        for key, val in self.items:
            if key == k:
                return val
        raise KeyError

add는 키 - 값 튜플을 항목들이 들어있는 리스트에 추가하며, 이 작업은 상수 시간이다.

get은 for 루프를 사용해서 리스트를 검색한다. 만약 목표 키를 찾으면 그에 대응하는 값을 반환한다. 못 찾으면, KeyError를 일으킨다.(따라서 get은 선형이다.)

다른 대안으로는 리스트를 키로 정렬해 두는 방법이 있다. 그 뒤엔 get이 이분검색을 사용할 수 있으며, 그러면 O(log n)이다. 하지만 리스트의 가운데에 새로운 항목을 삽입하는 것이 선형이기 때문에 가장 좋은 옵션은 아닐 수 있다. add와 get을 로그시간으로 구현할 수 있는 다른 자료형도 있지만 (http://en.wikipedia.org/wiki/Red-black_tree), 그것조차 상수시간에 비하면 그다지 좋지 않으므로 이 정도로 하고 넘어가자.

LinearMap을 향상시킬 수 있는 방법 중 하나는 키-값 쌍으로 되어있는 리스트를 더 작은 리스트로 쪼개는 것이다. 다음은 LinearMaps 100개로 된 리스트인 BetterMap이다. 곧 다룰 것처럼, get의 증가 기준은 여전히 선형이지만 BetterMap은 해시 테이블로 가는 여정의 첫 단계라고 볼 수 있다.

In [4]:

class BetterMap(object):
    
    def __init__(self, n=100):
        self.maps = []
        for i in range(n):
            self.maps.append(LinearMap())
            
def find_map(self, k):
    index = hash(k) % len(self.maps)
    return self.maps[index]

def add(self, k, v):
    m = self.find_map(k)
    m.add(k, v)
    
def get(self, k):
    m = self.find_map(k)
    return m.get(k)

__init__은 n개의 LinearMap이 들어있는 리스트를 만든다.

find_map은 add와 get에서 사용되며 새로운 항목을 어느 맵에 넣어야 할지나 어느 맵을 검색할지를 알아낼 때 쓴다.

find_map은 내장 함수인 hash를 사용하는데, hash는 거의 모든 파이썬 객체를 받아 정수 하나를 반환한다. 그러나 이 find_map의 한계는 해시 테이블의 키에만 동작한다는 것으로, 변경 가능한 자료형인 리스트나 사전은 해시가 불가능하다.

동일하다고 간주되는 해시 가능한 두 객체들은 동일한 해시값을 반환하지만, 그 반대가 참일 필요는 없다. 두 개의 다른 객체가 동일한 해시값을 반환할 수도 있는 것이다.

find_map은 나머지 연산자를 사용해서 해시값들을 0에서 len(self.maps) 번위 내로 포장하며, 그래서 그 결과로 해당 리스트의 제대로 된 인덱스가 나온다. 당연하게도 그러면 여러 개의 다른 해시값들이 동일한 인덱스로 포장된다. 하지만 해시 함수가 골고루 잘 분배해 준다면(그걸 하라고 해시 함수가 설계된 거지만), 우리는 LinearMap 당 n/100개의 항목을 기대할 수 있다.

 Linearmaap.get의 실행시간이 항목의 개수에 비례하기 때문에, 우리는 Bettermap이 LinearMap보다 100배 가량 빠르리라고 예상할 수 있다. 증가 기준은 여전히 선형이지만, 최고차계수가 작아졌다. 그럭저럭 낫긴 해도 여전히 해시 테이블보단 별로다.

이제 해시 테이블을 빠르게 만드는 결정적인 아이디어를 소개한다. 만약 여러분이 LinearMaps의 최대 길이를 고정 유지할 수 있다면, LinearMAp.get은 상수 시간이 된다. 여러분은 그저 항목의 개수만 잘 확인하고, Lienar map당 항목의 수가 한계치를 넘으면 LinearMap을 추가해서 해시 테이블의 크기를 조절하면 되는 것이다.

다음은 해시 테이블의 구현이다.

In [5]:

class HashMap(object):
    
    def __init__(self):
        self.maps = BetterMap(2)
        self.num = 0
    def get(self, k):
        return self.maps.get(k)
    
    def add(self,k,v):
        if self.num == len(self.maps.maps):
            self.resize()
            
        self.maps.add(k, v)
        self.num += 1
        
    def resize(self):
        new_maps = BetterMap(self.num*2)
        
        for m in self.maps.maps:
            for k, v in m.items:
                new_maps.add(k, v)
        self.maps = new_maps

각각의 HashMap에는 BetterMap이 하나씩 들어있다. __init__은 단 두 개의 LinearMap을 가지고 시작해 항목의 개수를 기록하는 num을 초기화한다.

get은 동일한 get의 역할을 할 뿐이고, 여기서 실제 주목해야 할 작업은 add다. add는 항목의 개수와 BetterMap의 크기를 확인한 다음, 두 개가 동일할 경우 resize를 호출한다. 왜냐하면 두 숫자가 동일하면 LinearMap 당 평균 항목의 수가 1이라는 뜻이기 때문이다.

그러면 resize는 기존 것의 두 배 크기로 새로운 BetterMap을 만든 다음, 이전 맵에서 새 맵으로 항목들을 '재해싱'한다.

재해싱이 필요한 이유는 LinearMap의 개수를 변경하게 되면 find_map 내에 있는 나머지 연산자의 분모가 변경되기 때문이다. 그러면 이전에 동일한 LinearMap에 포장되어 있던 객체들이 나뉘어지게 되는데, 딱 우리가 원하던 작업이 아니겠는가?

재해싱은 선형 작업이고, 그러므로 resize도 선형이다. 내가 앞서 add가 상수 시간이 될 거라고 이야기했으니 이게 어찌된 일일가 싶겠다. 설명하자면 매번 크기를 늘릴 필요는 없기 때문에, add는 대개의 경우 상수 시간이고 가끔 resize를 할 때만 선형인 것이다.

그래서 n번 add를 실행하는 총 작업 시간은 n에 비례하며, 평균적인 add 1회에 걸리는 시간은 상수 시간인 것이다.

이게 어떻게 작동하는지 이해하려면, 빈 해시 테이블로 시작해 일련의 항목들을 추가한다고 생각해 보자. 두 개의 LinearMap으로 시작하니까 첫 두번의 add는 빠르다(크기 조절이 필요없다). 그것에 각각 작업이 1 단위가 든다고 가정하자. 그 다음 add는 크기조절이 필요하니까 처음 두 항목들을 재해싱해야 하고(2 단위 작업이 추가된다고 하자), 그 다음에 세 번째 항목을 추가한다(1 단위가 더해진다). 그 다음 항목을 추가하는 데는 1 단위면 되니까, 그럼 4개의 항목에 대해서 총 6 단위의 작업이 걸린 것이다.

그리고 다음 add는 5 단위가 소요되지만, 이후 3개에 대해서는 각각 1 단위씩이 필요하게 된다. 즉, 맨 처음부터 add를 8번 하는 데까지 총 14단위 작업이 든다는 얘기다.

그리고 다음 add는 9 단위가 피룡하고, 다음 크기 조절 전까지 7개를 더 추가할 수 있으니까 그렇게 되면 맨 처음부터 add를 16번 하는 데까지 총 30단위의 작업이 필요하다.

32회의 add 이후엔 총 62개의 단위 작업이 소요되는데, 이쯤하면 여러분이 패턴을 눈치 챌 때도 됐다. n번의 add후에, n이 2의 거듭제곱이 되는 시점에서 총 작업 수는 2n-2가 되며, 따라서 add 당 평균적인 단위 작업 수는 2 보다 약간 작다. n이 2의 거듭제곱일 땐 그게 최선이다. n이 다른 숫자일 땐 소요되는 단위 작업이 좀 더 크지만 그게 중요한 문제는 아니다. 여기서 중요한 점은 알고리즘의 증가기준이 O(1)이라는 점이다.

In [ ]:

그림을 통해 시각적으로 설명해 보겠다. 각 블록은 단위 작업을 나타내고 있다. 열은 각 add마다 필요한 단위의 합을 왼쪽부터 순서대로 보여준다. 처음 두 add는 한 단위만 소요되고, 세 번째는 3 단위가 소요되는 등으로 해석하면 되겠다.

추가적인 재해싱 작업은 점점 높을 탑으로 나타나며, 탑들 사이의 공간 또한 점점 멀어진다. 이제 탑을 눞혀서 모든 add에 들었던 크기 조절 비용을 분할해 보면, n번의 add를 한 총 비용이 2n-2라는 것을 시각적으로 볼 수 있다.

이 알고리즘의 중요한 기능은 해시 테이블의 크기를 조정할 때 기하 급수로 증가한다는 점에 있다. 다시 말해, 어떤 상수를 곱해서 크기를 증가시킨다는 것이다. 산술적으로 크기를 늘린다면 (이를테면 매번 고정된 숫자를 더하는 것처럼) add 당 걸리는 평균 시간은 선형이 된다.

내가 구현한 HashMap은 http://thinkcomplex.com/Map.py에서 다운로드가 가능하다. 그러나 굳이 이걸 사용할 필요는 없다는 건 알고 넘어가자. 해시맵을 사용하고 싶으면 파이썬 딕셔너리를 쓰면 된다.

출처 : 복잡계와 데이터 과학