String에 있는 Java의 hashCode()는 왜 31을 승수로 사용합니까?

String에 있는 Java의 hashCode()는 왜 31을 승수로 사용합니까?

Java 매뉴얼에 따르면 의 해시 코드는String오브젝트는 다음과 같이 계산됩니다.

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

사용.int산술, 여기서s[i]문자열의 ih 문자입니다.n는 문자열 길이입니다.^지수를 나타냅니다.

31은 왜 승수로 사용되는가?

승수는 비교적 큰 소수여야 한다는 것을 이해했습니다.그럼 왜 29, 37, 심지어 97이 아닐까요?

Joshua Bloch의 Effective Java(충분히 추천할 수 없는 책으로 스택오버플로우 관련 언급이 끊이지 않아 구입한 책)에 따르면:

값 31은 홀수 소수이기 때문에 선택되었습니다.짝수이고 곱셈이 오버플로우일 경우 2의 곱셈은 이동과 같기 때문에 정보가 손실됩니다.프라임 사용의 장점은 명확하지 않지만, 전통적이다.31의 좋은 특성은 곱셈을 시프트와 뺄셈으로 대체할 수 있다는 것입니다.31 * i == (i << 5) - i최신 VM에서는 이러한 최적화가 자동으로 이루어집니다.

(제3장 항목 9부터: 동등함을 재정의할 때 항상 해시 코드를 재정의한다(48페이지))

Goodrich와 Tamassia는 50,000개가 넘는 영어 단어(Unix의 2가지 변종에서 제공되는 단어 목록 조합으로 구성됨)에서 상수 31, 33, 37, 39 및 41을 사용하면 각 경우에 7개 미만의 충돌이 발생한다고 계산했습니다.이것이 많은 Java 구현이 이러한 상수를 선택하는 이유일 수 있습니다.

Java의 데이터 구조 및 알고리즘 섹션 9.2 해시 테이블(522페이지)을 참조하십시오.

(대부분) 오래된 프로세서에서는 31을 곱하는 것이 비교적 저렴할 수 있습니다.예를 들어 ARM에서는 다음 명령어가1개뿐이에요

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

대부분의 다른 프로세서에서는 별도의 시프트 및 감산 명령이 필요합니다.그러나 승수가 느리더라도 이것은 여전히 승리입니다.최신 프로세서는 멀티플라이어가 고속인 경향이 있기 때문에 32개가 올바른 쪽에 있는 한 큰 차이는 없습니다.

이 알고리즘은 뛰어난 해시 알고리즘은 아니지만 1.0 코드보다 훨씬 우수하고 우수합니다(또한 1.0 사양보다 훨씬 우수합니다.

곱하면 비트가 왼쪽으로 이동합니다.이렇게 하면 해시 코드의 사용 가능한 공간이 더 많이 사용되어 충돌이 줄어듭니다.

2의 거듭제곱을 사용하지 않음으로써 하위의 최우측 비트도 입력되어 해시에 들어가는 다음 데이터 조각과 혼합됩니다.

표현n * 31와 동등하다(n << 5) - n.

http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622의 "댓글"에서 Bloch의 독창적인 이유를 읽을 수 있습니다.그는 해시 테이블의 결과인 "평균 체인 크기"와 관련하여 다양한 해시 함수의 성능을 조사했습니다. P(31)K&R의 책에서 발견한 그 당시 흔한 기능 중 하나였습니다(그러나 Kernighan과 Ritchie조차도 그것이 어디서 왔는지 기억할 수 없었습니다).결국 그는 기본적으로 하나를 선택해야 했고 그래서 그는 그 중 하나를 택했다.P(31)충분히 잘 할 수 있을 것 같아서요.그럼에도 불구하고.P(33)33의 곱셈도 마찬가지로 빠릅니다(단순히 5의 이동과 덧셈). 33이 소수가 아니기 때문에 31을 선택했습니다.

나머지 4개 중 RISC 기계로 계산하는 것이 가장 저렴하기 때문에 P(31)를 선택할 수 있습니다(31은 2승의 차이이기 때문입니다).P(33)도 마찬가지로 계산은 저렴하지만 성능은 약간 떨어지고 33은 복합성이기 때문에 조금 불안합니다.

그래서 그 추론은 여기 있는 많은 대답들이 암시하는 것처럼 합리적이지 않았다.하지만 우리는 모두 직감적인 결정 후에 합리적인 이유를 생각해 내는 데 능숙하다(Broch도 그럴 가능성이 있다).

사실 37은 꽤 잘 작동할 것이다! z : = 37 * x 는 다음과 같이 계산될 수 있다.y := x + 8 * x; z := x + 4 * y두 단계 모두 하나의 LEA x86 명령에 대응하므로 매우 빠릅니다.

실제로, 짝수인 소수 73을 갖는 곱셈은 다음과 같이 설정함으로써 같은 속도로 할 수 있다.y := x + 8 * x; z := x + 8 * y.

코드 밀도가 높아지기 때문에 (31이 아닌) 73 또는 37을 사용하는 것이 더 나을 수 있습니다.2개의 LEA 명령어는 6바이트밖에 걸리지 않습니다만, move+shift+subtract는 7바이트입니다.여기서 사용되는 3가지 원칙의 LEA 명령어가 인텔의 Sandy 브릿지 아키텍처에서 지연이 3사이클 증가하여 느려졌다는 것이 하나의 경고입니다.

게다가 73은 셸던 쿠퍼가 가장 좋아하는 숫자입니다.

Neil Coffey는 왜 31이 Ironing out bias에서 사용되는지 설명한다.

기본적으로 31을 사용하면 해시 함수에 대해 보다 균일한 설정 비트 확률 분포를 얻을 수 있습니다.

JDK-4045622에서 Joshua Bloch가 특정(신규)의 이유를 설명합니다.String.hashCode()구현이 선택되었다

다음 표는 3개의 데이터 세트에 대해 위에서 설명한 다양한 해시 함수의 성능을 요약한 것입니다.

1) Merriam-Webster의 두 번째 국제 생략되지 않은 사전(311,141 문자열, 평균 길이 10자)에 입력된 모든 단어와 구.

2) /bin/, /usr/bin/, /usr/lib/, /usr/ucb/ 및 /usr/openwin/bin/*의 모든 문자열(66,304 문자열, 평균 길이 21 문자)

3) 어젯밤 몇 시간 동안 웹 크롤러가 수집한 URL 목록(28,372 문자열, 평균 길이 49 문자)

이 표에 나타난 퍼포먼스 메트릭은 해시 테이블의 모든 요소에 대한 "평균 체인 크기"입니다(즉, 요소를 검색하기 위해 비교되는 키 수의 예상 값).

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

이 표를 보면 현재 Java 함수와 Weinberger 함수의 두 가지 고장 버전을 제외한 모든 함수가 거의 구분할 수 없는 뛰어난 성능을 제공한다는 것을 알 수 있습니다.저는 이 퍼포먼스가 본질적으로 "이론적인 이상"이라고 추측합니다.이것은 해시함수 대신 진정한 난수 생성기를 사용하면 얻을 수 있는 것입니다.

WAIS 함수는 사양에 난수 페이지가 포함되어 있고 성능이 매우 단순하기 때문에 제외합니다.나머지 6가지 기능 중 어느 것이든 훌륭한 선택으로 보이지만, 우리는 하나를 선택해야 합니다.나는 보의 변종과 와인버거의 기능은 제외한다고 생각한다. 왜냐하면 그것들은 비록 작지만 복잡하기 때문이다.나머지 4개 중 RISC 기계로 계산하는 것이 가장 저렴하기 때문에 P(31)를 선택할 수 있습니다(31은 2승의 차이이기 때문입니다).P(33)도 마찬가지로 계산은 저렴하지만 성능은 약간 떨어지고 33은 복합성이기 때문에 조금 불안합니다.

조시

Bloch는 이에 대해 잘 설명하지는 않지만, 제가 항상 듣거나 믿는 근거는 이것이 기초 대수학이라는 것입니다.해시는 곱셈 및 계수 연산으로 요약됩니다. 즉, 가능한 경우 공통 인수가 있는 숫자를 사용하지 않으려는 것입니다.즉, 상대적으로 소수가 균일한 답 분포를 제공합니다.

해시를 사용하여 구성되는 숫자는 일반적으로 다음과 같습니다.

• 입력한 데이터 유형의 계수(2^32 또는 2^64)
• 해시 테이블 내의 버킷카운트 계수(modulus)를 지정합니다.예전에는 자바가 소수였지만 지금은 2^n)
• 혼합함수에서 매직넘버를 곱하거나 이동시키는
• 입력값

이 값들 중 몇 가지만 제어할 수 있기 때문에 조금 더 주의를 기울여야 합니다.

JDK의 최신 버전에서는 31이 계속 사용됩니다.https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode()

해시 문자열의 목적은

• unique (연산자 참조)^해시 코드 계산 문서에서는, 일의에 도움이 됩니다).
• 계산에 드는 저렴한 비용

31은 8비트(= 1바이트) 레지스터에 넣을 수 있는 최대값이며, 1바이트 레지스터에 넣을 수 있는 최대 소수이며, 홀수입니다.

곱셈 31은 <5보다 작은 값이고, 자신을 뺀 값이기 때문에 저렴한 리소스가 필요합니다.

Java String hashCode() 및 31

이는 31이 우수한 특성을 가지고 있기 때문입니다. 즉, 곱셈은 표준 곱셈보다 빠른 비트 단위 시프트로 대체될 수 있습니다.

31 * i == (i << 5) - i

확실하지는 않지만, 소수 샘플을 테스트한 결과 31이 가능한 문자열 샘플보다 가장 잘 분포된 것으로 나타났습니다.

해시함수의 큰 기대는 결과의 균일한 랜덤성이 다음과 같은 연산에서 살아남는다는 것입니다.hash(x) % N여기서 N은 임의의 수(대부분의 경우 2의 거듭제곱)로, 이러한 연산이 해시 테이블에서 슬롯을 결정하기 위해 일반적으로 사용되는 것이 한 가지 이유입니다.해시를 계산할 때 소수 곱셈기를 사용하면 곱셈기와 N이 제수를 공유할 확률이 낮아져 연산의 결과가 덜 균일하게 랜덤하게 됩니다.

다른 사람들은 31을 곱하면 곱셈과 뺄셈을 할 수 있다는 좋은 성질을 지적해 왔다.이러한 소수점에는 수학적인 용어가 있다는 것을 지적하고 싶습니다.메르센 프라임

모든 메르센 소수는 2의 거듭제곱보다 1 작기 때문에 다음과 같이 쓸 수 있다.

p = 2^n - 1

x에 p를 곱하면:

x * p = x * (2^n - 1) = x * 2^n - x = (x << n) - x

많은 기계에서 시프트(SAL/SHL)와 감산(SUB)은 일반적으로 곱셈(MUL)보다 빠릅니다.Agner Fog의 지시 표 참조

그렇기 때문에 GCC는 메르센 소수를 시프트와 서브로 대체함으로써 곱셈을 최적화하는 것으로 보인다.

단, 해시함수에는 이러한 소수가 적합하지 않다고 생각합니다.해시 함수가 비교적 양호한 경우 해시의 상위 비트에서 랜덤성이 발생할 수 있습니다.단, Java 해시함수에서는 문자열이 짧은 상위 비트에서는 랜덤성이 거의 없습니다(그리고 하위 비트에서는 여전히 매우 의심스러운 랜덤성).이로 인해 효율적인 해시 테이블을 구축하기가 더욱 어려워집니다.Java 해시함수로는 할 수 없는 멋진 트릭을 보세요.

어떤 답변은 31이 한 바이트에 맞는 것이 좋다고 생각합니다.이것은 실제로 다음과 같은 이유로 쓸모가 없습니다.

(1) 곱셈 대신 시프트를 실시하기 때문에 승수의 크기는 상관없습니다.

(2) 내가 알기로는 8바이트 값과 1바이트 값을 곱하는 특별한 x86 명령은 없기 때문에 곱하는 경우에도 "31"을 8바이트 값으로 변환할 필요가 있었습니다.여기에서는 64비트 레지스터 전체를 곱합니다.

(그리고 127은 실제로 1바이트에 들어갈 수 있는 가장 큰 메르센 소수입니다.)

값이 작을수록 중하위 비트의 랜덤성이 증가합니까?그럴지도 모르지만, 충돌 가능성도 크게 증가하고 있는 것 같습니다. : )

여러 가지 문제를 나열할 수 있지만, 일반적으로 두 가지 핵심 원칙, 즉 혼란과 확산으로 요약됩니다.

하지만 빠른가요?아마, 별로 도움이 안 되니까.다만, 퍼포먼스가 정말로 중시되고 있는 경우는, 루프 마다 1 문자는 매우 비효율적입니다.이와 같이 긴 스트링에 대해 루프 반복마다 4글자(8바이트)씩 하는 것은 어떨까요?글쎄요, 모든 문자를 개별적으로 곱해야 하는 현재의 해시 정의로는 어렵습니다(이 문제를 해결하기 위한 약간의 해킹이 있으면 알려주세요).

언급URL : https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier