Google 发布 FarmHash,一个新的用于字符串的哈希函数系列

阅读数:3601 2014 年 4 月 8 日

话题:Google语言 & 开发架构

Google 刚刚发布了FarmHash,一个新的用于字符串的哈希函数系列。FarmHash 从CityHash继承了许多技巧和技术,是它的后继。FarmHash 有多个目标,声称从多个方面改进了 CityHash。

Geoff Pike 是 Google 的软件工程师,该库由他和 Jyrki Alakuijala 共同编写。根据他的报道,虽然 FarmHash 的开发一直受到 Google 数据中心里常见的 CPU 类型影响,但该库的目标之一是使开发人员可以快速便捷地将其应用在电话、平板电脑以及台式电脑上。正是因为这个原因,他们已经改进了现有的 32 和 64 位哈希实现。

Geoff 写道,与 CityHash 相比,FarmHash 的另一项改进是在多个特定于平台的实现之上提供了一个接口。这样,当开发人员只是想要一个用于哈希表的、快速健壮的哈希函数,而不需要在每个平台上都一样时,FarmHash 也能满足要求。

考虑了上述所有内容,FarmHash 的实现代码达到了大约 1500 行(不包括测试相关的代码),相比之下,CityHash 的代码大约为 600 行。读者可以在这里找到 CityHash 的全面分析。

目前,FarmHash 只包含在 32、64 和 128 位平台上用于字节数组的哈希函数。未来开发计划包含了对整数、元组和其它数据的支持。

CityHash 的哈希算法被发现容易受到针对算法漏洞的攻击,该漏洞允许多个哈希冲突发生(哈希泛滥)。尽管没有已知的 CityHash 漏洞利用程序,但这类攻击能够很快地让用了这种哈希算法的任何应用程序过载。该漏洞还影响了其它基于MurmurHash的主要哈希实现。目前还不清楚 FarmHash 是否能够免受相同漏洞的影响。

查看英文原文:Google publishes FarmHash, a new family of hash functions for strings