직육면체 내부의 모든 좌표를 나타내는 양의 정수 3개(0 <= x, y, z <= ~100,000)를 키로 갖는 해시맵을 만들려고 합니다. 예를 들어 x+y+z를 생각해 볼 수 있는데 이렇게 하면 키 충돌이 너무 많이 발생해서 좋지 않을 것 같습니다. 계산 부하가 적으면서 키 충돌이 적게 일어나는 해시 함수가 뭐가 있을까요?
x+y<<4+z<<8 (4, 8 대신 다른 숫자를 써도 되겠죠)
처음 올린 질문에는 명시하지 않았는데, 각 인덱스(x, y, z)의 값이 10만 정도 됩니다. 거듭제곱으로 해시 키의 범위를 늘리면, 오버플로우로 해시 키가 반복되는군요.
변수 하나당 20비트가 필요하다고 하면 기본 데이터는 총 60비트 정도가 될텐데 이걸 적당히 원하는 크기로 잘라서 xor하면 대충 uniform하게 distribution 시킬 수 있을 것 같네요.
예를 들어서 20비트 key 정도면 충분하다 싶으면 x ^ y ^ z 를 키로 쓰면 되고, 20비트는 해쉬맵이 메모리를 너무 많이 차지할 것 같아서 10비트로 해야겠다 하면 각 변수를 10비트씩 2개로 잘라서 6개를 xor하면 되죠.
(x >> 10) ^ (x & 0x003ff) ^ (y >> 10) ^ (y & 0x003ff) ^ (z >> 10) ^ (z & 0x003ff)
키가 일정한 분포를 보이기는 합니다만, 키의 범위가 줄어서 전체적으로 충돌은 더 많이 일어나는군요.
답반 참고해서 원하는 bit수로 응용하시면 되지 않겠습니까
각 인덱스에 홀수를 곱해서 XOR 연산을 하면, 충돌이 좀 줄더군요. 전반적인 성능은 x+y+z에 비해서 크게 다르지 않을 것 같아서 고민 중 입니다.
답변 참고해서 원하는 bit수로 응용하시면 되지 않겠습니까
빠르고 괜찮은 hash를 위해 이런 코드도 있습니다.http://www.azillionmonkeys.com/qed/hash.html
혹은 이런 코드도...http://google-opensource.blogspot.com/2011/04/introducing-cityhash.htmlhttp://code.google.com/p/cityhash/source/browse/trunk/src/city.cc
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
x+y<<4+z<<8 (4, 8 대신 다른 숫자를
x+y<<4+z<<8 (4, 8 대신 다른 숫자를 써도 되겠죠)
오버플로우로 키 값이 반복되는 군요.
처음 올린 질문에는 명시하지 않았는데, 각 인덱스(x, y, z)의 값이 10만 정도 됩니다. 거듭제곱으로 해시 키의 범위를 늘리면, 오버플로우로 해시 키가 반복되는군요.
간단히 생각나는 거로는
변수 하나당 20비트가 필요하다고 하면 기본 데이터는 총 60비트 정도가 될텐데
이걸 적당히 원하는 크기로 잘라서 xor하면 대충 uniform하게 distribution 시킬 수 있을 것 같네요.
예를 들어서 20비트 key 정도면 충분하다 싶으면 x ^ y ^ z 를 키로 쓰면 되고,
20비트는 해쉬맵이 메모리를 너무 많이 차지할 것 같아서 10비트로 해야겠다 하면 각 변수를 10비트씩 2개로 잘라서 6개를 xor하면 되죠.
(x >> 10) ^ (x & 0x003ff) ^ (y >> 10) ^ (y & 0x003ff) ^ (z >> 10) ^ (z & 0x003ff)
키가 일정한 분포를 보이기는 합니다만, 키의 범위가
키가 일정한 분포를 보이기는 합니다만, 키의 범위가 줄어서 전체적으로 충돌은 더 많이 일어나는군요.
답반 참고해서 원하는 bit수로 응용하시면 되지
답반 참고해서 원하는 bit수로 응용하시면 되지 않겠습니까
각 인덱스에 홀수를 곱해서 XOR 연산을 하면,
각 인덱스에 홀수를 곱해서 XOR 연산을 하면, 충돌이 좀 줄더군요. 전반적인 성능은 x+y+z에 비해서 크게 다르지 않을 것 같아서 고민 중 입니다.
답변 참고해서 원하는 bit수로 응용하시면 되지
답변 참고해서 원하는 bit수로 응용하시면 되지 않겠습니까
좀 overkill인 것 같지만...
빠르고 괜찮은 hash를 위해 이런 코드도 있습니다.
http://www.azillionmonkeys.com/qed/hash.html
혹은 이런 코드도...
http://google-opensource.blogspot.com/2011/04/introducing-cityhash.html
http://code.google.com/p/cityhash/source/browse/trunk/src/city.cc
댓글 달기