성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] VT sequences to "CONOUT$" vs. STD_O...
[정성태] NetCoreDbg is a managed code debugg...
[정성태] Evaluating tail call elimination in...
[정성태] What’s new in System.Text.Json in ....
[정성태] What's new in .NET 9: Cryptography ...
[정성태] 아... 제시해 주신 "https://akrzemi1.wordp...
[정성태] 다시 질문을 정리할 필요가 있을 것 같습니다. 제가 본문에...
[이승준] 완전히 잘못 짚었습니다. 댓글 지우고 싶네요. 검색을 해보...
[정성태] 우선 답글 감사합니다. ^^ 그런데, 사실 저 예제는 (g...
[이승준] 수정이 안되어서... byteArray는 BYTE* 타입입니다...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>괜찮은 문자열 해시 함수?</h1> <p> 오늘 재미있는 글을 하나 읽었습니다. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 컴파일 중에 문자열 해시 만들기....(를 시도해 보자? -_-) ; <a target='tab' href='http://www.gamedevforever.com/50'>http://www.gamedevforever.com/50</a> </pre> <br /> 위의 이야기 중에 보면, x65599 hash 함수 하나를 소개하고 있는데요. 소스 코드가 아래와 같이 실려져 있습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > // 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); } </pre> <br /> 마침, 우리 회사에서도 사용하고 있던 해시 함수가 있었는데 위의 함수에 비하면 무거운 연산을 하기 때문에 전체 메일로 소개를 했더랬지요. ^^<br /> <br /> 그러자, 자체 hash 충돌 코드로 테스트한 결과가 피드백으로 날아왔습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 테스트 문자열 경우의 수: 14,776,336 x65599 hash => <span style='color: blue; font-weight: bold'>해시 충돌=722,750</span> 사내 해시함수 => <span style='color: blue; font-weight: bold'>해시 충돌=0</span> </pre> <br /> 충돌 횟수가 비교될 정도로 많습니다. 여기서 갑자기 오기가 발동한 성태... ^^ 곧바로 x65599 해시 함수 개량에 나섰습니다.<br /> <br /> (*** 이후의 테스트 결과들은 확실한 비교를 위해 문자열 경우의 수를 기존 14,776,336에서 162,539,696으로 늘렸습니다.)<br /> <br /> 자... 이제 차근히 x65599 hash 함수를 보았습니다. 우선... 함수의 마지막 return 문에서 수행한 hash 쉬프트는 그다지 영양가가 없다는 판단이 들었습니다. 실제로 shift 연산을 제거하고 테스트했더니 오히려 충돌 횟수가 줄어드는 결과값이 나왔습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > x65599 hash 걸린 시간: 61,374 ms, collisions = 35,374,354 (21%) shift 제거한 hash 걸린 시간: 50,091 ms, collisions = 20,820,228 (12%) </pre> <br /> 충돌 수도 줄고, 속도도 빨라졌으니 x65599 hash는 일단 다음과 같이 바뀌는 것이 좋겠습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > int hash = 0; int len = chars.Length; for (int i = 0; i < len; ++i) { hash = 65599 * hash + (int)chars[i]; } return hash; </pre> <br /> 약간 나아지긴 했지만, 여전히 충돌 횟수가 걸립니다. 좀 더 개선할 수는 없을까요? 가만 보니까 사용된 소수(Prime number)값 - 65599가 마음에 안 듭니다. 구하려는 해시 값 자체가 전체 4byte인데 겨우 2 바이트 정도에 해당하는 65,599 값만을 쓴다는 것이 왠지 충돌의 원인이 아닐까 싶어서 <a target='tab' href='http://en.wikipedia.org/wiki/Cyclic_redundancy_check'>CRC32 알고리즘에서 사용되는 값의 하나인 0xEDB88320</a> 수로 대체를 해보았습니다. 다행히, 테스트 결과 ... 충돌 횟수가 어느 정도는 줄었습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 0xEDB88320 hash 걸린 시간: 53,705 ms, collisions = 2,633,400 (1.62%) </pre> <br /> 근데... 과연 0xEDB88320 값이 올바른 선택일까요? 짝수라는 것이 왠지 좀 그래서, <a target='tab' href='http://en.wikipedia.org/wiki/Cyclic_redundancy_check'>또 다른 CRC32 값 중에서 홀수인 0x741B8CD7</a> 값과 혹시나 싶어서 그 값보다 큰 수 중에서 소수를 찾아 (0x741b8cf1) 다시 한번 테스트를 돌려보았습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > <span style='color: blue; font-weight: bold'>또 다른 CRC32 0x741B8CD7 hash</span> 걸린 시간: 55,080 ms, collisions = <span style='color: blue; font-weight: bold'>131,040 (0.08%)</span> <span style='color: blue; font-weight: bold'>소수 0x741b8cf1 hash</span> 걸린 시간: 58,075 ms, collisions = 3,926,600 (2.42%) </pre> <br /> 오호... 결과를 보니, 소수라고 해서 항상 정답은 아닌 것 같습니다. ^^ 그러고 보면, CRC-32에서 사용되는 값이 괜히 채택된 것은 아닌 것 같습니다.<br /> <br /> 개인적으로 여기서 만족할 수 없더군요. 좀 더 값을 분산시켜 볼 수 있지 않을까 싶어서 bit 연산을 생각했습니다. 위에서 테스트 했던 16진수 값을 대상으로 각각 테스트를 해보았는데요. 결과는 의외로 0xEDB88320의 승리였습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 0xEDB88320 + 1bit Left Shift 걸린 시간: 56,407 ms, collisions = <span style='color: blue; font-weight: bold'>4,500 (0.0028%)</span> 0x741B8CD7 + 1bit Left Shift 걸린 시간: 54,360 ms, collisions = 240,065 (0.148%) 0x741b8cf1 + 1bit Left Shift 걸린 시간: 54,906 ms, collisions = 381,888 (0.235%) </pre> <br /> 여기까지 하고... 다시 회사에서 사용하던 CRC32 알고리즘과 충돌 횟수를 비교해 보았습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 사내 해시함수 걸린 시간: 135,649 ms, collisions = 1,265,312 (0.778%) </pre> <br /> 오호~~~ 압도적으로 "0xEDB88320 + 1bit Shift" 연산이 승리를 했군요. 그래서 최종적으로 제가 만든 해시 코드는 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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; } </pre> <br /> <hr style='width: 50%' /><br /> <br /> 참고로, 테스트를 위한 문자열 생성에 사용된 함수는 다음과 같습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 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++) { <span style='color: blue; font-weight: bold'> if (c5 > 10) { break; }</span> 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); </pre> <br /> 위에서 보면, 마지막 c5 변수의 값을 10 이하로 제한했는데요. 왜냐하면, 메모리가 너무 많이 소비되어서 그런 조치를 취한 것입니다. 10으로만 해도 테스트를 위해 5GB 가까운 메모리를 소비하기 때문에 어쩔 수 없이 제약을 두었습니다.<br /> <br /> 메모리 소비로 인해, 당연히 x86 환경에서는 테스트 할 수 없고 Hash 값을 보관하기 위한 자료구조도 C#의 것이 아닌 C++/CLI를 통해 CAtlMap을 가져다 써야만 했습니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > .NET 64비트 응용 프로그램에서 왜 (2GB) OutOfMemoryException 예외가 발생할까? ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/946'>http://www.sysnet.pe.kr/2/0/946</a> </pre> <br /> 여러분들도 <a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=681&boardid=331301885'>테스트를 직접 해볼 수 있도록, 위의 것들을 테스트 하는 데 사용한 코드를 첨부</a>했습니다.<br /> <br /> 마지막으로, 위와 같이 결과가 나왔다고 해서 제가 공개한 해시 함수가 제일 좋을 것이다라는 판단을 하시면 안됩니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Dictionary.Get(A) 대신 Dictionary.Get(A.GetHashCode())를 사용해서는 안되는 이유 ; <a target='tab' href='http://www.sysnet.pe.kr/2/0/889'>http://www.sysnet.pe.kr/2/0/889</a> </pre> <br /> 해시 함수는, 결국 해당 '업무 도메인'에서 사용되는 문자열 셋이 다르기 때문에 (가능하다면) 그에 따른 적절한 테스트를 해보고 선택하시는 것이 좋습니다.<br /> </p><br /> <br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
2139
(왼쪽의 숫자를 입력해야 합니다.)