해시 코드 계산을위한 합리적인 소수는 무엇입니까?

해시 코드 계산을위한 합리적인 소수는 무엇입니까?

---

Eclipse 3.5에는 Java hashCode () 함수를 생성하는 매우 멋진 기능이 있습니다. 예를 들어 생성됩니다 (약간 단축 됨 :)

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(클래스에 속성이 더있는 경우 result = prime * result + attribute.hashCode();추가 속성마다 반복됩니다. int의 경우 .hashCode ()는 생략 할 수 있습니다.)

이것은 괜찮아 보이지만 프라임에 대한 선택 31. 하드웨어 승수를 도입 한 후 오랫동안 사라진 성능상의 이유로 사용 된 Java String 의 hashCode 구현 에서 가져온 것 같습니다 . 여기에 i와 j의 작은 값에 대해 많은 해시 코드 충돌이 있습니다. 예를 들어 (0,0)과 (-1,31)은 동일한 값을 갖습니다. 작은 값이 자주 발생하기 때문에 나쁜 일 (TM)이라고 생각합니다. String.hashCode의 경우 "Ca"및 "DB"와 같이 동일한 해시 코드를 가진 많은 짧은 문자열도 찾을 수 있습니다. 큰 소수를 취하면 오른쪽 소수를 선택하면이 문제가 사라집니다.

그래서 내 질문 : 선택하기에 좋은 소수는 무엇입니까? 그것을 찾기 위해 어떤 기준을 적용합니까?

이것은 일반적인 질문을 의미하므로 i와 j에 대한 범위를 제공하고 싶지 않습니다. 그러나 대부분의 응용 프로그램에서 상대적으로 작은 값이 큰 값보다 더 자주 발생한다고 생각합니다. (당신이 큰 값을 가지고 있다면 소수의 선택은 아마도 중요하지 않을 것입니다.) 그것은 큰 차이를 만들지 않을 수도 있지만, 더 나은 선택은 이것을 개선하는 쉽고 명백한 방법입니다. 그렇다면 왜 그렇게하지 않습니까? Commons lang HashCodeBuilder 는 또한 매우 작은 값을 제안합니다.

( 설명 : 이것은 String에서 Java의 hashCode ()가 31을 승수로 사용 하는 이유 의 중복 이 아닙니다 . 내 질문은 JDK의 31 역사와 관련이 없지만 새 코드에서 더 나은 값은 무엇입니까? 동일한 기본 템플릿을 사용합니다. 거기에 대한 답은 아무도 대답하지 않습니다.)

---

92821을 사용하는 것이 좋습니다 . 그 이유는 다음과 같습니다.

이에 대한 의미있는 답변을 제공하려면 i및 의 가능한 값에 대해 알아야합니다 j. 일반적으로 생각할 수있는 유일한 것은 많은 경우 작은 값이 큰 값보다 더 일반적이라는 것입니다. (프로그램에서 값으로 15가 나타날 확률은 438281923보다 훨씬 낫습니다.) 따라서 적절한 소수를 선택하여 가능한 한 가장 작은 해시 코드 충돌을 크게 만드는 것이 좋습니다. (31)이 오히려 나쁜 경우 - 이미 대한 i=-1그리고 j=31당신과 동일한 해시 값이 i=0와 j=0.

이것이 흥미 롭기 때문에, 나는 이런 의미에서 가장 좋은 소수를 찾기 위해 전체 int 범위를 검색하는 작은 프로그램을 작성했습니다. 즉, 각 소수에 대해 동일한 해시 코드를 가진 Math.abs(i) + Math.abs(j)모든 값 에서의 최소값을 검색 한 다음이 최소값이 가능한 한 큰 소수를 취했습니다.i,j0,0

Drumroll :이 의미에서 가장 좋은 프라임은 486187739입니다 (가장 작은 충돌이 있음 i=-25486, j=67194). 92821은 거의 충돌이 가장 작고 기억하기 쉽습니다 i=-46272 and j=46016.

"작은"다른 의미를 부여하고 Math.sqrt(i*i+j*j)가능한 한 큰 충돌 에 대해 최소값이되고 싶다면 결과는 약간 다릅니다. 가장 좋은 것은를 사용 i=-6815 and j=70091하는 1322837333이되지만 제가 가장 좋아하는 92821 (가장 작은 충돌 -46272,46016)이 다시 거의 비슷합니다. 최고의 가치로

나는 이러한 계산이 실제로 의미가 있는지 여부에 대해 상당히 논쟁의 여지가 있음을 인정합니다. 그러나 나는 92821을 소수로 삼는 것이 31보다 훨씬 더 합리적이라고 생각합니다.

---

실제로 소수를 너무 커서.에 가까워 INT_MAX지면 모듈로 산술 때문에 동일한 문제가 발생합니다. 대부분 길이가 2 인 문자열을 해시 할 것으로 예상하는 경우 제곱근 근처의 소수 INT_MAX가 가장 좋을 것입니다. 해시 한 문자열이 더 길면 그다지 중요하지 않으며 어쨌든 충돌은 피할 수 없습니다.

---

충돌은 그다지 큰 문제가 아닐 수 있습니다. 해시의 주요 목표는 1 : 1 비교에 등식을 사용하지 않는 것입니다. 해시가 충돌 한 객체에 대해 equals가 "일반적으로"매우 저렴한 구현이있는 경우 이는 문제가되지 않습니다.

결국 가장 좋은 해싱 방법은 무엇을 비교하는지에 따라 달라집니다. int 쌍의 경우 (예제에서와 같이) 기본 비트 연산자를 사용하는 것으로 충분할 수 있습니다 (& 또는 ^ 사용).

---

i와 j에 대한 범위를 정의해야합니다. 둘 다 소수를 사용할 수 있습니다.

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

---

7243을 선택하겠습니다. 적은 수의 충돌을 피하기에 충분히 큽니다. 작은 숫자로 빠르게 넘치지 않습니다.

---

나는 해시 코드가 프라임과 아무 관련이 없다는 것을 지적하고 싶습니다. JDK 구현에서

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

31 을 27 로 바꾸면 결과가 매우 비슷하다는 것을 알았습니다 .

참조 URL : https://stackoverflow.com/questions/1835976/what-is-a-sensible-prime-for-hashcode-calculation