괜찮은 문자열 해시 함수? - 두 번째 이야기
이전 이야기에 대해서 더 할 이야기가 생겼군요. ^^
괜찮은 문자열 해시 함수?
; 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;
}
역시 이번에도
여러분이 테스트를 할 수 있도록 소스 코드와 데이터 파일을 첨부했습니다.
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]