해쉬함수

http://goo.gl/24Dq3

괜찮은 문자열 해쉬함수?

오늘 재미있는 글을 하나 읽었습니다. ^^

컴파일 중에 문자열해쉬 만들기....(를 시도해 보자? -_-)
; http://www.gamedevforever.com/50

위의 이야기 중에 보면, x65599 hash 함수 하나를 소개하고 있는데요. 소스 코드가 아래와 같이 실려져 있습니다.

// 65599를 곱하는 해쉬함수. (Red Dragon 책에서 훔쳐옴 -0-)
unsigned int generateHash(const char *string, size_t len)
{
  unsigned int hash = 0;
  for(size_t i = 0; i < len; ++i)
  {
     hash = 65599 * hash + string[i];
  }
  return hash ^ (hash >> 16);
}

마침, 우리 회사에서도 사용하고 있던 해쉬 함수가 있었는데 위의 함수에 비하면 무거운 연산을 하기 때문에 전체 메일로 소개를 했더랬지요. ^^

그러자, 자체 hash 충돌 코드로 테스트한 결과가 피드백으로 날아왔습니다.

테스트 문자열 경우의 수: 14,776,336

x65599 hash  => 해쉬 충돌=722,750
사내 해쉬함수 => 해쉬 충돌=0

충돌 횟수가 비교될 정도로 많습니다. 여기서 갑자기 오기가 발동한 성태... ^^ 곧바로 x65599 해쉬함수 개량에 나섰습니다.

(*** 이후의 테스트 결과들은 확실한 비교를 위해 문자열 경우의 수를 기존 14,776,336 에서 162,539,696 으로 늘렸습니다.)

자... 이제 차근히 x65599 hash 함수를 보았습니다. 우선... 함수의 마지막 return 문에서 수행한 hash 쉬프트는 그다지 영양가가 없다는 판단이 들었습니다. 실제로 shift 연산을 제거하고 테스트했더니 오히려 충돌 횟수가 줄어드는 결과값이 나왔습니다.

x65599 hash
걸린 시간: 61,374 ms, collisions = 35,374,354 (21%)

shift 제거한 hash
걸린 시간: 50,091 ms, collisions = 20,820,228 (12%)

충돌 수도 줄고, 속도도 빨라졌으니 x65599 hash는 일단 다음과 같이 바뀌는 것이 좋겠습니다.

int hash = 0;
int len = chars.Length;
for (int i = 0; i < len; ++i)
{
    hash = 65599 * hash + (int)chars[i];
}

return hash;

약간 나아지긴 했지만, 여전히 충돌 횟수가 걸립니다. 좀더 개선할 수는 없을까요? 가만 보니까 사용된 소수(Prime number)값 - 65599 가 마음에 안 듭니다. 구하려는 해쉬 값 자체가 전체 4byte 인데 겨우 2 바이트 정도에 해당하는 65,599 값만을 쓴다는 것이 왠지 충돌의 원인이 아닐까 싶어서 CRC32 알고리즘에서 사용되는 값의 하나인 0xEDB88320 수로 대체를 해보았습니다. 다행히, 테스트 결과 ... 충돌 횟수가 어느 정도는 줄었습니다.

0xEDB88320 hash
걸린 시간: 53,705 ms, collisions = 2,633,400 (1.62%)

근데... 과연 0xEDB88320 값이 올바른 선택일까요? 짝수라는 것이 왠지 좀 그래서, 또 다른 CRC32 값 중에서 홀수인 0x741B8CD7 값과 혹시나 싶어서 그 값보다 큰 수 중에서 소수를 찾아 (0x741b8cf1) 다시 한번 테스트를 돌려보았습니다.

또 다른 CRC32 0x741B8CD7 hash
걸린 시간: 55,080 ms, collisions = 131,040 (0.08%)

소수 0x741b8cf1 hash
걸린 시간: 58,075 ms, collisions = 3,926,600  (2.42%)

오호... 결과를 보니, 소수라고 해서 항상 정답은 아닌 것 같습니다. ^^ 그러고 보면, CRC-32 에서 사용되는 값이 괜히 채택된 것은 아닌 것 같습니다.

개인적으로 여기서 만족할 수 없더군요. 좀더 값을 분산시켜 볼 수 있지 않을까 싶어서 bit 연산을 생각했습니다. 위에서 테스트 했던 16진수 값을 대상으로 각각 테스트를 해보았는데요. 결과는 의외로 0xEDB88320 의 승리였습니다.

0xEDB88320 + 1bit Left Shift
걸린 시간: 56,407 ms, collisions = 4,500 (0.0028%)

0x741B8CD7 + 1bit Left Shift
걸린 시간: 54,360 ms, collisions = 240,065 (0.148%)

0x741b8cf1 + 1bit Left Shift
걸린 시간: 54,906 ms, collisions = 381,888 (0.235%)

여기까지 하고... 다시 회사에서 사용하던 CRC32 알고리즘과 충돌 횟수를 비교해 보았습니다.

사내 해쉬함수
걸린 시간: 135,649 ms, collisions = 1,265,312 (0.778%)

오호~~~ 압도적으로 "0xEDB88320 + 1bit Shift" 연산이 승리를 했군요. 그래서 최종적으로 제가 만든 해쉬 코드는 다음과 같습니다.

static int hash(char[] chars)
{
    int hash = 0;
    int len = chars.Length;

    unchecked
    {
        uint poly = 0xEDB88320;
        for (int i = 0; i < len; i++)
        {
            poly = (poly << 1) | (poly >> (32 - 1)); // 1bit Left Shift
            hash = (int)(poly * hash + chars[i]);
        }
    }

    return hash;
}

---

참고로, 테스트를 위한 문자열 생성에 사용된 함수는 다음과 같습니다.

TestHashLib.TestHash hashTable2 = new TestHashLib.TestHash();
x = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

char[] xx = x.ToCharArray();
int tot = 0, dup = 0;
for (int c1 = 0; c1 < x.Length; c1++)
{
    for (int c2 = 0; c2 < x.Length; c2++)
    {
        for (int c3 = 0; c3 < x.Length; c3++)
        {
            for (int c4 = 0; c4 < x.Length; c4++)
            {
                for (int c5 = 0; c5 < x.Length; c5++)
                {
                    if (c5 > 10)
                    {
                        break;
                    }
                    char[] c = new char[] { xx[c1], xx[c2], xx[c3], xx[c4], xx[c5] };
                    int hash = hashFunction(c);
                    tot++;
                    if (hashTable2.containsKey(hash))
                    {
                        dup++;
                    }
                    else
                    {
                        hashTable2.put(hash);
                    }
                    c = null;
                }
            }
        }
    }
}

Console.WriteLine("Total: " + tot + ", time: " + st.ElapsedMilliseconds + ", collisions = " + dup);

위에서 보면, 마지막 c5 변수의 값을 10 이하로 제한했는데요. 왜냐하면, 메모리가 너무 많이 소비되어서 그런 조치를 취한 것입니다. 10으로만 해도 테스트를 위해 5GB 가까운 메모리를 소비하기 때문에 어쩔 수 없이 제약을 두었습니다.

메모리 소비로 인해, 당연히 x86 환경에서는 테스트 할 수 없고 Hash 값을 보관하기 위한 자료구조도 C# 의 것이 아닌 C++/CLI를 통해 CAtlMap 을 가져다 써야만 했습니다.

.NET 64비트 응용 프로그램에서 왜 (2GB) OutOfMemoryException 예외가 발생할까?
; http://www.sysnet.pe.kr/2/0/946

여러분들도 테스트를 직접 해볼 수 있도록, 위의 것들을 테스트 하는 데 사용한 코드를 첨부했습니다.

마지막으로, 위와 같이 결과가 나왔다고 해서 제가 공개한 해쉬 함수가 제일 좋을 것이다라는 판단을 하시면 안됩니다.

Dictionary.Get(A) 대신 Dictionary.Get(A.GetHashCode()) 를 사용해서는 안되는 이유
; http://www.sysnet.pe.kr/2/0/889

해쉬 함수는, 결국 해당 '업무 도메인'에서 사용되는 문자열 셋이 다르기 때문에 (가능하다면) 그에 따른 적절한 테스트를 해보고 선택하시는 것이 좋습니다.