Microsoft MVP성태의 닷넷 이야기
.NET Framework: 295. 괜찮은 문자열 해시 함수? [링크 복사], [링크+제목 복사],
조회: 31518
글쓴 사람
정성태 (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)
12639정성태5/12/202112386오류 유형: 715. Arduino: Open Serial Monitor - The module '...\detection.node' was compiled against a different Node.js version using NODE_MODULE_VERSION
12638정성태5/12/202113521사물인터넷: 63. NodeMCU v1 ESP8266 - 펌웨어 내 파일 시스템(SPIFFS, LittleFS) 및 EEPROM 활용
12637정성태5/10/202113025사물인터넷: 62. NodeMCU v1 ESP8266 보드의 A0 핀에 다중 아날로그 센서 연결 [1]
12636정성태5/10/202113216사물인터넷: 61. NodeMCU v1 ESP8266 보드의 A0 핀 사용법 - FSR-402 아날로그 압력 센서 연동파일 다운로드1
12635정성태5/9/202112256기타: 81. OpenTabletDriver를 (관리자 권한으로 실행하지 않고도) 관리자 권한의 프로그램에서 동작하게 만드는 방법
12634정성태5/9/202111046개발 환경 구성: 572. .NET에서의 신뢰도 등급 조정 - 외부 Manifest 파일을 두는 방법파일 다운로드1
12633정성태5/7/202113146개발 환경 구성: 571. UAC - 관리자 권한 없이 UIPI 제약을 없애는 방법
12632정성태5/7/202114102기타: 80. (WACOM도 지원하는) Tablet 공통 디바이스 드라이버 - OpenTabletDriver
12631정성태5/5/202113239사물인터넷: 60. ThingSpeak 사물인터넷 플랫폼에 ESP8266 NodeMCU v1 + 조도 센서 장비 연동파일 다운로드1
12630정성태5/5/202113626사물인터넷: 59. NodeMCU v1 ESP8266 보드의 A0 핀 사용법 - CdS Cell(GL3526) 조도 센서 연동파일 다운로드1
12629정성태5/5/202115469.NET Framework: 1057. C# - CoAP 서버 및 클라이언트 제작 (UDP 소켓 통신) [1]파일 다운로드1
12628정성태5/4/202113289Linux: 39. Eclipse 원격 디버깅 - Cannot run program "gdb": Launching failed
12627정성태5/4/202113914Linux: 38. 라즈베리 파이 제로 용 프로그램 개발을 위한 Eclipse C/C++ 윈도우 환경 설정
12626정성태5/3/202113937.NET Framework: 1056. C# - Thread.Suspend 호출 시 응용 프로그램 hang 현상 (2)파일 다운로드1
12625정성태5/3/202112732오류 유형: 714. error CS5001: Program does not contain a static 'Main' method suitable for an entry point
12624정성태5/2/202117030.NET Framework: 1055. C# - struct/class가 스택/힙에 할당되는 사례 정리 [10]파일 다운로드1
12623정성태5/2/202113238.NET Framework: 1054. C# 9 최상위 문에 STAThread 사용 [1]파일 다운로드1
12622정성태5/2/20219572오류 유형: 713. XSD 파일을 포함한 프로젝트 - The type or namespace name 'TypedTableBase<>' does not exist in the namespace 'System.Data'
12621정성태5/1/202114177.NET Framework: 1053. C# - 특정 레지스트리 변경 시 알림을 받는 방법 [1]파일 다운로드1
12620정성태4/29/202116329.NET Framework: 1052. C# - 왜 구조체는 16 바이트의 크기가 적합한가? [1]파일 다운로드1
12619정성태4/28/202116364.NET Framework: 1051. C# - 구조체의 크기가 16바이트가 넘어가면 힙에 할당된다? [2]파일 다운로드1
12618정성태4/27/202114850사물인터넷: 58. NodeMCU v1 ESP8266 CP2102 Module을 이용한 WiFi UDP 통신 [1]파일 다운로드1
12617정성태4/26/202112656.NET Framework: 1050. C# - ETW EventListener의 Keywords별 EventId에 따른 필터링 방법파일 다운로드1
12616정성태4/26/202112504.NET Framework: 1049. C# - ETW EventListener를 상속받았을 때 초기화 순서파일 다운로드1
12615정성태4/26/20219951오류 유형: 712. Microsoft Live 로그인 - 계정을 선택하는(Pick an account) 화면에서 진행이 안 되는 문제
12614정성태4/24/202113408개발 환경 구성: 570. C# - Azure AD 인증을 지원하는 ASP.NET Core/5+ 웹 애플리케이션 예제 구성 [4]파일 다운로드1
... 46  [47]  48  49  50  51  52  53  54  55  56  57  58  59  60  ...