Microsoft MVP성태의 닷넷 이야기
.NET Framework: 295. 괜찮은 문자열 해시 함수? [링크 복사], [링크+제목 복사],
조회: 28976
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 3개 있습니다.)

괜찮은 문자열 해시 함수?

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

컴파일 중에 문자열 해시 만들기....(를 시도해 보자? -_-)
; 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 예외가 발생할까?
; https://www.sysnet.pe.kr/2/0/946

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

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

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

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





[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 7/9/2021]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 



2012-01-20 12시26분
괜찮은 문자열 해시 함수? - 두 번째 이야기
; http://www.sysnet.pe.kr/2/0/1223
정성태
2015-08-18 07시27분
[백곰] 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;
}
코드를 보면 초기 hash값이 0이기 때문에 처음에는 poly값을 활용하지 못하고 chars[0]값이 그대로 들어오게 되어 있는데 의도인가요?
[guest]
2015-08-18 01시01분
글쎄요. 저도 알 수 없군요. 그 부분의 정확한 답은 x65599 원 저작자에게 물어봐야 할 것 같습니다. 단지 추정을 해보자면, 의도라고 봐도 좋을 것 같습니다. 한 글자 내에서는 정확히 hash가 충돌 없이 나오므로 굳이 첫 글자에 poly 값을 적용할 필요는 없을 테니까요. ^^
정성태
2017-08-08 08시55분
[cok2529] 잘 보고 갑니다 !
[guest]

... 46  47  48  49  50  51  [52]  53  54  55  56  57  58  59  60  ...
NoWriterDateCnt.TitleFile(s)
12355정성태10/3/20208355오류 유형: 661. Hyper-V Linux VM의 Internal 유형의 가상 Switch에 대한 IP 연결이 되지 않는 경우
12354정성태10/2/202021300오류 유형: 660. Web Deploy (msdeploy.axd) 실행 시 오류 기록 [1]
12353정성태10/2/202011075개발 환경 구성: 518. 비주얼 스튜디오에서 IIS 웹 서버로 "Web Deploy"를 이용해 배포하는 방법
12352정성태10/2/202011636개발 환경 구성: 517. Hyper-V Internal 네트워크에 NAT을 이용한 인터넷 연결 제공
12351정성태10/2/202011137오류 유형: 659. Nox 실행이 안 되는 경우 - Unable to bind to the underlying transport for ...
12350정성태9/25/202014634Windows: 175. 윈도우 환경에서 클라이언트 소켓의 최대 접속 수 [2]파일 다운로드1
12349정성태9/25/20209451Linux: 32. Ubuntu 20.04 - docker를 위한 tcp 바인딩 추가
12348정성태9/25/202010203오류 유형: 658. 리눅스 docker - Got permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock
12347정성태9/25/202024550Windows: 174. WSL 2의 네트워크 통신 방법 [4]
12346정성태9/25/20209494오류 유형: 657. IIS - http://localhost 방문 시 Service Unavailable 503 오류 발생
12345정성태9/25/20209120오류 유형: 656. iisreset 실행 시 "Restart attempt failed." 오류가 발생하지만 웹 서비스는 정상적인 경우파일 다운로드1
12344정성태9/25/202010335Windows: 173. 서비스 관리자에 "IIS Admin Service"가 등록되어 있지 않다면?
12343정성태9/24/202020120.NET Framework: 945. C# - 닷넷 응용 프로그램에서 메모리 누수가 발생할 수 있는 패턴 [5]
12342정성태9/24/202011301디버깅 기술: 171. windbg - 인스턴스가 살아 있어 메모리 누수가 발생하고 있는지 확인하는 방법
12341정성태9/23/202010316.NET Framework: 944. C# - 인스턴스가 살아 있어 메모리 누수가 발생하고 있는지 확인하는 방법파일 다운로드1
12340정성태9/23/202010067.NET Framework: 943. WPF - WindowsFormsHost를 담은 윈도우 생성 시 메모리 누수
12339정성태9/21/202010170오류 유형: 655. 코어 모드의 윈도우는 GUI 모드의 윈도우로 교체가 안 됩니다.
12338정성태9/21/20209644오류 유형: 654. 우분투 설치 시 "CHS: Error 2001 reading sector ..." 오류 발생
12337정성태9/21/202011035오류 유형: 653. Windows - Time zone 설정을 바꿔도 반영이 안 되는 경우
12336정성태9/21/202013513.NET Framework: 942. C# - WOL(Wake On Lan) 구현
12335정성태9/21/202022886Linux: 31. 우분투 20.04 초기 설정 - 고정 IP 및 SSH 설치
12334정성태9/21/20208250오류 유형: 652. windbg - !py 확장 명령어 실행 시 "failed to find python interpreter"
12333정성태9/20/20208605.NET Framework: 941. C# - 전위/후위 증감 연산자에 대한 오버로딩 구현 (2)
12332정성태9/18/202010783.NET Framework: 940. C# - Windows Forms ListView와 DataGridView의 예제 코드파일 다운로드1
12331정성태9/18/20209929오류 유형: 651. repadmin /syncall - 0x80090322 The target principal name is incorrect.
12330정성태9/18/202010968.NET Framework: 939. C# - 전위/후위 증감 연산자에 대한 오버로딩 구현 [2]파일 다운로드1
... 46  47  48  49  50  51  [52]  53  54  55  56  57  58  59  60  ...