文档结构  
翻译进度:已翻译     翻译赏金:0 元 (?)    ¥ 我要打赏
参与翻译: vincentsun (10), tony (3)

前一段时间我需要一个快速的 哈希函数 ,其散列值 为32字节。我们在很多地方已经用到了 Murmur哈希 ,所以我开始寻找其他的Hash函数。之后我尝试过使用 xxHash,  发现运算速度稍快,所以我放弃了在代码库中使用 xxHash ,并搁置了最主要的事情并迅速离开 度假 ,脑海里涌现一个念头:“哪天应该研究一下其他的哈希函数,最少将所有的哈希函数归纳总结到我的一个文件夹中”。所以这就是我做的:“嘿,我将要MurmurHash, SpookyHash and xxHash的源代码放在一个地方”。但是事情很快升级失控。

第 1 段(可获 1.31 积分)

我发现了一些情况!  这些你会在一个有逼格的代码库中找到的,很多人在维护它:

  • 大多数地方使用了恰当的哈希函数--对于我们而言,如Murmur2A的32/64位哈希 和 SpookyV2的128位哈希,这些不是问题的根源。
  • Murmur 哈希以种子数作为输入项,所以,自然而然,代码中几乎所有的地方复制-粘贴的相同的十六进制随机数作为种子数:)
  • 这里至少有几处FNV或djb2哈希函数实现的复制分散在不同的地方,在不同的地方被使用。
  • 有的代码使用了真的十分糟糕的hash函数。在几年前当有人发现它如此的糟糕时候 甚至 在上面添加了一个注释,----然而他们只是在他们自己的项目中停止使用,而并没有替换成其他的用法。生活总是寻求最容易的路径:) ,幸运的是,我们描述中使用到散列函数的地方并不是很“关键”。
  • 而95%的使用非加密散列函数的代码由于运行时的原因(例如,他们实际上并不关心散列的确切值)依然的在使用,一些哈希文件,及序列化其哈希值,每一部分都需要仔细研究,无论你是否可以轻松的切换到一个新的哈希函数。
  •  一些其他与哈希相关的代码(具体来说,我们必须要有能保存128位哈希值的结构体来进行128位的哈希计算),在很久以前是以一种有趣的方式写的。当然,我们的代码也犯过类似错误(幸运的是,所有的都调试代码,或测试模拟代码,或一些非关键代码)。长话短说,绝对不要有像这样构造构造函数: Hash128(const char* str, int len=16)!
    • 有人会认为这是接收一个字符串来进行哈希运算,而不是对字节的哈希值。
    • 有人将“foo”传递进去,并没有提供参数的长度,这样会导致越界读取。
    • 有些代码会意外的传递一些值比如0给一个接收Hash128的函数,由于C++的特性,这将 隐式转换为一个Hash128(NULL, 16)的构造函数,那么问题就接踵而至了。
    • 教训:小心使用隐式构造函数(使用显式)。小心使用默认参数。不要将类型设置为const char *,除非它是一个字符串。
第 2 段(可获 4.41 积分)

所以一开始“移动一些文件”分支,最终成为一个“移动文件,切换大多数哈希函数,删除一些坏的哈希函数,更改一些代码,修复一些错误的用法,添加测试和评论”类型的事情。 这是哈希函数的另一个世界,一路走下去,无论如何!

哈希函数,该使用哪一个?

MurmurHash 很受欢迎,至少在游戏开发者的圈子里是这样,作为“通用哈希函数”。我在Twitter快速投票似乎印证了这个说法:

这是一个不错的选择,但让我们稍后再看,我们一般可以做得更好。 还一个很好的选择,尤其是你对你的数据比较了解而不是仅仅知道 “它将是一个未知的字节数”。不做的选择就是自己实现(例如:参考 Won Chun’s的答问 ,或 Rune’s 对 xxHash/Murmur的改进 专用于4字节的密钥 等等)。如果你知道你的数据,总是可以尝试看各种算法的使用是否可以产生好的效果!

第 3 段(可获 2.01 积分)

 

有时你不太了解 你的数据,比如你在哈希任意的文件,或者一些用户的“可能是任何事情”的输入。

因此,我们看一下通用的哈希函数。在网上有很多很好的测试(比如 Hash functions: An empirical comparison),但我希望自己做些小测试。毕竟,为什么不呢?下面是我随机鼓弄到一起的 小测试平台

吞吐率

下面是不同的哈希函数,处理不同长度的数据,得到的吞吐率结果(MB/s):

测试机器是2013年年末的MacBookPro(Core i7-4850HQ 2.3GHz处理器),Xcode 7.3.1 软件64 字节版。

  • xxHash用于32位变量、64位变量、以及用64位变量但用后32位作为处理结果的情况
  • SpookyHash V2版本,用于128位变量,只取后64位
  • Murmur,用于多种变量位数
  • CRC32,FNV 和 djb2,因为我在我们自己的代码库里面找到了他们。我实际上没有检查他们都是适当实现的版本,还是经过了一定调整的版本。他们的源代码存储在 实验床
第 4 段(可获 2.24 积分)

当处理不是很小的数据(超过10-20字节)时,xxHash的吞吐率最高。如果你需要128比特的哈希,SpookyHash效能也不错。

针对较小的散列值情况如何呢?

这是个好问题!XXH64通过利用现代CPU的指令级别并行来实现高吞吐率。它的主循环利用四个独立的哈希环(hash round),每次处理32字节数据。这个过程大概是这样子:

// rough outline of XXH64:
// ... setup code
do {
    v1 = XXH64_round(v1, XXH_get64bits(p)); p+=8;
    v2 = XXH64_round(v2, XXH_get64bits(p)); p+=8;
    v3 = XXH64_round(v3, XXH_get64bits(p)); p+=8;
    v4 = XXH64_round(v4, XXH_get64bits(p)); p+=8;
} while (p<=limit);
// ... merge v1..v4 values
// ... do leftover bit that is not multiple of 32 bytes

即使这种方式看起来是“多做了工作”,但结果是它比FNV(每次处理一个字节,而且每个操作都依赖前一个操作的结果)这样极为简单的算法还要快。

// rough outline of FNV:
while (*c)
{
	hash = (hash ^ *c++) * p;
}

 

第 5 段(可获 1.41 积分)

然而,xxHash在主循环周围有一些“开场白”和“后记”的代码段,用于处理一些没有对齐的数据,或者不是32字节整数倍的数据边角料。这会增加一些分支,而且对于短哈希值,甚至根本不需要进入那个聪明的主循环。

这一点可以从上图中看出来。例如,xxHash 32(主循环每次处理16字节数据)在哈希值大小小于100字节时更快。让我们用更小的数据值来测试一下。

这种情况下,我们可以看到其他算法的指令集并行优化效果不明显,但超级简单的FNV或djb2在性能上表现最优。我将FNV选为冠军的原因是,在我的测试中djb2出现了更多的哈希冲突(详见下文)。

第 6 段(可获 1.66 积分)

其他的平台情况如何呢?

台式机/Windows系统:我在一台Windows机器上(Core i7-5820K 3.3GHz处理器,Win10操作系统,Visual Studio 2015 软件 64 比特版本)的测试结果与Mac上基本一致。这一点在预料之中。

游戏机:我在XBoxOne上做了一个简单的测试。结果在两方面让人吃惊:1)天啊游戏机的CPU太慢了(呃,这也不那么令人吃惊),以及2)xxHash在这里表现不那么好了。它的表现尚可,但xxHash64要稳定地慢于xxHash32,以及对于较大的哈希值长度,SpookyHash击败了这两者。或许我需要需要修改一些设置,或者是让 Yann 来看看是怎么回事?住,以后再说...

第 7 段(可获 1.44 积分)

移动端:我在iPhone6手机的64字节版本上做了测试。结果同样不令人吃惊,但有一点与游戏机情况相同:不像在拥有Intel CPU的PC或Mac上,xxHash64不再比其他哈希函数好得多了——SpookyHash在ARM64机器上表现也很好。

JavaScript! :) 由于做起来很容易,我通过 Emscripten 将代码编辑到了asm.js 上面。整体上来看情况比较类似,但超过32比特的哈希函数(xxHash64,SpookyV2)会慢很多。这一点也是在预料之中的,因为xxHash64和Spooky都是要么为64比特的CPU专门设计的,要么是为你绝对需要一个大于32比特的哈希值的情况专门设计的。如果你使用32比特的哈希值,使用xxHash32或者Murmur!

第 8 段(可获 1.28 积分)

哈希质量如何?

SMHasher 是被实际采用的哈希函数测试套件(也有 另一个分支 包含了更多现代哈希函数)。

对于一个外行测试,我针对我关心的数据集测试了一些参数:

  • 单词” - 就是一堆英文单词(/usr/share/dict/words)。共235886条,总大小2.2MB,平均长度9.6字节。
  • 文件名” - 一堆文件路径(从一个Unity源码树的测试目录中获取的)。共80297条,总大小4.3MB,平均长度56.4字节。
  • “源代码” - 从Unity源码树中取了一部分源代码文件。共6069项,总大小43.7MB,平均长度7547字节。
第 9 段(可获 1.28 积分)

我们首先看一下,如果我们用哈希函数进行唯一性/校验和类型的检验,我们在这些数据集上遇到了多少次哈希冲突。数字越低越好(0是最理想的):

Hash Words collis Filenames collis Source collis

xxHash32 6 0 0

xxHash64-32 7 0 0

xxHash64 0 0 0

SpookyV2-64 0 0 0

Murmur2A 11 00

Murmur3-32 3 1 0

CRC32 5 2 0

FNV 5 1 0

djb2 10 1 0

ZOMGBadHash 998 84 20(?)

如上所述,ZOMGBadHash 使我们找的一个很差的哈希函数。它也不是很快,而且看它遇到了多少次哈希冲突!下面是它的代码:

unsigned CStringHash(const char* key)
{
	unsigned h = 0;
	const unsigned sr = 8 * sizeof (unsigned) - 8;
	const unsigned mask = 0xFu << (sr + 4);
	while (*key != '\0')
	{
		h = (h << 4) + *key;
		std::size_t g = h & mask;
		h ^= g | (g >> sr);
		key++;
	}
	return h;
}
第 10 段(可获 0.83 积分)

我猜测有人认为一个随机使用大量的“移位”和“异或”能够制作一个优秀的哈希函数。而且为了好的测试性能,随机使用混合的32比特和64字节计算。不要这么做!哈希函数不仅仅是随机的比特操作。

作为另一个“哈希质量”的度量,我们假设在一个哈希表里面使用哈希函数。想象一个典型的负载系数为0.8的哈希表,这样的表一般有2的整数幂个bucket(即类似于bucketCount = NextPowerOfTwo(dataSetSize / 0.8))。如果我们把上述数据集放进哈希表,那么平均每个bucket有多少项呢?数字越低越好(1.0是理想情况):

 

第 11 段(可获 1.4 积分)

Hash Words avg bucket Filenames avg bucket Source avg bucket

xxHash32 1.241 1.338 1.422

xxHash64-32 1.240 1.335 1.430

xxHash64 1.240 1.335 1.430

SpookyV2-64 1.241 1.336 1.434

Murmur2A 1.239 1.340 1.430

Murmur3-32 1.242 1.340 1.427

CRC32 1.240 1.338 1.421

FNV 1.243 1.339 1.415

djb2 1.242 1.339 1.414

ZOMGBadHash 1.633 2.363 7.260

在这里所有哈希函数表现近似,除了 ZOMGBadHash ,正如我们所预期的,表现较差。

下一步

我没有测试一些最新的哈希函数(CityHash,MetroHash,FarmHash等)。我也没有测试使用了特殊的CPU指令的哈希函数(比如FarmHash函数的变体,能用在SSE4.2中增加了的CRC32指令等)。我会在未来做这些测试。

第 12 段(可获 1.29 积分)

总结

  • xxHash64很不错,尤其是运行在64比特的Intel CPU上。
  • 如果你使用128比特的哈希值长度,使用SpookyHash。当你使用不是Intel的64比特CPU时它一样表现良好(如XboxOne - AMD和iPhone6 - ARM吞吐率测试所述)。
  • 如果你使用一个32比特的哈希,而且在32比特的CPU或操作系统上,不要使用xxHash64或者SpookyHash!他们的64比特计算对于32比特的哈希值来说代价很高;使用xxHash32或者Murmur。
  • 对于短的数据/字符串,FNV和djb2的简单性带来的高性能难以超越。他们在短数据上表现同样优异。
  • 不要进行一些随机的比特操作,然后叫它哈希函数。哈希函数质量非常重要,而且我们有很多又快又好的哈希函数!
第 13 段(可获 1.69 积分)

文章评论