해시 함수에서 소수의 사용에 대한 분석

Question

해시 기반 정렬을 연구하고 해시 함수에서 소수를 사용하는 것이 좋은 아이디어로 간주됩니다. 왜냐하면 : 키의 각 문자에 소수와 결과를 추가하면 소수가 고유하기 때문에 고유 한 값을 생성하고 31과 같은 소수는 키의 분배를 향상시킵니다.

각 문자를 곱하기 위해 짝수를 사용하는 이유는 무엇입니까? 아래의 설명에 대한 잘못된 생각 (다른 포럼에서 발견, 좋은 설명처럼 들리지만 나는 그것을 이해하지 못하고있다).

public int hashCode() 
{ 
int h = hash; 
if (h == 0) 
{ 
    for (int i = 0; i < chars.length; i++) 
    { 
     h = MULT*h + chars[i]; 
    } 
hash = h; 
} 
return h; 
} 

한다고 가정 MULT 26이었고, 백 - 문자열을 해시 을 고려 : 아래의 추론이 유효하지 않은 경우 ..

key(s)=s[0]*31(len–1)+s[1]*31(len–2)+ ... +s[len–1] 

샘플 코드를 간단한 설명을 부탁드립니다합니다. 문자열의 첫 번째 문자의 영향은 얼마나됩니까 값이 h'? The first character's value will have been multiplied by MULT 99 times, so if the arithmetic were done in infinite precision the value would consist of some jumble of bits followed by 99 low-order zero bits -- each time you multiply by MULT you introduce another low-order zero, right? The computer's finite arithmetic just chops away all the excess high-order bits, so the first character's actual contribution to h ' ... 정확히 0입니다! h' value depends only on the rightmost 32 string characters (assuming a 32-bit int), and even then things are not wonderful: the first of those final 32 bytes influences only the leftmost bit of h '이고 나머지는 에 영향을 미치지 않습니다. 분명히 짝수 인 MULT는 좋지 않습니다.

Answer 1

26 대신 2를 사용하는 것이 더 쉽다고 생각합니다. 둘 다 h의 최하위 비트에 동일한 효과가 있습니다. 일부 문자 c의 33 자 문자열 뒤에 32 바이트 (예 : 설명하기 위해)를 고려하십시오. 문자열이 완전히 null이 아니므로 해시 값이 0이 아니길 바란다.

첫 번째 문자의 경우 계산 된 해시 h은 c[0]과 같습니다. 두 번째 문자는 h * 2 + c[1]입니다. 자 이제 h은 2*c[0]입니다. 세 번째 문자의 경우 h은 이고 이제는 4*c[0]입니다. 30 번 더 반복하면 승수가 대상에서 사용할 수있는 것보다 많은 비트를 사용하므로 실제로는 c[0]이 최종 해시에 아무런 영향을주지 않음을 알 수 있습니다.

end math는 프로세스와 같이 중간 해시가 모듈로 2^32이 될 것을 제외하고는 26과 같은 다른 배수와 똑같이 작동합니다. 26이 심지어이기 때문에 각 반복마다 여전히 로우 엔드에 하나의 0 비트를 추가합니다.

Answer 2

이 해시는 다음과 같이 설명 할 수 있습니다. 여기에서 ^는 지수입니다 (x는 제외).

hash(string) = sum_over_i(s[i] * MULT^(strlen(s) - i - 1)) % (2^32). 

첫 번째 문자의 기여도를 살펴보십시오. 그것의입니다

(s[0] * MULT^(strlen(s) - 1)) % (2^32). 

문자열이 충분히 길면 (strlen (s)> 32) 다음이 0입니다.

Answer 3

는 바로 거기에 고유 한 값

중지를 생산하는 것이다. 해시는 고유하지 않습니다. 좋은 해시 알고리즘은 충돌을 최소화하지만 비둘기 원칙은 충돌을 완벽하게 피할 수 없다는 것을 보증합니다 (중요하지 않은 정보 내용이있는 데이터 유형의 경우).

Answer 4

다른 사람들이 답변을 게시했습니다. 짝수 배수를 사용하는 경우 해시를 계산할 때 문자열의 마지막 문자 만 중요합니다. 초기 문자의 영향이 레지스터에서 벗어 났기 때문입니다.

\ 합계 : 당신이 것을 사용하는 경우 1. 그래서, 최종 해시 값이 될 것입니다 -

지금 31 32-1 또는 2^5는 당신이 31 음과 같은 승수를 사용할 때 발생 고려할 수 있습니다

불행히도 stackoverflow는 TeX 수학 표기법을 지원하지 않으므로 위의 내용은 이해하기 어렵지만 문자열의 문자에 대한 두 합계를 계산할 수는 없습니다 (예 : 여기서 첫 번째 문자는 문자열의 각 후속 문자에 대해 각 문자를 5 비트 씩 이동합니다. 따라서 32 비트 컴퓨터를 사용하면 문자열의 마지막 7 문자를 제외한 모든 문자가 상단에서 벗어납니다.

31의 배수를 사용한다는 것은 마지막 7 개 이외의 문자가 문자열에 영향을 미치지 만 그 순서와는 완전히 독립적이라는 것을 의미합니다. 마지막 7 글자가 다른 2 글자를 취하면 다른 글자도 같지만 순서가 다르므로 둘 다 동일한 해시를 얻습니다. 또한 마지막 7 개의 문자 이외에 "az"및 "by"와 같은 해시를 얻습니다.

그래서 소수 승수를 사용하면 짝수 승수보다 훨씬 좋지만 여전히 좋지는 않습니다. 회전 명령을 사용하는 것이 더 좋습니다. 회전 명령은 맨 위로 이동하면 비트를 맨 아래로 이동합니다. 같은 뭔가 : 물론

public unisgned hashCode(string chars) 
{ 
    unsigned h = 0; 
    for (int i = 0; i < chars.length; i++) { 
     h = (h<<5) + (h>>27); // ROL by 5, assuming 32 bits here 
     h += chars[i]; 
    } 
    return h; 
} 

, 이것은 회전 명령의 관용구를 인식하고 최대 효율을위한 단일 명령으로 바꿀 수있을만큼 똑똑 컴파일러에 따라 달라집니다.

이

은 여전히 ​​그 훨씬 강한,하지만 대부분의 비 암호화 목적