JaPa2

작성:http://ospace.tistory.com/(ospace114@empal.com) 2012.01.09

들어가기

개발하다보면 hash라를 말을 자주 들어본다. 그리고 hash 함수를 만들어보기도 한다. 그냥 배껴서 만들기보다는 hash가 왜 필요한지, 어떻게 만들어지는지 간단하게 알아보면 좀더 잘 사용할 수 있을 거라 생각한다. 본인도 기억이 가물가물해져서 좀더 정확히 집고넘어가고자 이번 기회에 내용을 간단하게 정리하려고 한다.

Hash란

Hash의 목적은 긴 데이터를 짧은 값으로 변환한 것을 말한다. 짧은 값을 인덱스로 사용하여 관리하면 긴 데이터 검색하는 것 보다 더 짧은 시간에 데이터를 검색할 수 있을 것이다.  특히 값을 주소와 연계된다면 검색 시간은 상수값이 된다. 그러면 검색 처리하는 시간이 엄청나게 줄어드는 것은 자명한 일이다. 즉 데이터 10바이트 비교하는 것 보다 4바이트 비교하는게 빠른 것은 당연하다.

그러나 실제 Hash가 인덱스처럼만 사용하는게 아니라 에러 검출이나 암호화에서도 사용된다.

Hash 함수

그럼 Hash을 어떻게 만들까? Hash을 만드는 것은 Hash  함수에 의해서 생성된다. 즉, Hash 함수가 hash을 생성한다.

Hash함수에서 중요한 것은 다음 3가지이다.

• 공간 밀도
• 분포도
• 시간

앞에서 간 데이터를 짧은 데이터로 변경되었으니 데이터 범위가 줄어드는 것은 당연하다.

예를 들어 알파벳 4개를 조합해서 생성할수 있는 경우의 수는 45만개 이상이 된다. 이를 고려하기 위해 알파벳 4번을 비교하는 것을 hash로 만들경우 한번의 비교로 원하는 경우로 변경할 수 있다. 그러면 많은 시간이 절약될 것 이다. 이때 hash의 크기가 중요하다. short형(2byte)인 숫자로 변경된다면 unsigned형으로 최대 약 6만개 정도  지정 가능하다. 비율로 나타내면 약 0.13 정도 된다. 이를 공간 밀도 혹은 패킹 밀도라고 한다. 이 경우는 밀도가 너무 높은 경우이므로 10개 이상을 담기 시작하면 1개 정도 충돌이 발생한다는 의미이다. 자신의 데이터 분포를 잘 고려해서 적당한 밀도를 선택하는게 중요하다.

Hash함수는 넓은 분포도를 가져야 한다. Hash가 생성되어도 한쪽으로 값이 치우치게 된다면 금방 충돌이 발생하여 효율성이 떨어지게 될 것이다. 이 것 역시 데이터 특성을 고려해야 한다.

또한 Hash을 생성함에 있어서 중요한 것이 생성 시간이다. 한번 생성할 때마다 오래 걸린다면, 처리 성능 향상을 위한 목적이 유명무실하게 된다.

Hash 함수 생성 방법

생성 방법은 아래와 같은 것이 있다.

• Division
• Mid-Squre
• Digit Analysis
• Folding
• Radix Exchange
• Pseudo Random

Division

나머지 연산자(%)을 사용하여 나머지 값을 사용하는 방식.

아주 간단하지만 잘못된 값 선택시 충돌 발생 가능성이 매우 높음.

일반적으로 소수를 사용함.

Mid Square

값을 제곱하여(square) 중간에 임의 값을(mid) 주소로 사용.

값이 조금만 틀려도 다른 값을 가질 확률이 높다.

Digit Analysis

데이터를 분석하여 고른 분포를 가지는 데이터 영역들을 선택하여 사용.

Folding

긴 데이터를 일정 크기로 나눠서 값을 더하거나 XOR한 값을 주소로 사용.

앞에서 차례로 더하는 경우 Shift Folding이라고 하고, 처음 값을 그대로 다음 값은 역 순으로, 다시 다음은 값 그대로 사용하여 더하는 방식을 Boundary Folding이라고 한다.

• ABCDEFGHIJKL인 경우

  • Shilf Folding: ABC + DEF + GHI + JKL
  • Boundary Folding: ABC + FED + GHI + LKJ

Radix Exchange

진법을 변환하거나 임의 진법이라 간주하여 변환된 값을 키로 사용.

Pseudo Random

임의 랜덤값을 사용

기타사항

Windows의 MFC 메시지 맵에서 사용한 Hash 함수

unsigned int hash = (pMessageMap ^ messageId) & (512-1)

이 방식은 Folding형태라고 볼 수 있다. 메시지 맵와 메시지 아이디를 이용하여 해쉬를 구함. 해시 범위는 총 512개이다. 즉 같은 메시지 아이디라고 해도 메시지 맵에 따라 달라지기 때문에 메시지 맵 변경으로 해쉬가 변경된다. 뒤에 (512-1)은 Division형태라고 볼 수 있지만, 여기서는 맵 크기에 따라서 달라지는 값이기에 소수를 사용하는 것은 아니다.

참고

[1] http://internet512.chonbuk.ac.kr/datastructure/hash/hash1.htm

[2] http://blog.bagesoft.com/876

[3] http://www.codesos.com/book/algori/hash/hash.html

이 글은 스프링노트에서 작성되었습니다.