Multiplicative Hashing

Multiplicative Hashing이란 Middle Square와는 다르게 자기 자신이 아닌 특정한 상수를 곱하는 방식입니다.

이번 페이지에서는 Multiplicative Hashing이 어떤 특징을 가지는 지 살펴보겠습니다.

Contents

• Scheme
• Constants
• Interpretation
• Implementation
• AK mod 1

Scheme

Multiplicative Hashing은 다음과 같은 수식을 사용합니다.

h(k) = |_ M * ( (A / w) * K mod 1 ) _|  // ex) |_ x _| : x보다 크지 않은 정수, A mod B : A를 B로 나눈 나머지

bin의 개수인 M에다가 ( (A / w) * K mod 1 )이라는 값을 곱해서 index를 결정한다는 의미입니다.

(A / w) * K mod 1 는 Key에 (A / w)라는 값을 곱한 후 그것을 1로 나눈 나머지, 즉 소수부분을 결과값으로 가집니다.

정리하자면 M에 0에서 1 사이의 소수를 곱한 후 그 값의 정수부분을 취하여 Index로 사용한다는 의미입니다.

Constants

그렇다면 여기서 A와 w가 의미하는 것은 무엇일까요?

A는 integer를 의미합니다. 즉 32비트로 표현되는 정수를 뜻합니다.

w는 word size를 의미합니다. 여기서는 integer의 크기인 2^32로 생각합니다.

MSB를 부호로 생각하지 않는 unsigned int를 가정합니다.

실제 unsigned int의 크기는 최대 2^32 - 1이지만 편의를 위해 2^32로 생각하겠습니다.

정리하자면 A / w는 0에서 1 사이의 소수를 의미합니다.

Interpretation

The Art of Computer Programming, vol. 3 by Donald Knuth에 나오는 Multiplicative Hashing에 대한 설명은 다음과 같습니다.

word의 제일 왼쪽에 소수점이 찍혀있다고 생각하면 Integer A는 이것 자체로 소수(fraction)로 볼 수 있다는 것입니다.

즉 A / w 라는 분수를 왼쪽에 소수점이 찍혀있는 Integer A와 같은 것으로 간주하는 것입니다.

... 36 35 34 33 32 | 31 30 ... 2 1 0    // 각 숫자는 bit의 index를 의미합니다.
    integer part   | fractional part    // 좌측은 정수부분, 우측은 소수부분 

A / w를 이러한 방식으로 저장할 때 정수부분은 모두 0이고 소수부분으로 A의 bit들이 저장됩니다.

w는 word size이기 때문에 A보다 항상 큰 값을 가집니다.

그 후 K를 곱하면 소수부분의 bit들이 carry되어 정수부분의 bit들이 채워질 수 있습니다.

여기까지가 (A / w) * K에 대한 내용입니다.

이후 mod 1을 한다는 것은 carry된 정수부분 bit들을 없애준다는 의미입니다.

이렇게 남은 소수값을 M에 곱하여 0에서 M - 1의 Index를 얻고자 합니다.

Implementation

위의 아이디어를 실제로 구현한다면 다음과 같습니다.

먼저 M을 2^m으로 설정합니다.

그리고 AK mod w를 계산합니다. 이 값을 m bit만큼 왼쪽으로 옮겨서 Integer 범위를 벗어나는 m개의 bit를 Index로 가지는 것입니다.

좀 더 구체적으로 살펴보면 다음과 같습니다.

w가 2^32이기 때문에 AK mod w는 AK의 결과에서 오른쪽부터 32 bit만 남긴 결과입니다.

그리고 이것은 Interpretation의 아이디어를 기준으로 생각한 (A / w) * K mod 1 결과와 같습니다.

남은 32 bit에 대해서 m칸 왼쪽으로 이동시키면 m bit의 정수부분이 생겨나고 이를 Index로 사용한다면

M * ( (A / w) * K mod 1 )와 같은 결과가 나타나게 됩니다.

=> 뒤에 나오는 Three-distance theorem의 관점에서 봐야함.
=> 2^31 + 2^30 + ... + 2^1 + 2^0 | 2^-1 + 2^-2 + 2^-3 ... + 2^-32
=> 복잡하게 생각할 거 없이 이렇게 정수부분과 소수부분이 표현될 때, K에 곱해지는 값이 피보나치 비율인 경우
=> 즉 (A/w)가 피보나지 비율 값이고, 이게 2^-1 + 2^-2 + ... + 2^-32와 같이 소수부분을 2진수로 나타낸다고 생각해보자
=> 그리고 modular 1을 한다는건 소수부분의 모든 비트를 1로 만들고 &연산과 같다.
=> key값만큼의 step을 이동하고 그거에 M을 곱한 후에 정수부분을 취하면 몇 번째 bin인지 나옴
=> M을 2의 거듭제곱으로하면 위의 연산은 우측으로 (32 - m)칸 shift와 같다.

이를 실제로 코드로 나타내본다면

// 실제로 정수부분의 m bit를 얻기 위해서는 
// AK를 왼쪽으로 m칸이 아니라 
// 오른쪽으로 32 - m칸 이동시켜야함
return A * K >> (32 - m);

이와 같이 표현할 수 있습니다.

AK mod 1

Multiplicative Hashing이 Middle Square Hashing과 다른 점은 key에 곱할 상수를 임의로 정할 수 있다는 것입니다.

그렇다면 이러한 특징이 어떤 결과를 불러오게 될까요?

만약 A를 w에 대해서 relatively prime(최대 공약수가 1)한 값으로 설정한다면 다음과 같은 일이 발생합니다.

A` * A mod w = 1

이러한 수식을 만족하는 A`가 존재합니다.

만약 A와 w의 최대 공약수가 1이 아니라면

아무리 A에 어떤 값을 곱하더라도 A` * A mod w의 값은 해당 최대 공약수의 배수로 표현됩니다.

예를 들어 x = 3 * p, y = 4 * p 이고, p가 최대공약수이면

p p p p
p p p
0 0 0 p // y를 x로 나눈 결과 p만 남음

어느 것이든 n배를 하여도 p단위로 늘어나게 되고, 한쪽을 다른 한쪽으로 나누어도 p단위로 남게 됩니다.

양 변에 K를 곱하면

K * A` * A mod w = K 
=> K = ((A` mod w) * (AK mod w)) mod w  // mod의 계산 성질 사용 
=> K = (A` * (AK mod w)) mod w  // A` mod w = A`

이를 통해서 A와 w가 relatively prime일 때, Key가 달라진다면 AK mod w 또한 달라진다는 것을 알 수 있습니다.

c.f) A < w, K < w

이러한 성질은 key를 randomize할 수 있는 좋은 scrambling function으로 사용될 수 있습니다.