정수형 데이터 타입(Integer)의 해시 알고리즘

이번 글에서는 [1]의 내용을 중심으로 정수형 데이터 타입에 대한 해시 알고리즘을 알아보겠습니다: (각 알고리즘에 대한 제 이해도가 낮아서 정확하게 기록되지 않았습니다)

 

• Identity 해시 함수
• Trivial 해시 함수
• Folding
• Mid-squares
• Division 해싱
• Algebraic Coding
• Multiplicative 해싱
• 피보나치 해싱
• Zobrist 해싱

 

---

Identity 해시 함수

만약 해싱될 데이터가 충분히 작다면, 사용자는 데이터 자체를 integer로 처리하여 해시값으로 사용할 수 있습니다. 이러한 identity 해시 함수를 계산하는 비용은 제로입니다. 이 해시 함수는 각 인풋을 구분되는 해시값으로 매핑합니다. 

 

여기서 '충분히 작다'는 의미는 해시값으로 사용되는 타입의 크기에 의존합니다. 예로, 자바에서 해시코드는 32비트 integer입니다. 그러므로 32 비트 integer인 Integer와 32 비트 floating-point Float 객체는 그 값을 바로 사용할 수 있습니다. 반면 64 비트 integer인 Long과 64 비트 floating-point Double은 이 방법을 사용할 수 없습니다. 

 

다른 데이터 타입도 또한 이러한 해싱 방법을 사용할 수 있습니다. 예로, 대문자와 소문자 간의 character string를 매핑할 때 사용자는 integer로 치환되는 각 캐릭터의 바이너리 인코딩을 사용하여 캐릭터의 매핑 테이블을 인덱스할 수 있습니다. 만약 각 캐릭터가 8비트로 저장되어 있다면, 테이블은 오직 2^8 = 256 개의 entry가 존재합니다. 

 

비슷한 테크닉이 2 글자로 이뤄진 국가 코드 - 국가명 매핑, 5자리 우편번호 - 도시명 매핑에도 사용될 수 있습니다. 

 

 

Trivial 해시 함수

만약 키가 균일하거나 키 스페이스 상에서 충분히 균일하게 분산되어 있어 키 값이 본질적으로 랜덤하다면, 그것들은 이미 해싱된 것으로 간주될 수 있습니다. 이러한 경우에, 키 안의 일부 비트를 추출하여 해시 테이블의 인덱스로 사용될 수 있습니다. 

 

 

Folding

폴딩 해시 함수는 인풋을 m 비트로 이뤄진 n개의 조각으로 나누어 생성됩니다. 여기서 2^m은 테이블 크기이고, 나눠진 조각들을 결합하기 위해서 ADD 또는 XOR와 같은 parity-preserving bitwise 연산을 수행합니다. 최종적인 연산은 mask 또는 shift로 위 또는 아래로 초과된 비트를 trim off합니다. 예로, 15비트의 테이블 크기와 키 값 0x0123456789ABCDEF에서 5개의 섹션으로 나눌 수 있습니다:  0x4DEF, 0x1357, 0x159E, 0x091A and 0x8. Adding하면 15비트 값인  0x7AA4를 얻을 수 있습니다. 

 

 

Mid-squares

mid-squares 해시 코드는 인풋을 제곱하고 중간의 숫자 또는 비트를 적절한 길이로 추출하여 생성됩니다. 예로, 만약 인풋이 123,456,789이고 해시 테이블 크기가 10,000 이라면 키를 제곱하면 15,241,578,759,190,521이 되고 이 17자릿수의 숫자 중에 중간의 4자리를 취해서 해시코드를 생성할 수 있습니다. mid-squares 방법은 키 앞뒤로 0이 많지 않다면, 적절한 해시 코드를 생성합니다. mid-squares 방법은 multiplicative 해싱의 변형인데, 임의의 키는 좋은 multiplier가 아니라서 그것만큼 좋지는 않습니다.

 

 

Division 해싱

일반적인 테크닉은 키에 나누는 숫자를 테이블 크기에 가까운 소수 M으로 modulo 함수를 사용하는 것입니다. 테이블 크기는 보통 2의 거듭제곱인데요. 이것은 {0, M-1}까지의 분산을 제공해줍니다. 주오 큰 숫자로 이뤄진 키 세트에서 좋은 결과를 주는데요. division 해싱의 중대한 결점은 x86을 포함한 대부분의 모던 아키텍쳐에서 division이 microprogram디어 있다는 점이 multiply보다 10배 느릴 수 있다는 사실입니다. 두 번째 결점은 클러스터된 키들을 break up하지 않는다는 점인데요. 예로, 키가 123000, 456000, 789000이라면 modulo 1000은 모두 같은 주소로 매핑합니다. 이러한 기술은 많은 키 세트가 충분히 이미 랜덤하고 키 세트가 큰 소수 숫자에 대해 순환할 확률은 낮아서 잘 동작합니다.

 

Algebraic Coding

Algebraic 코딩은 해싱의 division 방법의 변형으로 n 비트를 m 비트에 매핑하기 위해 정수 대신에 다항식 modulo 2를 사용합니다. 이 접근법에서, $M = 2^m$ 이고 m차 다항식 $Z(x) = x^m + \zeta_{m-1}x^{m-1} + ... + \zeta_0$ 를 상정합니다. 키 $K = (K_{n-1}...k_1k_0)_2$ 는 다항식 $K(x) = k_{n-1}x^{n-1} + ... + k_1x + k_0$ 로 간주합니다. 다항식 연산 modulo 2의 나머지는 $K(x)  mod  Z(x) = h_{m-1}x_{m-1} + ... h_1x + h_0$ 입니다. 이후 $h(K) = (h_{m-1} ... h_1h_0)_2$ 입니다. 만약 $Z(x)$ 가 t나 더 적은 0이 아닌 계수를 가지도록 하려면, t 비트보다 적게 공유하는 키들이 충돌하지 않는 것을 보장해야 합니다. 

 

(추가 보충 필요)

 

Multiplicative 해싱

스탠다드 multiplicative 해싱은 {0, ..., M-1}의 해시값을 생성하는 공식 $h_a(K) = \lfloor(aK  mod  W)/(W/M)\rfloor$ 을 사용합니다. 값 a는 W에 대해 '상대적으로' 소수로 적절히 선택되어야 합니다. a는 충분히 커야하고 2진 표기시 1과 0이 랜덤하게 고루 잘 섞여있어야 합니다. $W = 2^w$ 와 $M = 2^m$ 이 2의 거듭제곱수이고 w가 machine word 크기일 때 특별한 케이스가 발생합니다. 이러한 케이스에서 위의 공식은 $h_a(K) = \lfloor(aK mod 2^w)/2^{w-m}\rfloor$ 이 됩니다. 이 경우 modul $2^w$ 연산이 저레벨 프로그래밍 언어에서 디폴트로 행해지고 2의 거듭제곱수로 나누는 것이 단순히 오른쪽 쉬프트가 되며, 예로 C에서 아래와 같은 형태가 됩니다:

 

unsigned hash(unsigned K)
{
    return (a*K) >> (w-m);
}

고정된 m과 w에 대해서 한 번의 곱셈 이후 오른쪽 쉬프트 연산으로 계산되기에 컴퓨팅이 매우 빠른 해시 함수가 됩니다. 

 

Multiplicative 해싱은 실수로 쏠린 해싱 알고리즘이 되기 쉽습니다. 큰 값의 인풋 비트가 낮은 값은 아웃풋 비트에 영향을 주지 않는 형태가 그런 부분인데요. Multiplication 단계 전에 높은 비트를 아래로 쉬프트하거나 XOR, ADD하는 변환은 이러한 부분을 교정해줍니다. 그렇기에 결과적으로 함수는 아래와 같은 모습을 가집니다:

 

unsigned hash(unsigned K)
{
    K ^= K >> (w-m);
    return (a*k) >> (w-m);
}

 

 

피보나치 해싱

피보나치 해싱은 multiplier가 $2^w/\phi$ 인 multiplicative 해싱으로 w는 machine word 길이이고 $\phi$ 는 황금율입니다. $\phi$ 는 대략 5/3인 무리수로 1.618033...입니다. 이 multiplier의 특징은 테이블 스페이스에 균일하게 분산하여 키의 비트 블록에 대한 연속적인 블록을 이룹니다. 키의 높은 비트 또는 낮은 비트 안의 연속적인 키는 상대적으로 흔합니다. 다양한 word 길이에 대한 multiplier는 아래와 같습니다:

 

• 16: a = 40503
• 32: a = 2654435769

...

 

Zobrist 해싱

Tabulation 해싱 또는 미국 컴퓨터 과학자 Albert Zobrist의 이름을 따 일반적으로 알려진 Zobrist 해싱은 XOR 연산으로 테이블 룩업을 결합하여 해시 함수를 만드는 방법입니다. 이 알고리즘은 빠르고 해싱 목적에 부합한 매우 좋은 퀄리티를 제공하는 것으로 입증되었습니다. 

 

Zobrist 해싱은 원래 컴퓨터 게임 프로그램에서 체스 위치를 컴팩트하게 표현하기 위한 수단으로 도입되었습니다. 보드의 각 공간을 나타내기 위해 각 공간에 유니크한 랜덤 숫자가 할당됩니다. 그러므로 64 x 12의 숫자가 프로그램 시작 전에 초기화됩니다. 랜덤 숫자는 변동 길이이나 보드에 64개 공간이 있기에 64 비트가 많이 사용됩니다. 위치는 위치 안의 부분들을 돌면서 기록되며, 상응하는 랜덤 숫자를 인덱싱하고, 그것들에 XOR 연산을 수행합니다. 결과값은 modulo, folding 또는 해시 테이블 인덱스를 생성하기 위한 연산으로 reduce됩니다. 원래 Zobrist 해시는 위치를 나타내기 위해 테이블에 저장되었습니다.

 

이후, 이 방법은 integer의 각 바이트를 각각 유니크한 32 비트 랜덤 숫자로 나타내는 4개의 위치로 표현하여 integer를 해싱하도록 확장되었습니다. 그러므로 랜덤 숫자의 2^8 x 4 의 테이블이 구성됩니다. 32 비트 해시 integer는 연속적으로 플레인 텍스트인 integer의 각 바이트 값으로 인덱싱하고 로드된 값에 모두 XOR를 수행하여 기록됩니다. 

 

 

Reference

[1] https://en.wikipedia.org/wiki/Hash_function#Hashing_integer_data_types