Microsoft MVP성태의 닷넷 이야기
.NET Framework: 295. 괜찮은 문자열 해시 함수? [링크 복사], [링크+제목 복사],
조회: 31517
글쓴 사람
정성태 (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)
12414정성태11/18/202014652VC++: 138. x64 빌드에서 extern "C"가 아닌 경우 ___cdecl name mangling 적용 [4]파일 다운로드1
12413정성태11/17/202014047.NET Framework: 970. .NET 5 / .NET Core - UnmanagedCallersOnly 특성을 사용한 함수 내보내기파일 다운로드1
12412정성태11/16/202016365.NET Framework: 969. .NET Framework 및 .NET 5 - UnmanagedCallersOnly 특성 사용파일 다운로드1
12411정성태11/12/202013423오류 유형: 680. C# 9.0 - Error CS8889 The target runtime doesn't support extensible or runtime-environment default calling conventions.
12410정성태11/12/202012985디버깅 기술: 174. windbg - System.TypeLoadException 예외 분석 사례
12409정성태11/12/202014552.NET Framework: 968. C# 9.0의 Function pointer를 이용한 함수 주소 구하는 방법파일 다운로드1
12408정성태11/9/202029051도서: 시작하세요! C# 9.0 프로그래밍 [8]
12407정성태11/9/202015122.NET Framework: 967. "clr!JIT_DbgIsJustMyCode" 호출이 뭘까요?
12406정성태11/8/202016450.NET Framework: 966. C# 9.0 - (15) 최상위 문(Top-level statements) [5]파일 다운로드1
12405정성태11/8/202013753.NET Framework: 965. C# 9.0 - (14) 부분 메서드에 대한 새로운 기능(New features for partial methods)파일 다운로드1
12404정성태11/7/202014503.NET Framework: 964. C# 9.0 - (13) 모듈 이니셜라이저(Module initializers)파일 다운로드1
12403정성태11/7/202014510.NET Framework: 963. C# 9.0 - (12) foreach 루프에 대한 GetEnumerator 확장 메서드 지원(Extension GetEnumerator)파일 다운로드1
12402정성태11/7/202014897.NET Framework: 962. C# 9.0 - (11) 공변 반환 형식(Covariant return types) [1]파일 다운로드1
12401정성태11/5/202014154VS.NET IDE: 153. 닷넷 응용 프로그램에서의 "My Code" 범위와 "Enable Just My Code"의 역할 [1]
12400정성태11/5/202010641오류 유형: 679. Visual Studio - "Source Not Found" 창에 "Decompile source code" 링크가 없는 경우
12399정성태11/5/202014526.NET Framework: 961. C# 9.0 - (10) 대상으로 형식화된 조건식(Target-typed conditional expressions)파일 다운로드1
12398정성태11/4/202013264오류 유형: 678. Windows Server 2008 R2 환경에서 Powershell을 psexec로 원격 실행할 때 hang이 발생하는 문제
12397정성태11/4/202013410.NET Framework: 960. C# - 조건 연산자(?:)를 사용하는 경우 달라지는 메서드 선택 사례파일 다운로드1
12396정성태11/3/202011149VS.NET IDE: 152. Visual Studio - "Tools" / "External Tools..."에 등록된 외부 명령어에 대한 단축키 설정 방법
12395정성태11/3/202013019오류 유형: 677. SSMS로 DB 접근 시 The server principal "..." is not able to access the database "..." under the current security context.
12394정성태11/3/202010952오류 유형: 676. cacls - The Recycle Bin on ... is corrupted. Do you want to empty the Recycle Bin for this drive?
12393정성태11/3/202011535오류 유형: 675. Visual Studio - 닷넷 응용 프로그램 디버깅 시 Disassembly 창에서 BP 설정할 때 "Error while processing breakpoint." 오류
12392정성태11/2/202015944.NET Framework: 959. C# 9.0 - (9) 레코드(Records) [4]파일 다운로드1
12390정성태11/1/202014695디버깅 기술: 173. windbg - System.Configuration.ConfigurationErrorsException 예외 분석 방법
12389정성태11/1/202013859.NET Framework: 958. C# 9.0 - (8) 정적 익명 함수 (static anonymous functions)파일 다운로드1
12388정성태10/29/202013563오류 유형: 674. 어느 순간부터 닷넷 응용 프로그램 실행 시 System.Configuration.ConfigurationErrorsException 예외가 발생한다면?
... 46  47  48  49  50  51  52  53  54  55  [56]  57  58  59  60  ...