Hash Map 이란 무엇인가

해싱

이진 트리 탐색에서는 리스트의 값이 순서대로 정렬되어 있다는 점을 활용하여 로가디즘시간(리스트의 크기가 커지면 탐색 시간이 리스트 크기의 로그값만큼 증가하는)에서 탐색이 이루어지도록 탐색 성능을 개선시킬 수 있음을 보았다. 이 장에서는 보다 나아가 고정시간이 걸리는 탐색을 살펴보고자 한다. 이 컨셉은 “해싱”이라는 기법으로 불린다.

이를 사용하기 위해서는 리스트에서 원소가 어디쯤에 위치할 것인지에 대해 좀 더 많은 것을 알아야 한다. 만약 모든 원소가 있어야 할 위치에 있다면 단 한 번의 비교 만으로도 아이템을 찾을 수 있다.

해시테이블은 각각의 원소가 나중에 찾기 쉬운 위치에 들어가 있는 집합의 형태이다. 해시 테이블의 각각의 위치는 슬롯으로 불리는데 0으로 시작하는 정수값으로 된 이름을 가지고 있다. 초기에 이 해시테이블에는 아무런 원소도 들어있지 않고 모든 슬롯이 비어있다. 따라서 우리는 모든 값이 None인 리스트를 통해서 파이썬에서 해시테이블을 만들 수 있다.

해시테이블에서 특정한 값의 원소와 그 원소가 차지하는 슬롯의 관계는 해시함수로 정의된다. 해시함수는 원소 자체를 받아서 그 원소의 슬롯 이름을 리턴하는 함수이다. 만약 정수값을 담는 해시 테이블이라면 간단히 원소의 값을 해시테이블의 길이로 나눈 나머지를 슬롯 이름으로 하는 해시 함수를 사용할 수 있다. (h(item) = item % {len(list)}) 만약 길이 11인 테이블이 있다면 다음과 같은 예시가 가능할 것이다.

item            hash value
---------------------------
54              10
26              4
93              5
17              6
77              0
31              9

일단 해시값이 구해지면 우리는 이 원소를 해시값이 가리키는 위치에 저장하면 된다. 위 예시를 본다면 11개짜리 슬롯을 가진 테이블에 6개의 원소가 들어있다. 이 비율을 로드 팩터라 하며 테이블 크기에 대한 원소의 개수의 비율로 정의한다.

$$lambda = {number\ of\ items} \over {length\ of\ table}$$

이제 반대로 테이블 내의 특정 원소를 찾으려면 동일하게 해시 함수를 사용하여 슬롯 이름을 구하고, 테이블에서 해당 슬롯에 원소가 있는지 여부를 보면 된다. 이 검색 작업은 \(O(1)\)이다. 해시 함수는 찾고자 하는 원소의 위치를 한 번에 내 놓으므로, 모든 원소가 제위치에 있다면 집합의 크기에 관계없이 원소를 찾는데는 일정한 시간이 걸린다.

이상의 예에서 보듯이 모든 원소가 맵상의 고유한 위치를 가지고 있을 때 이 테크닉이 제대로 작동하게 된다. 예를 들어 44가 이 집합에 들어간다고 하자. 이미 77이 슬롯 0에 위치하고 있고, 새로운 원소 44의 해시값도 0으로 나온다. 이 상황은 문제가 된다. 즉 해시 함수에 의해 서로 다른 두 원소가 동일한 슬롯을 갖게 되는 것이다. 이 문제는 일반적으로 충돌(Collision)이라 불린다. 명백하게 이 충돌은 해시 테크닉의 함정이다.

해시 함수

어떤 집합에서 해시함수가 모든 원소에대해 고유의 슬롯을 배정해줄 수 있다면 이는 완벽한 해시 함수가 된다. 만약 원소나 집합이 절대 변경될 일이 없다면 이 완벽한 해시 함수를 작성하는 것은 가능하다. 하지만 불행히도 임의의 원소 집합에 대해서 완전 해시 함수를 시스템적인 방법으로 구하는 방법은 없다. 다행스러운 것은 효율적인 퍼포먼스를 구하기 위해서는 이런 완전 해시함수를 반드시 만들어야할 필요가 없다는 것이다.

완전 해시 함수를 갖는 또 하나의 방법은 테이블의 크기를 늘려서 지금의 해시 함수가 완전 해시 함수처럼 작동하도록 하는 것이다. 이 방법은 모든 원소가 계속해서 고유의 슬롯을 갖는 것을 보장할 수 있다. 이 방법은 작은 테이블에 대해서는 유용할 수 있지만 테이블의 크기가 커지면 그리 좋은 방법이 못된다. 예를 들어 각각의 원소가 9자리 정수 값이라고 하면 이 방법은 거의 10억개의 슬롯을 필요로 한다. 만약 고작 25명의 학생을 저장하려고 한다면 이는 메모리 공간의 지나친 낭비가 될 것이다.

우리의 목표는 충돌의 횟수를 최소화하고 계산하기 쉬우며 또한 원소들을 균등하게 해시 테이블 내에 배치하는 것이다. 이러한 해시 함수를 구하는 여러 방법들이 있는데, 우리는 그 중에서 몇 가지를 살펴볼 것이다.

접기(Folding Method)는 각 원소를 균등한 조각으로 나누는 방법으로 접근한다. 이 조각들은 다시 하나로 합쳐져서 해시 값을 구성한다. 예를 들면 전화번호 436-555-4601은 숫자로 변경, 2개씩 짝을 지은 그룹으로 나눌 수 있다. (43, 65, 55, 46, 01) 그리고 이 값들을 모두 더하면 210이 나온다. 이 값을 다시 한 번 테이블의 크기로 나눈 나머지를 구하면 1이 된다.

좀 다른 방식으로는 각 그룹의 숫자값 중 중간에 있는 숫자들을을 뒤집어서 계산할 수도 있는데, 43+56+55+64+01로 계산하여 219를 구할 수 있다. 이 값을 11로 나눈 나머지는 10이 된다.

다른 해시 함수의 계산 방법 중에는 중간 제곱법(mid-square method)이 있다. 이는 값을 제곱한 다음, 그 제곱한 숫자의 일부를 취해서 해시를 만드는 법이다. 예를 들어 44는 제곱하면 1936이 되는데 이중 가운데 두 숫자인 93을 취해서 11로 나누면 된다. 앞서 예를 들었던 해시 테이블을 나머지에 의한 슬롯과 중간 제곱법을 사용한 슬롯으로 만들어보자면

item            hash value      mid-square
--------------------------------------------------
54              10              3
26              4               7
93              5               9
17              6               8
77              0               4
31              9               6

위와 같이 나쁘지 않은 결과를 보여주게 된다. 또한 추가로 44를 넣을 때 그 해시값은 5가 나오므로 추가적인 충돌을 피했다.

숫자값이 아닌 문자에 대해서도 해시함수를 만들 수 있다. 예를 들어 “cat”이라는 문자열에 대해서는 각 문자의 ascii값(ordinal value)을 가지고 계산한다.

>>> ord('c')
99
>>> ord('a')
97
>>> ord('t')
116

99 + 97 + 116 = 312
312 % 11 = 4

이런 계산은 다음과 같은 코드로 구현한다.

def hash(astring, tablesize):
    sum = 0
    for pos in range(len(astring)):
        sum = sum + ord(astring[pos])
    return sum % tablesize

물론 이 코드는 다음과 같이 좀 더 간단하고 우아한 코드로 변경할 수 있다.

def hash(astring, tablesize):
    return sum(map(ord, astring)) % tablesize

문제는 이 함수는 모든 애너그램 단어들이 같은 해시값을 갖게된다는 단점이 있다. 따라서 각 글자의 순서에 따라 가중치를 주는 방법이 있다. cat은 각각 (99, 97, 116)의 정수값으로 나타나므로

99 * 1 + 97 * 2 + 116 * 3 =  641
641 % 11 = 3

과 같은 식으로 보정할 수 있다.

이 동작은 파이썬 코드로 다음과 같이 정리할 수 있다.

def hash2(astring, tablesize):
    def ord2(pargs):
        a, b = pargs
        return ord(a) * b
    return sum(map(ord2, zip(astring, range(1,len(astring)))))

해시값을 계산해내는 해시 함수는 그 외에도 다양한 방법으로 구현할 수 있을 것이다. 이러한 해시함수 구현에서 기억해야 할 것은, 해시 함수는 효율적이어야 하고, 저장/탐색 프로세스에서 매우 작은 비중을 차지해야 한다는 것이다. 해시테이블에서 해시 함수는 매우 빈번히 호출되므로, 만약 해시함수가 크고 복잡하다면 해시테이블 전체의 성능을 떨어뜨리게 될 것이다.

해시 충돌의 해법

이제 다시 충돌의 문제로 돌아가자. 두 개의 원소가 같은 슬롯 해시를 가지게 된다면 이를 해결할 시스템적인 방법이 필요하고 우리는 이것을 “충돌 해법”이라고 부른다. 이전에도 말했지만 해시함수가 완벽하다면 이러한 충돌은 일어나지 않을 것이다. 하지만 그것은 사실상 불가능하므로 충돌 해법은 해싱에서 매우 중요한 부분이 된다.

충돌 해법의 한 가지 방법은 만약 이미 선점된 슬롯을 부여받는다면, 그 슬롯으로부터 빈슬롯이 나올 때까지 다음 슬롯들을 모두 점검하는 방법이 있다. 이는 open addressing이라는 기법으로 해시값의 슬롯이 이미 선점되었다면 다음 슬롯으로 순차적으로 이동하는 것이다. 시스템적으로는 이는 한 번에 한 슬롯을 방문하게 되므로 선형 해법이라 볼 수 있다.

문제는 이 방식은 클러스터링을 유발한다는 것이다. 이 방식은 테이블에 원소를 삽입할 때 순차적으로 비껴나가면서 빈 칸을 채우게 되는데, 만약 반대로 값을 찾아야 한다면? 원소의 해시에 해당하는 슬롯에 들어가 있는 원소가 찾고자 하는 것이 아니라면 우리는 전체 리스트를 대상으로 빈칸을 만나거나, 원래 위치로 돌아올 때까지 탐색을 계속해야 한다.

뿐만아니라 충돌이 반복적으로 일어나는 경우 인근 슬롯들이 다른 해시값의 원소들로 채워지기 때문에 원래 슬롯을 사용해야 하는 원소들이 다른 위치에 저장되는 악순환이 발생할 수 있다.

open addressing의 클러스터링을 완화하는 한 가지 대책으로는 “바로 옆”이 아닌 “좀 떨어진” 곳의 슬롯을 사용하는 방법이 있다. 예를 들면 슬롯의 “+1″이 아닌 “+3을 반복하면서 빈 슬롯을 찾는 것이다. 즉 \(rehash(pos) = (pos + 1) % ({size\ of \ table})\) 대신에 \(rehash(pos) = (pos + 3) % ({size\ of \ table})\)을 사용하여 빈 칸을 찾고, 좀 더 일반적으로는 \(rehash(pos) = (pos + skip) % ({size\ of \ table})\)으로 정리하는데, 이 때 skip은 테이블 크기의 약수가 아니어야지 결과적으로 모든 슬롯을 방문하여 비어있는지 여부를 검사할 수 있게 된다.