djb2 ​​알고리즘에서 5381과 33이 왜 그렇게 중요한가요?

djb2 ​​알고리즘에서 5381과 33이 왜 그렇게 중요한가요?

---

djb2 알고리즘은 문자열에 대한 해시 함수를 갖는다.

unsigned long hash = 5381;
int c;

while (c = *str++)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

5381과 33이 왜 그렇게 중요한가요?

---

이 해시 함수는 선형 합동 생성기 (LCG-일련의 의사 난수를 생성하는 간단한 함수 클래스 )와 유사 하며 일반적으로 다음과 같은 형식을 갖습니다.

X = (a * X) + c;  // "mod M", where M = 2^32 or 2^64 typically

djb2 ​​해시 함수와 유사합니다 ... a = 33, M = 2 ^ 32 LCG가 "전체 기간"(즉, 가능한 임의의 기간) 을 갖기 위해서는 a에 특정 속성 이 있어야합니다.

• a-1은 M의 모든 소인수로 나눌 수 있습니다 (a-1은 32, 2로 나눌 수 있으며 2 ^ 32의 유일한 소인수)
• M이 4의 배수 인 경우 a-1은 4의 배수입니다 (예 및 예).

또한 c 와 M 은 상대적으로 소수 여야합니다 (이는 c의 홀수 값에 해당됨 ).

보시다시피이 해시 함수는 좋은 LCG와 다소 유사합니다. 그리고 해시 함수에 관해서는 실제 입력 문자열 세트가 주어진 경우 해시 값의 "무작위"분포를 생성하는 함수를 원합니다.

이 해시 함수가 문자열에 좋은 이유는 해시 값의 합리적인 분포를 제공하는 동시에 매우 빠른 균형이 잘 잡혀 있다고 생각합니다. 그러나 훨씬 더 나은 출력 특성을 가지고 있다고 주장하지만 더 많은 코드 라인을 포함하는 다른 해시 함수를 많이 보았습니다. 예를 들어 해시 함수에 대한이 페이지 를 참조하십시오.

편집 : 이 좋은 대답은 왜 33과 5381이 실용적인 이유로 선택되었는지 설명합니다.

---

33은 다음과 같은 이유로 선택되었습니다.

1) 앞에서 언급했듯이 곱셈은 시프트와 더하기를 사용하여 계산하기 쉽습니다.

2) 시프트 및 추가 구현에서 볼 수 있듯이 33을 사용하면 해시 누산기에서 대부분의 입력 비트를 두 개 복사 한 다음 해당 비트를 상대적으로 멀리 분산시킵니다. 이것은 좋은 눈사태를 만드는 데 도움이됩니다. 더 큰 시프트를 사용하면 더 적은 비트가 복제되고 더 작은 시프트를 사용하면 비트 상호 작용이 더 로컬로 유지되고 상호 작용이 확산되는 데 더 오래 걸립니다.

3) 5의 시프트는 32 (레지스터의 비트 수)에 상대적으로 소수이므로 눈사태에 도움이됩니다. 문자열에 충분한 문자가 남아 있지만 입력 바이트의 각 비트는 결국 모든 이전 입력 비트와 상호 작용합니다.

4) 5의 시프트는 ASCII 문자 데이터를 고려할 때 좋은 시프트 양입니다. ASCII 문자는 4 비트 문자 유형 선택기 및 4 비트 문자 유형 선택기로 간주 될 수 있습니다. 예를 들어 숫자는 모두 처음 4 비트에서 0x3을 갖습니다. 따라서 8 비트 시프트는 특정 의미를 가진 비트가 대부분 동일한 의미를 가진 다른 비트와 상호 작용하도록합니다. 4 비트 또는 2 비트 시프트는 비슷한 생각을 가진 비트간에 강력한 상호 작용을 유사하게 생성합니다. 5 비트 시프트는 문자의 하위 4 개 비트 중 많은 부분이 동일한 문자의 상위 4 개 비트와 강력하게 상호 작용하도록합니다.

다른 곳에서 언급했듯이 5381의 선택은 그다지 중요하지 않으며 다른 많은 선택도 여기서 잘 작동합니다.

한 번에 입력되는 문자를 처리하고 명령어 수준 병렬 처리를 사용하지 않기 때문에 빠른 해시 함수가 아닙니다. 그러나 쓰기는 쉽습니다. 출력의 품질을 코드 작성의 용이성으로 나눈 것은 최적의 지점에 도달 할 수 있습니다.

최신 프로세서에서 곱셈은이 알고리즘이 개발되었을 때보 다 훨씬 빠르며 다른 곱셈 계수 (예 : 2 ^ 13 + 2 ^ 5 + 1)는 비슷한 성능과 약간 더 나은 출력을 가지며 쓰기가 약간 더 쉽습니다.

위의 답변과는 달리, 좋은 비 암호화 해시 함수는 임의의 출력을 생성하지 않습니다. 대신 거의 동일한 두 입력이 주어지면 매우 다른 출력을 생성하려고합니다. 입력 값이 무작위로 분포되어 있다면 좋은 해시 함수가 필요하지 않으며 입력에서 임의의 비트 세트를 사용할 수 있습니다. 일부 현대 해시 함수 (Jenkins 3, Murmur, 아마도 CityHash)는 매우 유사한 임의의 입력보다 더 나은 출력 분포를 생성합니다.

---

5381에서 Dan Bernstein (djb2) 은이 기사 에서 다음 과 같이 말합니다 .

[...] 거의 모든 좋은 승수가 작동합니다. c와 d가 0에서 255 사이이면 31c + d가 적절한 범위의 해시 값을 다루지 않는다는 사실에 대해 걱정하시는 것 같습니다. 그래서 33 해시 함수를 발견하고 압축기에서 사용하기 시작했습니다. , 저는 5381의 해시 값으로 시작했습니다. 이것이 261 승수만큼 효과적이라는 것을 알게 될 것입니다.

관심이 있다면 전체 스레드가 여기에 있습니다.

Ozan Yigit에는 다음과 같은 해시 함수에 대한 페이지 가 있습니다.

[...] 33 번의 마법 (소수 여부에 관계없이 다른 많은 상수보다 더 잘 작동하는 이유)는 제대로 설명되지 않았습니다.

---

아마도 33 == 2^5 + 1많은 해싱 알고리즘 2^n + 1이 승수로 사용 하기 때문 일까요?

Jerome Berger에 대한 크레딧

최신 정보:

이것은 원래 소프트웨어 패키지 djb2의 현재 버전이 원래 출처 인 cdb에 의해 입증 된 것 같습니다.

해싱 알고리즘의 핵심을 설명하기 위해 링크 한 메모는 해싱 h = ((h << 5) + h) ^ c을 수행하는 데 사용 하는 것입니다 ... x << 52 ^ 5를 승수로 사용하는 빠른 하드웨어 방법입니다.

참고 URL : https://stackoverflow.com/questions/1579721/why-are-5381-and-33-so-important-in-the-djb2-algorithm