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

괜찮은 문자열 해시 함수? - 두 번째 이야기

이전 이야기에 대해서 더 할 이야기가 생겼군요. ^^

괜찮은 문자열 해시 함수?
; https://www.sysnet.pe.kr/2/0/1222

아무래도 무작위 문자열을 고르는 것이 테스트의 신뢰도를 떨어뜨리는 것 같고, 저 역시 좀 더 현실적인 테스트가 있으면 좋지 않을까 생각해서 이번엔 문제를 좀 골라봤습니다.

파일을 4개를 만들었는데요.

  • 영문 성경 텍스트 파일 (http://ebible.org/web/index.htm)
  • 한글 성경 텍스트 파일 (http://jwch.net/bbs/board.php?bo_table=util&wr_id=30)
  • C# 소스 코드 파일 (All-In-One Code Framework의 소스 파일)
  • 크롬 소스 코드 파일 중에서 50MB 분량만 취합

정말 x65599 해시의 경우 '영문 성격 텍스트 파일'의 경우에 아무런 충돌도 없었습니다. 하지만... 완벽한 해시가 어디있겠습니까? ^^ '한글 성경'에서는 충돌이 발생하더군요.

암튼... 테스트는 5가지 해시 방식에 대해서 진행했습니다.

  • x65599: http://www.gamedevforever.com/50 글에서 가져온 해시 코드
  • x65599 (마지막 shift 제거): "x65599" 코드 중에서 마지막 return 문에서 hash 값을 그대로 반환하도록 수정
  • 0xEDB88320: 지난번 글에서 소개한 0xEDB88320
  • 0xEDB8832F: 0xEDB88320의 값에 '0x0F'를 더한 숫자를 사용
  • .NET 4.0 GetHashCode: .NET 4.0의 string 타입에서 기본 제공되는 GetHashCode 사용

텍스트 파일이 사실 크기만 컸지, 고유 단어수를 계산해 보면 375,719 밖에 되지 않았기에 '현실(?)'을 많이 반영한 것 같지는 않지만 테스트를 아니한 것보다는 나으므로 ^^ 그냥 진행을 했습니다.

결과는...? 다음과 같습니다.

전체 워드 수: 375,719

x65599: 
    * 걸린 시간 9,573 ms
    * 충돌: 39 (0.0104 %)

x65599 (마지막 shift 제거):
    * 걸린 시간 9,309 ms
    * 충돌: 22 (0.0059 %)

0xEDB88320:
    * 걸린 시간 9,897 ms
    * 충돌 81,139 (21.5957%)

0xEDB8832F:
    * 걸린 시간 9,442 ms
    * 충돌 16 (0.0043%)

.NET 4.0 GetHashCode:
    * 걸린 시간 9,546 ms
    * 충돌 34 (0.0090%)

재미있는 결과가 나왔습니다.

  • 지난번의 무작위 테스트를 훌륭하게 통과한 0xEDB88320 값이 이번에는 20%가 넘는 충돌을 보임.
  • x65599는 여전히 shift 구문을 제거한 반환문이 더 빠르고 충돌도 낮음.

0xEDB88320 값이 저를 실망시키는군요. ^^; 오히려, 별다른 기대 없이 0xF 값을 더한 0xEDB8832F 숫자를 이용한 해시가 좋은 결과를 보여주고 있습니다. (이래서... 해시 코드는 해당 업무 도메인에 대한 문자열 셋으로 테스트가 필요한 것입니다. ^^)

그렇다면, 여기서 1등을 한 "0xEDB8832F"와 "shift 없는 x65599"에 대해서 지난번 글의 무작위 문자열 테스트 결과를 비교해 보면 어떨까요?

총 단어수 162,539,696

shift 제거한 hash
    * 걸린 시간 50,091 ms
    * 충돌 20,820,228 (12%)

0xEDB8832F:
    * 걸린 시간 53,372 ms
    * 충돌 2,807,510 (1.73%)

비록 0xEDB8832F 해시 함수가 0xEDB88320에 비해서 충돌이 더 발생하긴 했지만, '텍스트 파일' 실험의 결과와 종합해 보면 더욱 우수하기 때문에 용서가 됩니다.

아래는 이렇게 해서 최종적으로 만들어진 0xEDB88320 해시 함수입니다.

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;
}

역시 이번에도 여러분이 테스트를 할 수 있도록 소스 코드와 데이터 파일을 첨부했습니다.




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

[연관 글]






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

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

비밀번호

댓글 작성자
 



2012-01-20 12시25분
꿀보("http://blog.naver.com/gloryo") 님의 정보에 의하면 x65599 방식이 윈도우 XP 부터 기본 지원되는 방식이라고 합니다. 실제로 찾아보니 RtlHashUnicodeString 의 도움말에서 HASH_STRING_ALGORITHM_X65599 옵션을 볼 수 있고 그것이 기본값이라고 설명되어 있습니다.

RtlHashUnicodeString routine
; http://msdn.microsoft.com/en-us/library/windows/hardware/ff561915(v=vs.85).aspx

와~~~ x65599 해쉬가 꽤나 유명한 것이었군요. ^^
정성태

... 31  32  33  34  35  36  37  [38]  39  40  41  42  43  44  45  ...
NoWriterDateCnt.TitleFile(s)
12865정성태12/6/202110313개발 환경 구성: 611. 파이썬 - PyPI 패키지 만들기 (2) long_description, cmdclass 옵션
12864정성태12/6/20218262Linux: 46. WSL 환경에서 find 명령을 사용해 파일을 찾는 방법
12863정성태12/4/202110637개발 환경 구성: 610. 파이썬 - PyPI 패키지 만들기
12862정성태12/3/20218825오류 유형: 768. Golang - 빌드 시 "cmd/go: unsupported GOOS/GOARCH pair linux /amd64" 오류
12861정성태12/3/202111819개발 환경 구성: 609. 파이썬 - "Windows embeddable package"로 개발 환경 구성하는 방법
12860정성태12/1/20219414오류 유형: 767. SQL Server - 127.0.0.1로 접속하는 경우 "Access is denied"가 발생한다면?
12859정성태12/1/202115956개발 환경 구성: 608. Hyper-V 가상 머신에 Console 모드로 로그인하는 방법
12858정성태11/30/202113325개발 환경 구성: 607. 로컬의 USB 장치를 원격 머신에 제공하는 방법 - usbip-win
12857정성태11/24/202110238개발 환경 구성: 606. WSL Ubuntu 20.04에서 파이썬을 위한 uwsgi 설치 방법
12856정성태11/23/202112630.NET Framework: 1121. C# - 동일한 IP:Port로 바인딩 가능한 서버 소켓 [2]
12855정성태11/13/20219329개발 환경 구성: 605. Azure App Service - Kudu SSH 환경에서 FTP를 이용한 파일 전송
12854정성태11/13/202111394개발 환경 구성: 604. Azure - 윈도우 VM에서 FTP 여는 방법
12853정성태11/10/20219348오류 유형: 766. Azure App Service - JBoss 호스팅 생성 시 "This region has quota of 0 PremiumV3 instances for your subscription. Try selecting different region or SKU."
12851정성태11/1/202110921스크립트: 34. 파이썬 - MySQLdb 기본 예제 코드
12850정성태10/27/202112171오류 유형: 765. 우분투에서 pip install mysqlclient 실행 시 "OSError: mysql_config not found" 오류
12849정성태10/17/202111308스크립트: 33. JavaScript와 C#의 시간 변환 [1]
12848정성태10/17/202112312스크립트: 32. 파이썬 - sqlite3 기본 예제 코드 [1]
12847정성태10/14/202111860스크립트: 31. 파이썬 gunicorn - WORKER TIMEOUT 오류 발생
12846정성태10/7/202111720스크립트: 30. 파이썬 __debug__ 플래그 변수에 따른 코드 실행 제어
12845정성태10/6/202111721.NET Framework: 1120. C# - BufferBlock<T> 사용 예제 [5]파일 다운로드1
12844정성태10/3/20219014오류 유형: 764. MSI 설치 시 "... is accessible and not read-only." 오류 메시지
12843정성태10/3/20219699스크립트: 29. 파이썬 - fork 시 기존 클라이언트 소켓 및 스레드의 동작파일 다운로드1
12842정성태10/1/202129417오류 유형: 763. 파이썬 오류 - AttributeError: type object '...' has no attribute '...'
12841정성태10/1/202112062스크립트: 28. 모든 파이썬 프로세스에 올라오는 특별한 파일 - sitecustomize.py
12840정성태9/30/202112135.NET Framework: 1119. Entity Framework의 Join 사용 시 다중 칼럼에 대한 OR 조건 쿼리파일 다운로드1
12839정성태9/15/202113483.NET Framework: 1118. C# 11 - 제네릭 타입의 특성 적용파일 다운로드1
... 31  32  33  34  35  36  37  [38]  39  40  41  42  43  44  45  ...