자료구조 - 해시 함수와 엔트로피

해시 함수

파이썬의 객체는 이미 __hash__, __cmp__ 함수를 구현하므로 일반적으로 해시가 가능합니다. int나 float 같은 산술 타입은 수의 bit를 기반으로 해시값을 구하고 튜플과 문자열은 내용을 기반으로 해시값을 구합니다. 다만, 리스트는 값과 크기가 변경될 수 있으므로 해시를 지원하지 않습니다. (리스트의 값이 변경되면 리스트를 나타내는 해시값이 엉뚱한 색인을 참조할 수 있기에 사전의 키로 사용할 수 없습니다)

사용자 정의 클래스에서는 어떨까요? 기본 __hash__ 함수는 내장 함수인 id 함수를 이용해서 객체의 메모리 함수를 반환하고 __cmp__ 함수는 객체의 메모리 위치를 산술 비교합니다. 일반적으로 어떤 클래스의 두 인스턴스는 서로 다르고 해시 테이블 내에서 충돌이 발생하지 않으리라 예상할 수 있습니다.

class Point(object):
	def __init__(self, x, y):
    	self.x = x
        self.y = y

x, y 값이 동일한 Point 객체를 여러 개 생성하더라도 메모리에서는 서로 다른 위치에 위치해 있으므로 id 함수 값이 다르기에 객체 별로 해시값이 다르게 됩니다. 따라서 이 객체들을 모두 같은 set에 추가한다면 각각의 항목이 추가되겠죠. 만약 인스턴스화 한 객체의 메모리 주소가 아니라 Point 객체의 속성 (x, y)으로 사전이나 셋을 활용하려면 다음과 같이 Point 클래스를 변경해야 합니다.

class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __hash__(self):
        return hash((self.x, self.y))
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y    
        
>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
>>> Point(1,1) in set([p1, p2])
True

 

엔트로피

사용자 정의 해시 함수에서 충돌을 피하려면 해시값이 최대한 균일하게 분포하도록 해야 합니다. 만약에 키가 대부분 혹은 자주 충돌한다면 다른 값을 프로빙을 통해 계속 씨도해야되고 사전을 상당 부분 살펴보며 적당한 키를 찾아야 하기에 시작복잡도가 최악의 경우 $O(n)$이 소요되게 됩니다.

해시 함수가 얼마나 균일한 분포를 가지는지 아려면 해시 함수의 엔트로피를 재면 됩니다. $p(i)$는 해시 함수가 $i$를 출력할 확률로 모든 해시값의 확률이 같을 때 엔트로피가 최대가 되게 됩니다. 엔트로피가 최대가 되는 해시 함수는 최소 충돌을 보장하며 이를 완전 해시 함수라고 합니다.

$S = -\Sigma_i p(i) \cdot log (p(i))$

사전의 크기가 무한하다면 단순히 정수를 해시 함수로 사용하는 것이 이상적일 겁니다. 정수 그 자체가 해시값으로 사용되고 사전의 크기가 무한하므로 마스크값도 무한할 것이므로 해시값의 모든 bit를 사용하게 될 테니 말이죠. 따라서 서로 다른 어떠한 두 수에 대해서도 다름을 보장할 수 있고 해시 충돌이 발생하지 않습니다. 하지만 사전의 크기는 유한하기에 이렇게 할 수가 없습니다. 만약 항목이 4개인 사전은 마스크로 0b111을 사용하게 되는데, 5의 해시값은 5이고 501의 해시값도 5이기 때문에 충돌이 발생합니다.

---

크기가 N인 사전에서 마스크값을 구하려면?

2/3이면 해시 크기가 커지기에, N개를 채우기 위한 최소 버킷 크기를 구해야 합니다. 이는 2/3을 더 채우는데 필요한 N개에 N*2/3 을 더하여 구할 수 있습니다. 예를 들어 N=1039인 경우 최소 버킷 크기는 1731이 되게 됩니다. 여기서 그 항목을 담을 수 있는 사전의 최소 크기 (8; 32; 128; 512; 2048; ..) 을 찾는데 여기서는 2048이 되겠네요. 따라서 마스크 값은 bin(2048-1) = (1이 11개) 가 되게 됩니다.

---

결론적으로 유한한 사전에서는 완벽한 해시 함수는 존재할 수 없습니다. 하지만 저장할 값의 범위와 크기를 사전에 정의할 수 있다면 좋은 선택을 할 수 있는데, 예를 들어 사전의 키로 두 소문자의 모든 조합 (26*26=576) 을 사용한다면 다음 해시 함수를 사용할 수 있습니다.

def twoletter_hash(key):
	offset = ord('a')  # 97
    k1, k2 = key
    return (ord(k2) - offset) + 26 * (ord(k1) - offset)  # 0 <    < 676

• 이 해시 함수는 모든 두 소문자 조합에 대해 해시 충돌이 발생하지 않습니다. 
• 항목이 676개 사전이 될 것이므로 2048 해시 테이블이 사용되고 마스크값은 bin(2048-1) 이 사용됩니다.

 

다음 예시는 나쁜 해시 함수를 선택한 사용자 정의 클래스가 얼마나 느릴 수 있는지 보여줍니다. 40배나 차이나네요.

import string
import timeit

class BadHash(str):
    def __hash__(self):
        return 4207

class GoodHash(str):
    def __hash__(self):
        return ord(self[1]) + 26 * ord(self[0]) - 2619

baddict = set()
gooddict = set()

for i in string.ascii_lowercase:
    for j in string.ascii_lowercase:
        key = i + j
        baddict.add(BadHash(key))
        gooddict.add(GoodHash(key))
        
>>> badtime = timeit.repeat("key in baddict", setup="from __main__ import baddict, BadHash; key=BadHash('zz')", repeat=3, number=1000000)
>>> print(min(badtime))
17.854072561000066

>>> goodtime = timeit.repeat("key in gooddict", setup="from __main__ import gooddict, GoodHash; key=GoodHash('zz')", repeat=3, number=1000000)
>>> print(min(goodtime))
0.4189556409992292