[go] FNV 해싱 알고리즘과 분석 도구

12 Dec 2023

FNV 해싱 알고리즘은 해시 함수를 생성하는 데 사용되는 간단하면서도 효율적인 방법입니다. FNV은 Fowler-Noll-Vo 약자로, Glenn Fowler, Phong Vo, Landon Curt Noll이 개발했습니다. 이 알고리즘은 데이터를 해시 값으로 매핑하는 데 널리 사용되며, 특히 해시 테이블, 데이터베이스 인덱싱, 메시지 다이제스트 등에서 사용됩니다.

FNV 해싱 알고리즘의 특징

간단하고 빠름: 단순한 비트 조작을 통해 빠르게 해시 값을 계산할 수 있습니다.
저 메모리 사용량: 적은 메모리를 사용하여 해시를 생성할 수 있습니다.
등집합 분포: 데이터의 동일성에 따른 해시 충돌 가능성이 낮습니다.

FNV-1 해싱 알고리즘

FNV-1은 첫 번째 해시 알고리즘으로, 초기 해시 값을 특정 상수로 설정하고 데이터를 반복하여 XOR 및 곱셈을 사용하여 해시 값을 갱신합니다. 컴퓨터 시스템의 네이티브 해시 값과 동일한 비트 수를 갖는 경우에 더 효과적입니다.

func fnv1Hash(data []byte) uint32 {
    const (
        fnvOffset32 = 2166136261
        fnvPrime32  = 16777619
    )
    hash := fnvOffset32
    for _, b := range data {
        hash *= fnvPrime32
        hash ^= uint32(b)
    }
    return hash
}

FNV-1a 해싱 알고리즘

FNV-1a 알고리즘은 데이터를 해시하기 위해 XOR 연산을 수행하는 FNV-1과 달리, 곱셈 후 XOR를 수행합니다. 이 알고리즘은 FNV-1에 비해 효과적인 분포 특성을 가지고 있습니다.

func fnv1aHash(data []byte) uint32 {
    const (
        fnvOffset32 = 2166136261
        fnvPrime32  = 16777619
    )
    hash := fnvOffset32
    for _, b := range data {
        hash ^= uint32(b)
        hash *= fnvPrime32
    }
    return hash
}

결론

FNV 해싱 알고리즘은 간단하면서도 효율적인 데이터 해싱에 사용되는 방법으로, 고성능을 요구하는 시스템에서 널리 사용됩니다. 데이터 무결성 검증, 빠른 조회, 인덱싱 등 다양한 응용 프로그램에서 유용하게 활용될 수 있습니다.

참고 문헌: