해슁(Hashing)

1 해슁(Hashing)이란 무엇인가?

해슁(hashing)이란 한마디로 말해서 많은 양의 데이터(data)들을 그보다는 작은 크기의 테이블(table)로 대응(mapping)시켜 저장할 수 있도록 하는 일종의 데이터 관리 기법이다. 데이터들을 저장하거나 찾을 때 인덱스(index)라는 또다른 데이터 스트럭쳐(data structure)를 이용하는 대신, 각 데이터들이 테이블의 어느 영역에 위치할 것인가를 결정해주는 해쉬함수(hash function)를 사용하여 일정한 시간 내에 데이터들을 효과적으로 찾을 수 있도록 해주는 것이 바로 해슁이다. 따라서 데이터들은 순차적으로 저장되는 것이 아니라 테이블 전 영역에 걸쳐서 고루 분포하게 되며, 저장된 데이터를 찾을 때에도 해쉬함수를 사용하면 곧바로 그 위치를 알 수가 있기 때문에 빠르게 데이터를 검색할 수가 있게 된다.

그러나 해슁은 그 기본 개념으로 인하여 매우 치명적인 약점을 지니고 있는데, 해쉬함수가 이상적(ideal)이지 않은 이상 서로 다른 키(key)들이 테이블의 같은 위치로 결정될 소지가 다분하다는 것이 바로 그것이다. 이런 현상을 충돌(collision)이라 하며, 따라서 해슁에서는 이 충돌을 어떻게 해결할 것인가가 매우 커다란 이슈(issue)가 된다. 결국 해슁 알고리즘(hashing algorithm)은 해쉬함수와 충돌해결전략(collision resolution strategy)으로 나뉘게 된다.

 

2 해슁(Hashing)의 필요성

한 예를 통해서 왜 해슁이 필요한 지를 살펴보자. 미국에는 사람마다 SSN (Social Security Number)라는 9자리 수로 된 고유 식별 번호가 있다.(우리나라의 주민등록번호와 비슷한 개념이다.) 이제 이것을 키로 해서 각 데이터들을 데이터베이스(database)에 저장하려고 한다. 물론 우리는 그 9자리의 수로 만들어질 수 있는 1,000,000,000개의 키가 다 필요한 것은 아니고 어느 일정한 양의 키만 필요할 것이다. 그런데 문제는 새로운 데이터를 집어넣으려고 할 때 그 데이터의 SSN을 절대로 짐작할 수가 없다는 데에 있다. 그렇다고 해서 저 어마어마한 양의 저장 용량을 확보할 수는 없는 일이고, 어차피 우리는 일정한 수의 데이터만 처리할 것임은 분명할 텐데 말이다. 물론 새로운 데이터를 추가할 때마다 순차적으로 저장한다면야 SSN을 짐작할 수 없더라도 문제될 것은 없겠지만, 그 다음에 처리되어야 할 검색 부분에서 엄청나게 느린 속도를 체감해야만 할 것이다. 그러나 해슁을 쓴다면 이러한 문제를 말끔하게 해결할 수가 있다. 우선 원하는 데이터의 양이 10,000개라면 그만큼 크기의 해쉬 테이블(hash table)을 미리 할당해 둔다. 그런다음 0 < f(SSN) < 10,000인 값을 가지는 해쉬함수 f(SSN)을 정의하면 SSN을 미리 짐작할 수 없더라도 적당한 영역에다 데이터를 저장할 수가 있게 되고, 또 검색할 때도 데이터베이스의 앞에서부터 순차적으로 찾을 필요 없이 단번에 그 데이터의 위치를 알 수 있게 된다. 즉 해슁의 정의에서 언급한 대로 예측할 수 없는 많은 양의 데이터들을 일정한 시간 내에, 정해진 용량 안에다 효율적으로 저장할 수가 있는 것이다. 이것이 바로 해슁이 데이터를 다루는 데 있어서 많이 쓰이는 이유이다.

 

3 해슁 알고리즘 (Hashing Algorithm)

해슁 알고리즘(hashing algorithm)은 해슁을 위한 구현 부분으로, 다음과 같이 크게 세 가지로 구분할 수가 있다.

1. 완전 해슁 (Perfect Hashing)

   완전 해슁은 나중에 좋은 해슁 기법으로 언급될 simple uniform 해슁을 의미한다. 즉 서로 다른 키(key)값이 해슁에 의해 주소값을 할당받을 때, 주소값이 절대로 겹치지 않는 이상적인 해슁을 의미한다. 물론 이런 방식은 일대일대응 이외에는 존재하지 않는 방식으로 이상적인 것이다.

2. 정형 해슁 (Conventional Hashing)

   데이타 개수를 이미 알고 있어서, 데이타들이 저장될 주소 범위를 미리 데이타 개수만큼 지정해 두는 방식을 의미한다. 즉, 필요한 메모리의 크기는 미리 측정되고 미리 할당받아야 한다.

3. 동적 해슁 (Dynamic Hashing)

   정형 해슁의 문제점은 데이타를 입력하기 이전에 데이타 개수에 대한 정보가 있어서 메모리를 미리 할당받아야 한다는 점이다. 일반적으로 시간이 지남에 따라서 데이터의 양의 증가하게 되므로 잘못된 측정으로 데이터가 메모리의 범위를 넘게 되면, 더 큰 메모리 크기를 잡고 다시 해슁을 해야 하는 시간적, 자원적 낭비가 일어나게 된다. 동적 해슁은 이러한 데이터의 증감에 적응하기 위해서 나타난 것으로, 동적으로 메모리의 크기를 변화시키는 해슁 기법을 의미한다.

 

 

출처 : http://home.postech.ac.kr/~sinclair/doc/hashing/hashing.html