해시 함수가 소수 모듈을 사용해야하는 이유는 무엇입니까?

해시 함수가 소수 모듈을 사용해야하는 이유는 무엇입니까?

---

오래 전에 저는 거래 테이블에서 1.25 달러에 데이터 구조 책을 구입했습니다. 그것에서, 해싱 함수에 대한 설명은 "수학의 본질"때문에 궁극적으로 소수로 수정되어야한다고 말했다.

1.25 달러 책에서 무엇을 기대하십니까?

어쨌든, 나는 수학의 본질을 생각하기 위해 수년을 보냈지 만 여전히 그것을 이해할 수는 없습니다.

소수의 버킷이 있어도 숫자 분포가 실제로 더 많은가? 아니면 다른 사람들 이 그것을 받아들이 기 때문에 모두 가 받아들이 는 오래된 프로그래머의 이야기 입니까?

---

일반적으로 간단한 해시 함수는 입력의 "구성 요소 부분"(문자열의 경우 문자)을 취하고 상수의 거듭 제곱을 곱한 다음 정수 유형으로 함께 추가하여 작동합니다. 예를 들어 문자열의 전형적인 (특히 좋지는 않지만) 해시는 다음과 같습니다.

(first char) + k * (second char) + k^2 * (third char) + ...

그런 다음 첫 번째 문자가 모두 같은 문자열 묶음이 공급되면 적어도 정수 유형이 오버플로 될 때까지 결과는 모두 동일한 모듈로 k가됩니다.

[예를 들어, Java의 문자열 hashCode는 이와 매우 유사합니다. k = 31로 문자를 역순으로 수행합니다. 따라서 같은 방식으로 끝나는 문자열간에 모듈로 31과 눈에 띄는 관계를 얻으며 끝 근처를 제외하고 같은 문자열 사이에서 모듈로 2 ^ 32의 눈에 띄는 관계를 얻습니다. 해시 테이블 동작을 심각하게 망칠 수는 없습니다.]

해시 테이블은 버킷 수에 대한 해시 계수를 가져와 작동합니다.

충돌이 해시 테이블의 효율성을 감소시키기 때문에 해시 테이블에서는 가능한 경우 충돌을 일으키지 않는 것이 중요합니다.

이제 누군가가 첫 번째 문자가 모두 같은 것처럼 항목 사이에 관계가있는 해시 테이블에 전체 값을 넣었다고 가정 해보십시오. 이것은 상당히 예측 가능한 사용 패턴이므로 너무 많은 충돌을 일으키기를 원하지 않습니다.

해시에 사용 된 상수와 버킷 수가 coprime 이면 "수학의 특성 때문에"수학 적인 경우 충돌이 최소화됩니다. 그들이 coprime 이 아닌 경우충돌이 최소화되지 않은 입력들 사이에는 상당히 간단한 관계가 있습니다. 모든 해시는 공통 계수와 같은 모듈로 나온다. 즉, 공통 계수의 모듈로 값을 갖는 버킷의 1 / n 번째에 해당된다. n 배의 충돌이 발생합니다. 여기서 n은 공통 요소입니다. n은 2 이상이므로 상당히 간단한 유스 케이스가 일반적인 경우보다 최소 두 배의 충돌을 생성하는 것은 허용되지 않습니다. 일부 사용자가 배포판을 버킷으로 나누려는 경우 간단한 예측 가능한 사용법이 아니라 이상한 사고가 되길 원합니다.

이제 해시 테이블 구현은 분명히 항목에 넣은 항목을 제어 할 수 없습니다. 그들은 그들이 관련되는 것을 막을 수 없습니다. 따라서 할 일은 상수와 버킷 수를 동일하게 유지하는 것입니다. 그렇게하면 작은 공통 요소와 관련하여 버킷의 계수를 결정하기 위해 "마지막"구성 요소에만 의존하지 않습니다. 내가 아는 한, 그들은 이것을 달성하기 위해 소수가 될 필요는 없으며 단지 coprime입니다.

그러나 해시 함수와 해시 테이블이 독립적으로 작성된 경우 해시 테이블은 해시 함수의 작동 방식을 모릅니다. 작은 요인으로 상수를 사용하고있을 수 있습니다. 운이 좋으면 완전히 다르게 작동하고 비선형적일 수 있습니다. 해시가 충분하면 모든 버킷 수는 괜찮습니다. 그러나 편집증 해시 테이블은 좋은 해시 기능을 가정 할 수 없으므로 소수의 버킷을 사용해야합니다. 마찬가지로 편집증 해시 함수는 큰 소수 상수를 사용해야하므로 누군가 상수와 공통 요소를 갖는 여러 버킷을 사용할 가능성을 줄입니다.

실제로 버킷 수로 2의 거듭 제곱을 사용하는 것이 일반적이라고 생각합니다. 이것은 편리하며 올바른 크기의 소수를 검색하거나 미리 선택해야하는 시간을 절약 해줍니다. 따라서 승수도 사용하지 않는 해시 함수에 의존합니다. 일반적으로 안전한 가정입니다. 그러나 위와 같은 해시 함수를 기반으로 때때로 해시 동작이 잘못 발생할 수 있으며 주요 버킷 수는 더 도움이 될 수 있습니다.

"모든 것이 가장 중요하다"는 원칙을 고수하는 것은 해시 테이블에 대한 적절한 배포를 위해 충분하지만 필요한 조건은 아는 한입니다. 다른 사람이 동일한 규칙을 따랐다 고 가정 할 필요없이 모든 사람이 상호 운용 할 수 있습니다.

[편집 : 소수의 버킷을 사용해야하는 또 다른보다 전문적인 이유가 있습니다. 선형 프로빙과의 충돌을 처리하는 경우입니다. 그런 다음 해시 코드에서 보폭을 계산하고 해당 보폭이 버킷 수의 요인이되면 시작한 곳으로 돌아 오기 전에 프로브 (bucket_count / stride) 만 수행 할 수 있습니다. 가장 피해야 할 경우는 stride = 0입니다. 물론 특수 사례이어야하지만 작은 정수와 같은 특수 케이스 bucket_count / stride도 피하기 위해 bucket_count를 소수로 만들 수 있습니다. stride가 0이 아니라면 제공됩니다.]

---

해시 테이블에서 삽입 / 검색 할 때 가장 먼저해야 할 일은 주어진 키에 대한 해시 코드를 계산 한 다음 hashCode % table_length를 수행하여 hashCode의 크기로 해시 코드를 트리밍하여 올바른 버킷을 찾는 것입니다. 다음은 아마도 당신이 어딘가에서 읽은 2 가지 '설명'입니다

1. table_length에 2의 거듭 제곱을 사용하면 (hashCode (key) % 2 ^ n)를 찾는 것이 (hashCode (key) & (2 ^ n -1))만큼 간단하고 빠릅니다. 그러나 주어진 키에 대해 hashCode를 계산하는 기능이 좋지 않으면 몇 가지 해시 버킷에서 많은 키를 클러스터링해야합니다.
2. 그러나 table_length에 소수를 사용하면 약간 바보 같은 hashCode 함수가 있더라도 계산 된 hashCode가 다른 해시 버킷에 매핑 될 수 있습니다.

그리고 여기 증거가 있습니다.

hashCode 함수가 다른 {x, 2x, 3x, 4x, 5x, 6x ...} 중에서 다음과 같은 해시 코드를 생성한다고 가정하면,이 모든 것이 m 개의 버킷으로 클러스터링됩니다. 여기서 m = table_length / GreatestCommonFactor (table_length, x). (이것을 확인 / 파생하는 것은 사소한 일입니다). 이제 클러스터링을 피하기 위해 다음 중 하나를 수행 할 수 있습니다.

{x, 2x, 3x, 4x, 5x, 6x ...}와 같이 다른 hashCode의 배수 인 hashCode를 너무 많이 생성하지 않도록하십시오. 그러나 hashTable이 있어야하는 경우 다소 어려울 수 있습니다. 수백만 개의 항목. 또는 단순히 GreatestCommonFactor (table_length, x)를 1로 설정하여, 즉 x와 table_length를 함께 사용하여 m을 table_length와 동일하게 만듭니다. 그리고 x가 임의의 숫자 일 수 있다면 table_length가 소수인지 확인하십시오.

에서-http: //srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

---

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

사진과 함께 매우 명확한 설명.

편집 : 요약으로, 소수를 선택한 소수에 곱하고 모두 더할 때 고유 한 값을 얻을 가능성이 가장 높으므로 소수가 사용됩니다. 예를 들어 문자열이 주어지면 각 문자 값에 소수를 곱한 다음 모두 더하면 해시 값이됩니다.

더 좋은 질문은 왜 정확히 숫자 31입니까?

---

tl; dr

index[hash(input)%2]가능한 모든 해시의 절반과 값 범위에 충돌이 발생합니다. index[hash(input)%prime]가능한 모든 해시의 <2의 충돌이 발생합니다. 제수를 테이블 크기로 고정하면 숫자가 테이블보다 클 수 없습니다.

---

다항식 모듈로 P를 사용하는 일반적인 해시 함수에 고유 한 값을 얻을 가능성이 높으므로 프라임이 사용됩니다. 예를 들어 길이 <= N의 문자열에 이러한 해시 함수를 사용하면 충돌이 발생합니다. 이는 2 개의 다른 다항식이 동일한 값의 모듈로 P를 생성한다는 것을 의미합니다.이 다항식의 차이는 다시 같은 정도 N (또는 그 이하)의 다항식입니다. 그것은 N 뿌리를 넘지 않습니다 (이 주장은 필드 => 소수에 대한 다항식에 대해서만 참이므로 수학의 본질 자체입니다). 따라서 N이 P보다 훨씬 작 으면 충돌이 없을 것입니다. 그 후, 실험은 37이 길이가 5-10 인 문자열의 해시 테이블에 대한 충돌을 피하기에 충분히 크고 계산에 사용하기에 충분히 작은 것을 보여줄 수 있습니다.

---

다른 관점을 제공하기 위해이 사이트가 있습니다.

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

소수의 버킷으로 반올림하는 대신 가능한 많은 버킷을 사용해야한다고 주장합니다. 합리적인 가능성처럼 보입니다. 직관적으로, 더 많은 수의 버킷이 더 나은 방법을 확실히 알 수는 있지만 수학적 주장을 할 수는 없습니다.

---

소수는 고유 한 숫자입니다. 소수가 다른 소수를 가진 소수의 결과는 소수가 그것을 구성하는 데 사용된다는 사실 때문에 고유 한 가능성이 가장 높다는 점에서 고유합니다 (물론 소수 자체가 아닙니다). 이 속성은 해싱 함수에서 사용됩니다.

"Samuel"이라는 문자열이 주어지면 각 구성 숫자 또는 문자에 소수를 곱하고 합산하여 고유 한 해시를 생성 할 수 있습니다. 이것이 프라임이 사용되는 이유입니다.

그러나 소수를 사용하는 것은 오래된 기술입니다. 여기에서 핵심은 충분히 고유 한 키를 생성 할 수있는 한 다른 해싱 기술로도 이동할 수 있다는 것을 이해하는 것입니다. http://www.azillionmonkeys.com/qed/hash.html 에 대한이 주제에 대한 자세한 내용을 보려면 여기로 이동하십시오

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

---

해시 함수의 선택에 따라 다릅니다.

많은 해시 함수는 데이터의 다양한 요소를 기계의 워드 크기에 해당하는 2의 거듭 제곱을 모듈로 곱하여 여러 요소를 결합합니다 (계산은 오버플로로 계산하여 자유 롭습니다).

데이터 요소의 승수와 해시 테이블의 크기 사이에 공통 요소를 원하지 않습니다. 데이터 요소를 변경해도 전체 테이블에 데이터가 분산되지 않을 수 있기 때문입니다. 테이블 크기에 대해 소수를 선택하면 공통 요인이 거의 없습니다.

반면, 이러한 요소는 일반적으로 홀수 소수로 구성되므로 해시 테이블에 2의 거듭 제곱을 사용하여 안전해야합니다 (예 : Java hashCode () 메소드를 생성 할 때 Eclipse가 31을 사용함).

---

테이블 크기 (또는 모듈로의 숫자)가 T = (B * C)라고 가정하십시오. 이제 입력의 해시가 N이 정수일 수있는 (N * A * B)와 같으면 출력이 잘 분산되지 않습니다. n이 C, 2C, 3C 등이 될 때마다 출력이 반복되기 시작합니다. 즉, 출력은 C 위치에만 배포됩니다. 여기서 C는 (T / HCF (table-size, hash))입니다.

이 문제는 HCF 1을 만들어 제거 할 수 있습니다. 소수는 매우 좋습니다.

또 다른 흥미로운 점은 T가 2 ^ N 일 때입니다. 이것들은 모든 하위 N 비트의 입력 해시와 정확히 동일한 출력을 제공합니다. 모든 숫자가 2의 거듭 제곱으로 표현 될 수 있으므로 T로 어떤 수의 모듈로를 취하면> = N 인 2 개의 형식 번호의 모든 거듭 제곱을 빼서 입력에 따라 항상 특정 패턴의 수를 줄입니다. . 이것은 또한 나쁜 선택입니다.

마찬가지로, 10 ^ N 인 T도 비슷한 이유로 인해 나쁩니다 (이진 대신 숫자를 십진수로 나타내는 패턴).

따라서 소수는 더 나은 분산 결과를 제공하는 경향이 있으므로 테이블 크기에 적합한 선택입니다.

---

내 다른 답변에서 복사 https://stackoverflow.com/a/43126969/917428 . 자세한 내용과 예는 참조하십시오.

컴퓨터가 기본 2에서 작동한다는 사실과 관련이 있다고 생각합니다. 기본 10에서 동일한 기능이 어떻게 작동하는지 생각해보십시오.

• 8 % 10 = 8
• 18 % 10 = 8
• 87865378 % 10 = 8

숫자가 무엇이든 상관 없습니다. 8로 끝나는 한 모듈로 10은 8이됩니다.

충분히 큰, 2의 제곱수가 아닌 숫자를 선택하면 해시 함수가 실제로 일부 입력 비트가 아닌 모든 입력 비트의 함수인지 확인할 수 있습니다.

---

Steve Jessop의 답변에 뭔가를 추가하고 싶습니다 (평판이 충분하지 않아서 언급 할 수 없습니다). 그러나 나는 유용한 자료를 발견했다. 그의 대답은 매우 도움이되지만 실수를 범했습니다. 버킷 크기는 2의 제곱이 아니어야합니다. 나는 토마스 코멘 (Thomas Cormen), 찰스 라이저 슨 (Charles Leisersen) 등의 "Introduction to Algorithm"책에서 인용 할 것입니다.

나누기 방법을 사용할 때 일반적으로 특정 값 m을 피합니다. 예를 들어, m = 2 ^ p이면 h (k)는 k의 p 최하위 비트 일 뿐이므로 m은 2의 거듭 제곱이되어서는 안됩니다. 모든 하위 p- 비트 패턴이 똑같이 가능하다는 것을 알지 못하면 키의 모든 비트에 의존하도록 해시 함수를 설계하는 것이 좋습니다. 연습 11.3-3에서 보여 주듯이 k가 기수 2 ^ p로 해석되는 문자열 인 경우 m = 2 ^ p-1을 선택하면 k의 문자를 치환해도 해시 값이 변경되지 않으므로 선택이 좋지 않을 수 있습니다.

도움이 되길 바랍니다.

---

해시 함수의 경우 일반적으로 colisions를 최소화하는 것뿐만 아니라 몇 바이트를 변경하면서 동일한 해시를 유지하는 것을 불가능하게하는 것이 중요합니다.

: 당신이 방정식이 말 (x + y*z) % key = x과를 0<x<key하고 0<z<key. key가 소수이면 n * y = key는 N의 모든 n에 대해 true이고 다른 모든 수에 대해서는 false입니다.

key가 주요한 예가 아닌 예 : x = 1, z = 2 및 key = 8 key / z = 4는 여전히 자연수이므로 4는 방정식의 해가되고이 경우에는 (n / 2) * y = key는 N의 모든 n에 대해 참입니다. 8이 소수가 아니기 때문에 방정식의 해가 실제로 두 배가되었습니다.

공격자가 이미 8이 방정식에 대한 가능한 솔루션이라는 것을 알고 있다면 파일을 8에서 4로 변경하여 동일한 해시를 얻을 수 있습니다.

---

나는 위에있는 인기있는 답변 중 일부에 링크 된 인기있는 wordpress 웹 사이트를 읽었습니다. 내가 이해 한 것으로부터, 나는 내가 한 간단한 관찰을 나누고 싶다.

이 기사의 모든 세부 정보는 here 에서 찾을 수 있지만 다음 사항을 충족한다고 가정합니다.

• 소수를 사용하면 고유 한 가치 의 "최고의 기회"가됩니다

일반적인 해시 맵 구현에서는 두 가지가 고유해야합니다.

• 키의 고유 해시 코드
• 실제 값 을 저장하는 고유 인덱스

고유 인덱스는 어떻게 얻습니까? 내부 컨테이너의 초기 크기도 중요합니다. 그래서 기본적으로 소수는 고유 객체를 생성하고 내부 컨테이너 내부에서 색인을 찾는 고유 한 숫자를 생성하는 독특한 특성을 가지고 있기 때문에 관여합니다.

예:

키 = "키"

값 = "값" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

고유 한 ID로 매핑

이제 우리는 가치가 있는 독특한 위치 를 원합니다.

uniqueId % internalContainerSize == uniqueLocationForValue가정 internalContainerSize은 또한 프라임입니다.

나는 이것이 간단하다는 것을 알고 있지만 일반적인 아이디어를 얻고 싶습니다.

---

주요 전력 계수에 관한 "수학의 본질"은 유한 필드 의 하나의 빌딩 블록이라는 것 입니다 . 다른 두 빌딩 블록은 덧셈과 곱셈 연산입니다. 프라임 모듈러스의 특별한 속성은 모듈러스에 대한 "정규"덧셈과 곱셈 연산으로 유한 필드를 형성한다는 것입니다. 이것은 모든 곱셈이 다른 ​​정수 모듈로 프라임에 매핑되므로 모든 덧셈도 마찬가지입니다.

프라임 모듈러스는 다음과 같은 이유로 유리합니다.

• 그들은 2 차 해싱에서 2 차 승수를 선택할 때 최대한의 자유를 제공합니다. 0을 제외한 모든 승수는 모든 요소를 ​​정확히 한 번만 방문하게됩니다.
• 모든 해시가 계수보다 작 으면 전혀 충돌이 없습니다
• 랜덤 프라임은 두 계수의 거듭 제곱보다 더 잘 혼합되며 서브셋뿐만 아니라 모든 비트의 정보를 압축합니다.

그러나 그들은 큰 단점을 가지고 있지만 정수 CPU가 필요합니다. 이는 현대 CPU에서도 많은 (~ 15-40) 사이클이 필요합니다. 약 절반의 계산으로 해시가 매우 잘 혼합되도록 할 수 있습니다. 두 번의 곱셈과 xorshift 연산은 주요 moudulus보다 더 잘 혼합됩니다. 그런 다음 해시 테이블 크기와 해시 축소가 가장 빠른 것을 사용하여 2 테이블 크기의 거듭 제곱에 대해 총 7 개의 작업을 수행하고 임의 크기에 대해 약 9 개의 작업을 수행 할 수 있습니다.

나는 최근에 가장 빠른 해시 테이블 구현 을 많이 보았고 대부분은 프라임 모듈러스를 사용하지 않습니다.

참고 URL : https://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus