NABHash介绍及原理

项目地址

github.com/mengzhuo/nabhash

什么是NABHash？

NABHash 是一种 超级快的 基于AES的非密码学安全哈希算法（Hash Algorithm)

有以下特点：

• 速度快，Intel i7 处理器上（2.6GHz 支持AES硬件）可达到40GB/s处理速度
• 128 位哈希值，不像其他为了快速的哈希算法，产生的哈希值长度过短，NABHash与sha1长度相当。
• 通过所有了SmHasher的测试，雪崩性和分布性良好。
• 针对大数据，大于1024字节时就有优良性能。
• 支持X86、ARMv8平台

性能对比图


可以看到，在65536字节时，NABHash的速度是xxhash、murmur3这些常见快速哈希算法的10倍左右。

为啥可以这么快？

因为“简约”。

一般哈希算法是使用加法、异或、移位完成的（Shift Add XOR）
而哈希算法为了满足雪崩性和分布性，会多计算几轮，导致就算使用SIMD技术，也无可避免性能下降。

这就是NABHash优化的地方，NABHash对于一个16字节数据块，在Intel平台上仅仅使用了1个指令：

AESENC

即AES加密。而选择AES的主要原因是，现在主流的CPU都支持了AES硬件加速（ARM、PPC），而SHA系列虽然有硬件支持，但指令复杂，往往一个数据块还需要多个指令才能完成计算。

主要流程可见下图：

相当于用数据不停地加密初始向量值（0x5A827999 0x6ED9EBA1），最终得到一个哈希值。

可能有些小朋友就会问了，为啥初始向量是这个值，是随机生成的么？不，这是sha1的初始key值。

最后，为啥叫NABHash

因为这是Non-Crypto-Safe AES Based Hash，简写NABHash，基于AES的非密码学安全哈希算法。