hash 기초

hash라고 했을때 헷갈리는 이유는 

자료구조로서 hash map (hash table) 과 

그 핵심함수인 hash function 이 헷갈려서 그런 이유가 크다.

비트코인에는 hash function이 내부적으로 사용된다.

자료구조로서 hash map은

key와 value가 있는데, key를 주면 value를 빠르게 토해내는 컨테이너..

기능으로 보자면 stl map이나 python dict 등과 비슷하다고 볼 수 있다.

단 map이나 dict는 보통 tree(그 중에서도 레드-블랙트리가 일반적)로 구현된다.

tree는 O(log N)의 복잡도를 가져서 hash의 O(1)보다 느리지만, 사용량에 따라 가변적으로 메모리를 할당하기 유리하기 때문.

거꾸로 말하면 hash는 미리 상당한 양의 메모리를 덩어리째 할당해야하는 구조라 trade-off가 있다고 볼 수 있다.

 

hash map은 O(1)의 속도를 위해서 쓰는것은 자명한데.. 어떤것이 빠른거냐.

Insert,Update,Delete,Search

위 네 가지 연산 모두 O(1)이다.

(물론 메모리공간을 처음에 충분히 할당한 경우이며, worst case 시나리오에서 collision이 발생하면 실제로는 이보다 느려질 수 있음)

c++에서는 stl map 을 쓰면 내부구현에 tree가 보통 사용되고, 내부적으로 tree가 아닌 hash가 사용되도록 하고 싶으면 unordered_map을 쓰면된다.

핵심함수인 hash function은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 

이게 무슨 뚱딴지 같은 소리인가 하겠지만.. 

일단 이해를 돕기위해 string to int hash function의 예를 들어보자.

임의의 string이 들어왔을때 1024이하의 숫자하나로 매핑이 된다고 해보자.

예를 들면 "Kim Wonil"이 들어왔을때 42로 매핑이 되고,

"Lee Hana"가 들어왔을때 27이 매핑되는 식이다.

이런걸 만들어서 어따가 쓸까..

1. hash map 자료구조를 hash function을 통해서 만들면 O(1)로 매우 빠른 자료구조를 만들수 있다.

2. 긴 길이의 데이터를 짧은 길이의 숫자로 바꿔주는 구조로 인해서 변경내용이 있는지 확인하는데 쓸 수 있다.

예를 들어서 겉보기에는 매우 비슷한 소스코드 두 개가 있다고 해보자.

그런데 둘의 내용이 일치하는지 아닌지 확실하지 않다고 해보자.

그러면 나이브한 방법으로는 두 파일을 바이트 단위로 비교하는 방법이 있을 것이다.

그런데 이렇게 나이브하게 하지 않고, 두 파일의 내용에 대해 각각 (string to int) hash function을 적용한다음 결과로 나온 숫자를 비교하는 방법도 있다.

예를 들어 첫번째 파일에서는 내용으로 해시한 결과값이 42인데 두번째 파일로 나온 값은 27이라면 두 파일의 내용은 확실히 다르다고 판정할 수 있다.

단, 해시값이 예를 들어 42로 동일하다고 해도 반드시 두 파일의 내용이 같다고 역으로 보장해주지 않는다.

이는, 큰 숫자를 작은숫자로 매핑하는 과정에서 반드시 충돌이 발생할 수 있다는 점을 상기해 보면 쉽게 이해가 된다.

이를 다시 적어보면 다음과 같다.

두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다)

해시 함수의 가장 기본적인 성질은 두 해시 값이 다르다면 원래의 데이터도 다르다는 것이다. 이 특징은 해시 함수가 결정적이기 때문이다. 

위의 내용중 바이트 단위로 비교한다는 나이브 접근이 심각해보이지 않을 수도 있는데, 

단 두개의 문서를 비교할때는 심각성이 크지 않을 수 있지만,

예를 들어 특정폴더에 있는 파일중 내용이 같은파일이 있는지 검사하는 프로그램을 짠다고 해보자.

나이브한 방법으로는 파일의 갯수가 n개라면 모든 pair에 대해서 n(n-1)/2번 비교를 해야 중복파일 여부를 알 수 있다. 즉 $O(n^2)$

그런데 위의 해시함수를 사용한 방법으로는 해시함수값 끼리만 숫자비교를 하면 되기 때문에 $O(n)$ 으로 수행속도를 줄일 수 있다.

3. 함호학이나 비트코인에서 사용되는 해시 함수는 관련글(http://sevity.tistory.com/22) 참조

 

http://www.partow.net/programming/hashfunctions/index.html

위링크에 가보면 엄청 많은 종류의 해시펑션을 제공함..