[go] FNV 해싱 알고리즘의 해시 함수 추가 보완
FNV(Fowler-Noll-Vo) 해싱 알고리즘은 간단하지만 효과적으로 작동하는 해시 함수로 널리 사용됩니다. 이 알고리즘은 입력에 대한 해시 값을 생성하기 위해 비트 XOR과 비트 곱을 사용하여 해시 값을 계산합니다. 그러나 일부 입력에 대해 충돌이 발생할 수 있으며 이를 해결하기 위한 보완적인 해시 함수를 만들어 보겠습니다.
현재의 FNV 해시 함수
func FNVHash(data []byte) uint32 {
var hash uint32 = 2166136261
for _, b := range data {
hash *= 16777619
hash ^= uint32(b)
}
return hash
}
해시 함수 보완
FNV 해시 함수는 입력 데이터에 따라 충돌을 일으킬 수 있습니다. 이를 줄이기 위해 연속적인 해시 함수를 사용하여 보완할 수 있습니다. 예를 들어, 두 번째 해시 함수에는 원래 해시값도 함께 고려하여 보다 복잡한 해시 값을 생성하여 충돌을 줄일 수 있습니다.
func ImprovedFNVHash(data []byte) uint32 {
hash1 := FNVHash(data) // 기존의 FNV 해시 함수
hash2 := FNVHash(append(data, uint32ToBytes(hash1)...)) // 원래 해시 값도 고려한 두 번째 해시 함수
return hash2
}
func uint32ToBytes(i uint32) []byte {
b := make([]byte, 4)
binary.LittleEndian.PutUint32(b, i)
return b
}
위에서 제시된 추가 보완된 해시 함수는 원래 FNV 해시 함수를 사용하면서, 추가적으로 해시 값을 고려한 두 번째 해시 함수를 결합하여 보다 효과적인 충돌 감소가 기대됩니다.
이러한 변경사항을 적용함으로써, FNV 해싱 알고리즘의 해시 함수의 보완을 이룰 수 있습니다.
참고문헌: