해싱(Hashing)과 트리 해싱(Tree Hashing)

(해싱에 대한 개념은 제 개인적인 생각이 많이 섞여있어서 틀린 내용이 있을 수도 있다는 것을 미리 밝힙니다.)

해싱은 어떤 큰 데이터(스트링, 트리 등)가 있을 때 이 것을 하나의 수로 나타내어 비교를 하기 쉽도록(그리고 빠르도록)

할 때 유용하다. 기본적으로 컴퓨터에서 저장할 수 있는 수의 크기의 한계가 존재하기 때문에

보통 해시값은 아무리 커도 long long 범위 내에 들어 와야 한다. 그래서 modular 연산을 사용하게 되는데

그러면 문제가 생길 수 있는게 서로 다른 데이터 인데 해시값이 같은 경우가 생길 수가 있는 것이다. 그래서 원래의 해쉬테이블은

해시값이 단순히 해쉬테이블의 인덱스를 나타내고 그 인덱스에 실제 데이터가 링크드 리스트와 같은 형태로 연결되어서

결국 실제 데이터를 찾는 과정이 필요하기 때문에 상수연산이 안된다. 물론 해쉬값을 통해 접근하기 때문에 후보를 많이

줄여 주긴하지만 결국 시간 복잡도는 상수 시간이 아니고 구현도 더 복잡해진다. 

PS에서 사용하는 해싱은 (내가 생각하기엔) 이렇게 서로 다른 데이터인데 해쉬값이 같은 경우가 입력으로 들어오는 데이터 내에는

없다고 가정한다. 그래도 AC가 잘 나오는 이유는 보통 모듈러 연산을 하는 수가 꽤 크기 때문에

그만큼 확률이 꽤 낮기 때문이다. 

어쨌든 해쉬함수로 해시값을 만들면 서로 다른 두개의 스트링이나 트리의 비교에서 O(N) 이 걸리던 것을 O(1) 에

비교가 가능해 지기 때문에 복잡도를 한차원 낮출 수가 있다.

그럼 트리 해싱은 말 그대로 하나의 트리를 정수로 변환하여 편의를 도모하는 것일 것이다. 그렇다면 중요한건

하나의 트리를 정수로 변환하는 해쉬함수를 어떻게 정의할 것인가 하는 것이다.

해쉬함수를 제대로 정의하지 않는다면 충분히 큰 수로 모듈러 연산을 해도 Collision 이 발생할 확률이 생각처럼

낮아지지 않을 수도 있을 것이다. 우선 한가지 방법은 이것이다.

1. 트리를 전위 순회를 한 순서대로 트리상의 모든 노드들의 값들을 일렬로 펼친다.

2. 일렬로 펼친 데이터들을 가지고 문자열 해싱하듯이 하면 된다.

그렇다면 노드에 저장된 값의 범위가 클 경우에는 실제 문자로 표현할 수가 없기 때문에 트리의 노드마다

벡터를 가지고있어서 자식노드의 벡터들을 왼쪽부터 차례대로 합쳐서 현재노드의 벡터를 구성하는 식으로 생각할 수 있으나

 이렇게 하면 구현도 귀찮아지고 속도도 좀 느릴 수 있을 것이다. 이렇게 하지 말고 조금만 생각을 해보면

결국 벡터로 이어 붙여도 결국 왼쪽에 있는 자식의 서브트리의 모든노드가 그다음 자식의 서브트리의 모든노드보다

먼저 나오기 때문에 자식 서브트리들의 해시값들을 차례대로 잘 조립해 나가면 현재 트리의 해시값을 계산 할 수가 있다.

조립하는 방법은 현재 노드의 해시값에 맨왼쪽 자식의 서브트리의 노드 수만큼 base를 거듭제곱한 결과를 곱해주고

이 서브트리 자체를 해싱 한 결과를 누적해준다. 이것을 모든 자식에 대해 반복하면 현재 노드의 해시값이 완성된다. 즉, 

size[here] : here 를 루트로 하는 트리의 노드의 수

hash[here] : here 를 루트로 하는 트리의 해시값

c1, c2, c3, .... , ck 가 here 의 자식들일 때

hash[here] = 0;

for all ci which is child of here

hash[here] += hash[ci]

hash[here] *= size[ci]

물론 모든 연산 중간 중간에는 모듈러 연산이 들어가야한다.

앞에서 말한 '문자열 해싱하듯이 한다는 것'을 좀더 설명을 하자면 문자열을(혹은 선형 데이터들을)

base 진법으로 나타내는 것이다. 물론 그렇다면 각각 하나의 값들은 base보다는 값이 작아야 할 것이다.

그런데 여기서 한가지 고려해 주어야 할 것이 있다. 쿼드 트리의 경우에는 자식들의 순서가 하나라도 바뀌면

아예 다른 트리가 될 가능성이 있다. 자식들의 순서가 중요하기 때문이다. 하지만 일반적인 트리에서는

자식의 순서가 바뀌어도 결국 그대로 같은 트리이다. 그런데 방금 위에서 말한 해싱 방법에서는 자식들을

왼쪽에서 부터 차례대로 봐주면서 계산하기 때문에 순서가 중요하다. 그렇기 때문에 실제로는

같은 트리에 자식의 순서만 다른 경우에 해시 값이 다르게 나올 가능성이 있다. 그래서 순서를 강제해 주어야 한다.

순서를 강제해 주기 위한 하나의 방법으로는 자식 서브트리들을 해시값으로 정렬하 여 순서대로 해시값을 조립해 나가는 것이다