Hashing

1 Hashing이란 무엇인가?

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

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

2 Hashing의 필요성

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

3 Hashing 알고리즘 (Hashing Algorithm)

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

• 완전 Hashing (Perfect Hashing)

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

• 정형 Hashing (Conventional Hashing)

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

• 동적 Hashing (Dynamic Hashing)

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

4 충돌해결전략 (Collision Resolution Strategy)

충돌(collision)이란 복수개의 키(key)들이 같은 데이터 영역으로 해쉬되는 것을 말하며, 또그 데이터 영역이 꽉 차서 더이상 데이터를 집어넣을 수 없게 되었음에도 불구하고 다른 키가그쪽으로 해쉬되는 것을 오버플로우(overflow)가 일어났다라고 말한다. 이 현상은 해쉬함수가 이상적으로는 각 키와 그것이 저장될 데이터 주소를 완벽하게 일대일 대응을 시켜야 함에도 불구하고 실제적으로는 그렇지 못하기 때문에 일어나는 것인데, 적절한 충돌해결전략(collision resolution strategy)을 이용함으로써 이러한 문제를 어느정도 해결할 수가 있다.

우선 생각할 수 있는 충돌해결전략에는 완전Hashing(perfect hashing)이라는 것이 있다. 이것은 말그대로 한 데이터 영역에 단 한 개의 키만이 대입되는 경우를 뜻하는 것으로, 들어오는 키값들을 어느정도 예측할 수 있는 경우에는 인위적으로 완전한 해쉬함수를 만들 수 있기도 하지만, 일반적인 경우에 있어서는 완전Hashing을 구현하기란 거의 불가능에 가깝다. 그다음으로 생각할 수 있는 간단한 방법으로 데이터 영역의 크기를 처음부터 매우 크게 잡는 것을 생각할 수가 있다. 그러나 이 방법 또한 데이터 용량의 낭비가 심하므로 실제로 사용될 지는 의문인 것이 사실이다.

위에 언급한 간단한 방법들 외에 매우 다양하고도 복잡한 충돌해결전략이 실제적으로 많이 사용되고 있는데, 크게 두가지 부류로 나눌수 있다. 한가지는 오버플로우가 일어났을 때 다른데이터 주소로 다시 해쉬 시키는 방법 - open addressing이라 부른다 - 이고, 나머지 한가지는 같은 데이터 주소 내에서 끝까지 해결을 보는 방법 - closed addressing이라 부른다 - 이다.

5 Hashing과 데이터베이스(Database)

지금까지 Hashing에 대한 기본적인 내용과 종류, 그리고 작동 원리에 대하여 알아보았다. 이제까지 한 내용들을 종합하여 Hashing의 장점과 단점을 정리하면 다음과 같다.

장점

·     ISAM(파일시스템)보다 세 배나 빠른 검색 속도를 지니고 있다.

·     데이타에 대한 입력이나 삭제가 쉽다.

·     검색 시간(retrieval time)이 데이타의 양과 상관없이 일정하게 유지된다.

단점

·     연속적인 데이터 검색에는 비효율적이다.

·     디스크 공간이 비효율적으로 사용된다

·     정형 Hashing의 경우, 데이터가 꽉 차서 디스크 공간을 늘리고 재구조화를하게 되면, O(n)번에 해당하는 디스크 검색을 해야 하므로 시간이 많이 걸리게 된다.

·     아직까지는 Hashing의 병렬성(concurency)와 회복(recovery)에 대한 연구가 부족하다.

그런데 이제까지 소개된 내용들이 그대로 데이타베이스에 이용되는 것은 아니다. 앞서 살펴보았던 것들은 데이타 스트럭쳐의 관점에서 메모리를 최적화하기 위한 방식으로 Hashing을 이용되는 것이었고, 데이타베이스의 관점에서는 다음에 설명하게 될 내용과 같은 측면에서Hashing을 다루게 된다.

우선 데이타베이스는 검색 속도가 그 데이타베이스의 성능과 활용도를 결정하게 되므로,Hashing에서 데이타를 검색하는 시간(retrieval time)이 일정하다는 것은 그만큼 데이터베이스에서 중요한 요소가 된다. 결국 Hashing을 사용함으로써 데이터의 검색 시간을 보장할 수있다는 장점이 있게 되는 것이다. 하지만 이 장점은 디스크 속도와 검색 속도가 최적화 되었을 때에 나타날 수 있는 장점이다. 즉 검색 속도가 아무리 빠른 Hashing을 이용할 지라도 디스크의 검색 속도가 느리다면, Hashing의 장점은 무용지물이 되며, 아무리 좋은 디스크를 가지고 있다 하더라도, Hashing의 검색 속도가 느리게 되면, 이 디스크는 그 가격 만큼의 성능을 발휘하지 못하게 되는 것이다. 따라서 Hashing에서는 디스크 속도와 균형을 이루는 것이중요하다. 이것이 Hashing의 데이타베이스적 접근이다.

앞에서 언급했던 것처럼 Hashing을 데이타베이스에서 사용하는 이유는 검색 시간이 일정하기 때문인데, 이것은 Hashing 알고리즘보다는 그 검색 효율을 더 중시한다는 것을 의미한다.데이타의 속성을 잘 관찰한 다음, 데이타의 변화율이 작고, 검색을 위한 데이타베이스인 경우에는 Hashing이 사용하는 것이 유용하다고 말할 수 있다. 따라서 데이타베이스 관리자(DBA)는 데이타를 분석하고 그 속성을 잘 검토하여, Hashing의 장점을 잘 활용할 수 있는데이타에 한하여 Hashing을 이용하도록 해야 할 것이다.

Hashing을 사용하면 검색 시간이 어느 한도 내에서 보장되므로, 검색 시간이 비용과 직접적으로 연결되는 분야에 이용하도록 해야 한다. 신용 조회, 이동 통신, 카드 결제 등과 같은 실시간 통신은 일정한 검색 시간이 무엇보다도 중요하다. 따라서 이런 분야에서는 실제적으로Hashing을 이용한 데이타베이스로 운용을 해 나가고 있다.

Hashing의 단점은 연속적인 데이터의 검색이 비효율적이다라는 것이므로 연속적인 질문을던지는 데이타베이스에서는 사용하지 않는 것이 현명한 처사이다. 이는 데이타베이스 관리자가 결정할 문제로 데이타를 속성과 질문의 경향을 잘 살펴서, 연속적인 데이터에 대한 응답을요구하는 경향이 많은 데이타베이스인 경우에는 사용하지 않도록 결정을 해야 할 것이다.