해시 코드 계산을위한 현명한 프라임은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1835976

  •  11-09-2019
  •  | 
  •  

문제

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 ()를 생략 할 수 있습니다.)

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

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

이것은 일반적인 질문입니다. 따라서 I와 J에 대한 범위를주고 싶지 않습니다. 그러나 대부분의 응용 분야에서 비교적 작은 값은 큰 값보다 자주 발생한다고 가정합니다. (큰 가치를 가지고 있다면 프라임의 선택은 아마도 중요하지 않을 것입니다.) 그것은 큰 차이를 만들지 않을 수도 있지만, 더 나은 선택은 이것을 개선하는 쉽고 명백한 방법입니다. 그렇지 않습니까? 커먼즈 랭 해시 코드 빌더 또한 호기심이 많은 작은 가치를 제안합니다.

(설명: 이것은 ~ 아니다 의 복제 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,j 그것은 동일한 해시 코드를 가지고 있습니다 0,0, 그리고이 최소 값이 가능한 한 프라임을 취했습니다.

드럼 롤: 이런 의미에서 가장 좋은 프라임은 486187739입니다 (가장 작은 충돌은 i=-25486, j=67194). 기억하기가 훨씬 좋고 훨씬 쉽고 쉽게 충돌하는 것이 가장 적습니다. i=-46272 and j=46016.

"작은"또 다른 의미를주고 최소값이되고 싶다면 Math.sqrt(i*i+j*j) 충돌이 가능한 한 큰 경우 결과는 약간 다릅니다. 최고는 1322837333입니다. i=-6815 and j=70091, 그러나 내가 가장 좋아하는 92821 (가장 작은 충돌 -46272,46016)은 다시 최고의 가치만큼 우수합니다.

이러한 계산이 실제로 의미가 있는지 여부는 논란의 여지가 있음을 인정합니다. 그러나 나는 프라임으로 92821을 복용하는 것이 아무런 이유가 없다면 31보다 훨씬 더 의미가 있다고 생각합니다.

다른 팁

실제로, 당신이 너무 큰 프라임을 가져 가서 가까이에옵니다. INT_MAX, 모듈로 산술 때문에 동일한 문제가 있습니다. 당신이 주로 길이 2의 줄을 해시 할 것으로 예상한다면, 아마도 제곱근 근처의 프라임 일 것입니다. INT_MAX 당신이 해시가 더 길다면 그렇게 많이 중요하지 않으며 충돌이 불가피합니다 ...

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

결국 해싱의 가장 좋은 방법은 비교하는 것에 달려 있습니다. int 쌍 (예에서와 같이)의 경우 기본 비트 타이어 연산자를 사용하면 충분할 수 있습니다 (& or ^사용).

I 및 J의 범위를 정의해야합니다. 둘 다에 소수를 사용할 수 있습니다.

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

나는 7243을 선택했다. 적은 숫자로 빠르게 넘치지 않습니다.

해시 코드가 Prime과 아무 관련이 없다고 지적하고 싶습니다. JDK 구현에서 

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

당신이 교체하면 찾았습니다 31 ~와 함께 27, 결과는 매우 유사합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top