FNV-1a 해시

문제 - “랜덤인데 항상 같아야 해요”

게임 개발 중 디자이너 요청이 들어왔다.

스테이지마다 데코레이션 아이콘을 랜덤하게 배치하고 싶어요.

추가 논의 결과, 요구사항이 구체화됐다.

• 결정론적: 앱을 껐다 켜도, 같은 스테이지에는 항상 같은 아이콘이 보여야 한다
• 무작위성: 눈으로 봤을 때 패턴이 느껴지면 안 된다

정리하면 “랜덤처럼 보이지만, 실제로는 입력이 같으면 출력도 항상 같은” 매핑이 필요하다.

왜 단순 나머지 연산이 안 되는가

가장 먼저 떠오르는 방법은 이렇다.

int spriteIndex = stageIndex % spriteCount;

간단하지만, 이렇게 하면 아이콘이 0, 1, 2, 3, 0, 1, 2, 3, ... 순서로 반복된다. 무작위성이 전혀 없다. 디자이너가 원한 건 이런 게 아니다.

chapterId를 곱하거나 더해봐도 마찬가지다. 산술 연산의 조합은 입력값의 순차적 특성을 깨뜨리지 못한다. 여기서 필요한 건 입력이 1만 달라져도 출력이 완전히 달라지는 함수, 즉 해시 함수다.

해시 함수라는 선택지

해시 함수는 임의의 입력을 고정 크기의 값으로 매핑하며, 좋은 해시 함수는 Avalanche Effect(눈사태 효과)를 가진다 - 입력의 1비트 변화가 출력의 약 50% 비트를 뒤바꾼다. 덕분에 순차적인 입력(stage 1, 2, 3, ...)도 출력에서는 패턴 없이 흩어진다.

이 용도에서 해시 함수를 고를 때 중요한 기준은 세 가지다.

1. 분포 균일성: 출력이 고르게 퍼져야 한다 (특정 아이콘에 쏠리면 안 됨)
2. 구현 단순성: 게임 클라이언트에 가볍게 넣을 수 있어야 한다
3. 속도: 런타임에 호출되므로 빨라야 한다

암호학적 해시(SHA-256 등)는 분포는 완벽하지만 이 용도에는 과하다. 비암호학적 해시 중 주요 후보를 비교하면 다음과 같다.

해시	분포 품질	구현 복잡도	비고
FNV-1a	좋음	매우 낮음	가변 길이 바이트 시퀀스 해싱용 설계
MurmurHash3 finalizer	매우 좋음	낮음	단일 정수 입력에 최적화
SplitMix64 mixer	매우 좋음	낮음	단일 64비트 정수-정수 해싱 특화

노트

솔직히 말하면, 구현 당시에는 FNV-1a만 알고 있었고 SplitMix64는 이 글을 정리하면서 처음 알게 됐다. 공부해보니 순차 정수 입력에 대한 분포 품질은 MurmurHash3이나 SplitMix64가 더 낫다.

다만 SplitMix64와 MurmurHash3 finalizer는 단일 정수를 받는 mixer다. 입력이 2개 이상이면 먼저 하나로 합쳐야 한다.

// SplitMix64를 쓰려면 두 입력을 하나로 packing해야 함
long packed = ((long)chapterId << 32) | (uint)stageIndex;

지금은 chapterId와 stageIndex 두 개라 bit packing으로 충분하지만, 입력이 늘어나면 packing 전략을 매번 다시 짜야 한다. FNV-1a는 가변 길이 입력을 체이닝하도록 설계되었기 때문에, 입력이 추가되면 한 줄만 늘리면 된다.

// FNV-1a: 입력 추가는 한 줄
hash = (hash ^ (uint)newInput) * 16777619;

정리하면 FNV-1a를 선택한 이유는 “분포가 가장 좋아서”가 아니라, 이 규모에서 분포가 충분하면서 입력 확장에 가장 유연하고 구현이 간단하기 때문이다.

FNV-1a 알고리즘

FNV(Fowler-Noll-Vo)는 1991년에 제안된 비암호학적 해시 함수다. FNV-1a는 그 변형으로, XOR과 곱셈의 순서를 바꿔 Avalanche 특성을 개선한 버전이다.

32비트 FNV-1a의 동작은 다음과 같다.

1. Offset Basis로 초기화: hash = 2166136261
2. 입력 바이트를 하나씩 순회하며:
   • hash = hash XOR byte (XOR-먼저)
   • hash = hash * 16777619 (FNV Prime으로 곱셈)
3. 최종 hash 값을 반환

Algorithm 1 FNV-1a (32-bit)

procedure FNV1a($bytes$)

$hash \gets 2166136261$

for each $byte$ in $bytes$ do

$hash \gets hash \oplus byte$

$hash \gets hash \times 16777619$

end for

return $hash$

end procedure

두 매직 넘버의 정체는 이렇다.

• 2166136261 - FNV Offset Basis. 초기 해시값으로, 빈 입력에도 0이 아닌 해시를 만들어준다.
• 16777619 - FNV Prime. 곱셈에 사용되는 소수로, 해시 비트의 확산(diffusion)을 극대화하도록 선택된 값이다.

FNV-1(원본)은 곱셈을 먼저 하고 XOR을 나중에 한다. FNV-1a는 이 순서를 뒤집어서, 각 바이트의 영향이 곱셈을 통해 더 넓게 퍼지도록 했다. 실측에서도 FNV-1a가 소규모 입력에 대해 더 나은 분포를 보인다.

왜 하필 이 숫자들인가

FNV Prime - 16777619

FNV Prime은 아무 소수나 쓰는 게 아니다. 공식 FNV 스펙은 다음 조건을 모두 만족하는 소수를 요구한다.

1. 소수(prime)여야 한다
2. 이진 표현에서 1인 비트가 극히 적어야 한다 (low popcount)
3. 2^n + 2^8 + b 형태여야 한다 (n은 해시 비트 수에 따라 결정, 0 < b < 2^8)

32비트 FNV Prime인 16777619(0x01000193)의 이진 표현을 보면:

0x01000193 = 0000 0001 0000 0000 0000 0001 1001 0011
             ^                        ^  ^    ^  ^ ^
             bit 24                   8  7    4  1 0

32비트 중 1인 비트가 6개뿐이다. 이 “희소한 비트 패턴”이 핵심인데, 이유는 곱셈의 동작 원리에 있다. 이진수에서 곱셈은 본질적으로 shift와 add의 조합이다.

$$x\times 16777619=(x\ll 24)+(x\ll 8)+(x\ll 7)+(x\ll 4)+(x\ll 1)+x$$

1인 비트가 적다는 건 곱셈이 소수의 shift-add 단계로 분해된다는 뜻이다. 이것이 의미하는 바는:

• Avalanche에 유리하다: 각 shift 오프셋(24, 8, 7, 4, 1, 0)만큼 떨어진 비트 위치들이 서로 영향을 주고받는다. 랜덤한 소수(평균 16개 비트가 1)로 곱하면 오히려 비트 간 간섭이 과도해져 패턴이 생길 수 있다.
• 부수적으로 하드웨어 친화적이다: 하드웨어 곱셈기가 없는 임베디드 환경에서도 6번의 shift-add로 대체할 수 있다. 다만 현대 CPU는 IMUL 명령어가 3 사이클이면 끝나므로, 이 점은 주된 선택 이유가 아니라 부수 효과에 가깝다.

64비트, 128비트 FNV Prime도 같은 패턴을 따른다.

비트	FNV Prime	Hex	1인 비트 수
32	16777619	0x01000193	6
64	1099511628211	0x00000100000001B3	7
128	309485009821345068724781371	0x0000000001000000000000000000013B	7

Hex 값을 보면 01 00 ... 01 xx 형태가 반복되는 것을 알 수 있다.

Offset Basis - 2166136261

FNV에는 초기 버전인 FNV-0이 있었다. FNV-0은 Offset Basis가 0이었는데, 치명적인 약점이 있다. 입력이 0바이트로 시작하면 0 * prime = 0, 0 XOR 0 = 0이므로 선행 0바이트를 아예 무시해버린다. 즉, \0\0hello와 hello의 해시가 같아진다.

이를 해결하기 위해 FNV-1에서는 0이 아닌 초기값을 도입했다. 그 값을 정하는 방법은 의외로 자기참조적이다 - FNV-0 알고리즘으로 FNV 저자(Landon Curt Noll)의 식별 문자열을 해싱한 결과가 곧 Offset Basis다.

특별한 수학적 의미가 있는 건 아니고, “0만 아니면 된다”는 조건을 결정론적이고 재현 가능한 방법으로 충족시킨 것이다.

구현

StageDecorationHelper.cs

private static int GetDeterministicSpriteIndex(int chapterId, int stageIndex, int spriteCount)
{
    unchecked
    {
        var hash = (uint)2166136261;                    // FNV Offset Basis
        hash = (hash ^ (uint)chapterId) * 16777619;    // chapterId 해싱
        hash = (hash ^ (uint)stageIndex) * 16777619;   // stageIndex 해싱
        hash ^= hash >> 16;                             // 상위 비트를 하위로 접기
        return (int)(hash % (uint)spriteCount);
    }
}

한 줄씩 살펴보자.

• unchecked: C#은 기본적으로 정수 오버플로우를 조용히 wrap-around 처리하지만, 프로젝트 설정에서 CheckForOverflowUnderflow를 활성화하면 오버플로우 시 예외가 발생한다. unchecked 블록은 이런 설정과 관계없이 항상 wrap-around를 보장한다. 해시 함수는 의도적으로 오버플로우를 활용하므로, 어떤 프로젝트 설정에서도 안전하게 동작하도록 명시하는 것이 좋다.
• Offset Basis 초기화: 2166136261(0x811C9DC5)로 시작한다.
• 입력 해싱: chapterId와 stageIndex를 순서대로 XOR하고 FNV Prime을 곱한다. 바이트 단위 대신 정수 단위로 처리하는 것은 이 용도에서 충분하며, 성능상 이점도 있다.
• hash ^= hash >> 16: XOR-fold. 32비트 해시의 상위 16비트를 하위 16비트에 섞는다. spriteCount가 작을 때(예: 4~8개) % spriteCount 연산이 하위 비트만 사용하게 되는데, 이 접기 과정이 상위 비트의 정보를 하위로 내려서 분포를 개선한다.
• hash % spriteCount: 최종 해시를 아이콘 개수로 나눈 나머지가 곧 선택된 아이콘 인덱스다.

주의사항 - 해시는 결국 충돌 확률 싸움

충돌은 반드시 일어난다

해시 함수는 넓은 입력 공간을 좁은 출력 공간으로 압축한다. 32비트 해시는 약 43억 개의 출력값을 가지지만, 이를 spriteCount개로 다시 줄이면 충돌(다른 스테이지가 같은 아이콘을 받는 것)은 불가피하다.

다만 이 시나리오에서 “충돌”의 의미를 정확히 짚어야 한다. 여기서의 충돌은 보안 위협이 아니라 심미적 문제다 - 연속된 스테이지가 같은 아이콘을 받으면 랜덤하지 않아 보인다는 것이다.

Birthday Problem

$n$개의 스테이지에서 아이콘이 $k$종류일 때, 최소 한 쌍의 연속 스테이지가 같은 아이콘을 가질 확률은 Birthday Problem으로 근사할 수 있다.

$$P(\text{collision})\approx 1-e^{-\frac{n(n-1)}{2k}}$$

아이콘 8종, 스테이지 10개만 되어도 충돌 확률은 거의 100%다. 이건 해시 함수의 문제가 아니라 수학적 필연이다. 좋은 해시 함수는 충돌을 없애는 게 아니라, 충돌을 균등하게 분산시킨다. 즉, 특정 아이콘에 쏠리지 않고 모든 아이콘이 비슷한 빈도로 등장하게 만든다.

spriteCount가 2의 거듭제곱일 때

spriteCount가 2의 거듭제곱(2, 4, 8, 16 등)이면 % 대신 비트 마스크를 쓸 수 있다.

// spriteCount가 2의 거듭제곱일 때만 사용 가능
return (int)(hash & (uint)(spriteCount - 1));

이 경우 XOR-fold 단계(hash ^= hash >> 16)가 특히 중요하다. 비트 마스크는 하위 비트만 취하므로, 상위 비트의 엔트로피를 아래로 내리지 않으면 분포가 치우칠 수 있다.

반대로, spriteCount가 2의 거듭제곱이 아니면 % 연산을 사용해야 하는데, 이때는 미세한 분포 편향(modulo bias)이 생긴다. 해시 출력 범위($2^{32}$)가 spriteCount로 정확히 나누어떨어지지 않기 때문이다. 하지만 spriteCount가 수십 이하인 이 용도에서 편향은 무시할 수 있는 수준이다.

입력 순서에 주의

FNV-1a는 입력 순서에 민감하다. (chapterId=1, stageIndex=2)와 (chapterId=2, stageIndex=1)은 다른 해시값을 만든다. 다만 이건 나의 유즈케이스에서 유리한 특성이다 - 챕터가 다르면 같은 스테이지 번호라도 다른 아이콘 배치가 나온다.

단, 같은 이유로 입력 순서를 실수로 바꾸면 전체 배치가 달라진다. 함수 시그니처와 호출부의 인자 순서가 일치하는지 확인해야 한다.