성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] Working with Rust Libraries from C#...
[정성태] Detecting blocking calls using asyn...
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
[정성태] "props[i].GetValue(props[i])" 코드에서 ...
[정성태] 저렇게 조각 코드 말고, 실제로 재현이 되는 예제 프로젝트를 압...
[정성태] Modules 창(Ctrl+Shift+U)을 띄워서, 해당 Op...
글쓰기
제목
이름
암호
전자우편
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.sysnet.pe.kr/2/0/1222'>http://www.sysnet.pe.kr/2/0/1222</a> </pre> <br /> 아무래도 무작위 문자열을 고르는 것이 테스트의 신뢰도를 떨어뜨리는 것 같고, 저 역시 좀 더 현실적인 테스트가 있으면 좋지 않을까 생각해서 이번엔 문제를 좀 골라봤습니다.<br /> <br /> 파일을 4개를 만들었는데요.<br /> <br /> <ul> <li>영문 성경 텍스트 파일 (http://ebible.org/web/index.htm)</li> <li>한글 성경 텍스트 파일 (http://jwch.net/bbs/board.php?bo_table=util&wr_id=30)</li> <li>C# 소스 코드 파일 (<a target='tab' href='http://1code.codeplex.com/'>All-In-One Code Framework</a>의 소스 파일)</li> <li>크롬 소스 코드 파일 중에서 50MB 분량만 취합</li> </ul> <br /> 정말 x65599 해시의 경우 '영문 성격 텍스트 파일'의 경우에 아무런 충돌도 없었습니다. 하지만... 완벽한 해시가 어디있겠습니까? ^^ '한글 성경'에서는 충돌이 발생하더군요.<br /> <br /> 암튼... 테스트는 5가지 해시 방식에 대해서 진행했습니다.<br /> <br /> <ul> <li>x65599: <a target='tab' href='http://www.gamedevforever.com/50 '>http://www.gamedevforever.com/50 </a>글에서 가져온 해시 코드</li> <li>x65599 (마지막 shift 제거): "x65599" 코드 중에서 마지막 return 문에서 hash 값을 그대로 반환하도록 수정</li> <li>0xEDB88320: <a target='tab' href='http://www.sysnet.pe.kr/2/0/1222'>지난번 글에서 소개한 0xEDB88320</a></li> <li>0xEDB8832F: 0xEDB88320의 값에 '0x0F'를 더한 숫자를 사용</li> <li>.NET 4.0 GetHashCode: .NET 4.0의 string 타입에서 기본 제공되는 GetHashCode 사용</li> </ul> <br /> 텍스트 파일이 사실 크기만 컸지, 고유 단어수를 계산해 보면 375,719 밖에 되지 않았기에 '현실(?)'을 많이 반영한 것 같지는 않지만 테스트를 아니한 것보다는 나으므로 ^^ 그냥 진행을 했습니다.<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;' > 전체 워드 수: 375,719 x65599: * 걸린 시간 9,573 ms * 충돌: 39 (0.0104 %) x65599 (마지막 shift 제거): * 걸린 시간 9,309 ms * 충돌: 22 (0.0059 %) <span style='color: blue; font-weight: bold'>0xEDB88320: * 걸린 시간 9,897 ms * 충돌 81,139 (21.5957%)</span> <span style='color: blue; font-weight: bold'>0xEDB8832F: * 걸린 시간 9,442 ms * 충돌 16 (0.0043%)</span> .NET 4.0 GetHashCode: * 걸린 시간 9,546 ms * 충돌 34 (0.0090%) </pre> <br /> 재미있는 결과가 나왔습니다.<br /> <br /> <ul> <li>지난번의 무작위 테스트를 훌륭하게 통과한 0xEDB88320 값이 이번에는 20%가 넘는 충돌을 보임.</li> <li>x65599는 여전히 shift 구문을 제거한 반환문이 더 빠르고 충돌도 낮음.</li> </ul> <br /> 0xEDB88320 값이 저를 실망시키는군요. ^^; 오히려, 별다른 기대 없이 0xF 값을 더한 0xEDB8832F 숫자를 이용한 해시가 좋은 결과를 보여주고 있습니다. (이래서... 해시 코드는 해당 업무 도메인에 대한 문자열 셋으로 테스트가 필요한 것입니다. ^^)<br /> <br /> 그렇다면, 여기서 1등을 한 "0xEDB8832F"와 "shift 없는 x65599"에 대해서 지난번 글의 무작위 문자열 테스트 결과를 비교해 보면 어떨까요?<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 총 단어수 162,539,696 shift 제거한 hash * 걸린 시간 50,091 ms * 충돌 20,820,228 <span style='color: blue; font-weight: bold'>(12%)</span> 0xEDB8832F: * 걸린 시간 53,372 ms * 충돌 2,807,510 <span style='color: blue; font-weight: bold'>(1.73%)</span> </pre> <br /> 비록 0xEDB8832F 해시 함수가 0xEDB88320에 비해서 충돌이 더 발생하긴 했지만, '텍스트 파일' 실험의 결과와 종합해 보면 더욱 우수하기 때문에 용서가 됩니다.<br /> <br /> 아래는 이렇게 해서 최종적으로 만들어진 0xEDB88320 해시 함수입니다. <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 hash4(string word) { uint hash = 0; int len = word.Length; int ch = 0; unchecked { uint poly = 0xEDB8832F; for (int i = 0; i < len; i++) { hash = (hash << 1) | (hash >> (32 - 1)); ch = word[i]; hash = (uint)(poly * hash + ch); } } return (int)hash; } </pre> <br /> 역시 이번에도 <a target='tab' href='http://www.sysnet.pe.kr/bbs/DownloadAttachment.aspx?fid=682&boardid=331301885'>여러분이 테스트를 할 수 있도록 소스 코드와 데이터 파일을 첨부</a>했습니다.<br /> </p><br /> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
1076
(왼쪽의 숫자를 입력해야 합니다.)