16777619与FNV哈希算法

留言

FNV哈希算法

FNV（Fowler-Noll-Vo）哈希算法是一系列设计用于快速生成散列值的非加密哈希算法。它的设计目标是在散列散列键时实现高度分散，以减少碰撞并提高哈希表的性能。FNV算法特别适合散列字符串类型的数据，例如文件名、URLs、IP地址等。

提出时间

FNV哈希算法最初由Glenn Fowler、Landon Curt Noll和Phong Vo在1991年提出。之后，该算法经过了几次迭代，目前主要有FNV-1和FNV-1a两个版本。

16777619与FNV哈希算法的关系

在32位版本的FNV-1和FNV-1a算法中，16777619是算法的乘法因子（或称为FNV素数）。FNV算法的基本步骤包括将哈希值初始化为FNV偏移基数（offset basis），然后对于输入数据的每个字节，结合该乘法因子进行散列。对于32位FNV-1和FNV-1a，初始化的偏移基数通常是2166136261，乘法因子是16777619。这个特定的素数和初始哈希值的选择是FNV设计中的关键部分，目的是在散列过程中尽可能地分散数据。

FNV与Rabin-Karp算法的区别

FNV哈希算法和Rabin-Karp算法都可以用于字符串的哈希计算，但它们的应用场景和设计目的不同。

  • FNV哈希算法主要用于一般的哈希表查找、数据唯一性验证等场景。它通过特定的素数乘法和累加操作生成数据的哈希值，目标是实现快速且分散的哈希计算，以减少哈希碰撞。

  • Rabin-Karp算法主要用于字符串搜索和模式匹配问题，尤其是在查找子字符串或多个模式匹配的应用中。Rabin-Karp算法通过滚动哈希技术实现高效的字符串搜索，当算法处理文本的下一个字符时，它可以快速更新哈希值而不需要重新计算整个字符串的哈希值。Rabin-Karp算法的关键在于其使用哈希技术来加速字符串比较过程，而不是直接用于数据存储或检索。

总的来说，FNV是一个高效的哈希函数，适用于散列和数据检索，而Rabin-Karp算法则专注于通过哈希技术加速字符串的搜索和匹配过程。

概况


FNV哈希算法全名为Fowler-Noll-Vo算法，是以三位发明人 Glenn Fowler，Landon Curt Noll（这位在发现大素数领域成绩卓著），Phong Vo的首字母命名。 最早在1991年提出 (实际比Rabin-Karp算法要晚)

FNV能快速hash大量数据并保持较小的冲突率，它的高度分散使它适用于hash一些非常相近的字符串，比如URL，hostname，文件名，text，IP地址等。 (来自 FNV哈希算法)

这个算法的厉害之处在于其可以保存(上一次的)状态。比如对于字符串ab，它的哈希值是aE+b=HashAB，如果计算bc的哈希值，可以利用第一次计算的结果(HashAB-aE)*E+c=HashBC。该例是两个字符效果不明显，但如果当前串是100个字符，后移一位去哈希算法性能，就会比其他哈希方式(如md5)要快很多。(常见的哈希算法和用途)

对于很多算法，和暴力解法相比，优化的重要途径之一，是把每次运算(如比较)产生的结果在下一次尽可能用上，发挥一点价值。。而不是纯粹每次从头开始再去算(和KMP算法如此，Rabin-Karp算法亦然)


FNV在Go源码的src/hash/fnv/fnv.go中，

1
2
3
4
5
6
7
8
9
10
const (
	offset32        = 2166136261
	offset64        = 14695981039346656037
	offset128Lower  = 0x62b821756295c58d
	offset128Higher = 0x6c62272e07bb0142
	prime32         = 16777619
	prime64         = 1099511628211
	prime128Lower   = 0x13b
	prime128Shift   = 24
)

16777619 为32 bit FNV的Prime值。


在rust中也内置该算法, 在Linux，OceanBase等项目中有较多使用,

在Go reflect包中也有使用


使用


可将 字符串 哈希为32bit的数字；将字符串 哈希为任意bit的数字，将字符串 哈希为特定范围的数字

更多参考 FNV算法实战



更多阅读：

FNV哈希算法【学习】

go/src/internal/bytealg/bytealg.go

字符串查找算法（二）

Go语言源码中的Rabin-Karp算法

github-16777619

分布式技术探索——如何判断哈希的好坏