자바 문서 단위의 해시 코드 A의 String객체는 다음과 같이 계산된다 :
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
int산술 사용 ( 여기서 문자열s[i]의
i 번째 문자)은 문자열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 개 이상의 영어 단어 (유닉스의 두 변형에서 제공되는 단어 목록의 결합으로 구성됨 )를 사용하는 경우 상수 31, 33, 37, 39 및 41을 사용하면 7 번 미만의 충돌이 발생합니다. 각각의 경우에. 이것을 알면 많은 Java 구현이 이러한 상수 중 하나를 선택한다는 것은 놀라운 일이 아닙니다.
우연히도이 질문을 보았을 때 “다항식 해시 코드”섹션을 읽는 중이었습니다.
편집 : 여기에 내가 언급하고있는 ~ 10mb PDF 책에 대한 링크가 있습니다. Java 의 데이터 구조 및 알고리즘에 대한 섹션 10.2 해시 테이블 (413 페이지)을 참조하십시오.
답변
(대부분의) 오래된 프로세서에서는 31을 곱하면 비교적 저렴할 수 있습니다. 예를 들어 ARM에서는 하나의 명령어 일뿐입니다.
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의 2 제곱의 차이이므로). P (33)는 계산하기가 비슷하지만 성능이 약간 떨어지고 33은 합성이므로 약간 긴장합니다.
따라서 추론은 여기에 많은 대답이 암시하는 것처럼 합리적이지 않았습니다. 그러나 우리는 직감 결정 후에 합리적 이유를 생각해내는 데 능숙합니다 (Bloch조차도 그 경향이 있습니다).
답변
실제로 37은 꽤 잘 작동합니다! z : = 37 * x는로 계산할 수 있습니다 y := x + 8 * x; z := x + 4 * y. 두 단계 모두 하나의 LEA x86 명령어에 해당하므로 매우 빠릅니다.
실제로, 짝수보다 큰 소수 ( 73) 와의 곱셈 은 설정하여 동일한 속도로 수행 될 수 있습니다 y := x + 8 * x; z := x + 8 * y.
73 또는 37 (31 대신)을 사용하면 코드 가 더 밀도가 높아지기 때문에 더 좋을 수 있습니다 . 두 LEA 명령은 31만큼 곱하기 위해 이동 + 시프트 + 빼기의 경우 6 바이트 대 7 바이트 만 사용합니다. 가능한 한 가지주의 사항은 여기에 사용 된 3- 인수 LEA 명령어는 인텔의 샌디 브리지 아키텍처에서 3주기의 대기 시간이 증가함에 따라 느려졌습니다.
또한 73 은 Sheldon Cooper가 가장 좋아하는 숫자입니다.
