文档章节

选择一种优秀的HASH算法

mickelfeng
 mickelfeng
发布于 2017/09/07 16:28
字数 1171
阅读 40
收藏 0
点赞 0
评论 0

大约3年前,我在关于BloomFilter容量的研究一文中提到想研究一下各种HASH算法的速度。时至今日,一直没有动手去做。自我安慰地说,Premature Optimization是没有必要的,可能大多数HASH算法都差不多吧。但最近碰上了一个O(2n)问题,为解决它,我必须去设计一个尽可能高效的BloomFilter和HASH对象。HASH算法的选择就变得相当重要了。

 

首先,我做了一个Literature Review,研究了以下资料:

  • http://en.wikipedia.org/wiki/Jenkins_hash_function
    • http://www.burtleburtle.net/bob/hash/doobs.html
    • http://www.burtleburtle.net/bob/hash/spooky.html
  • http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash
    • http://www.isthe.com/chongo/tech/comp/fnv/index.html
  • http://en.wikipedia.org/wiki/CityHash
  • http://en.wikipedia.org/wiki/MurmurHash
  • http://programmers.stackexchange.com/a/145633/108318
  • http://www.drdobbs.com/parallel/fast-parallelized-crc-computation-using/229401411
  • http://stackoverflow.com/questions/17645167/implementing-sse-4-2s-crc32c-in-software

根据上述资料,备选的HASH可能是:

  • CityHash
  • SpookyHash
  • MurmurHash3
  • FNV Hash
  • CRC32/SSE4.2

以上绝大多数HASH的“官方”版本是C或者C++的。但我使用的语言是FreePascal。重写这些HASH是个不小的工作量。由于我开始入手研究的是lookup3这个HASH(也就是Spooky作者写的一个早期版本),加上FP已经内建了CRC32支持,我选择了以下几个算法进行测试:

  • lookup3(我这次研究的出发点)
  • crc32(FreePascal内置支持)
  • fnv1a(改写足够简单)
  • murmur2(以前有现成的Pascal代码)
  • crc128(FreePascal内置支持,可能需要128bit的HASH)
  • md5(同上)
  • sha1(同上)

执行循环一千万次后的结果如下(单位:秒):

  • lookup3:  3.027
  • crc32:  2.810
  • fnv1a:  4.185
  • murmur2:  2.128
  • crc128:  6.028
  • md5:  5.698
  • sha1:  7.692

对以上测试结果,我的解读如下:

  1. 测试结果只能作相对比较,因为测试程序的编写、测试数据的长度等等都是非常随意的。我的这次测试使用的是10个长整数,也就是40个字节的数据,共一千万个,使用EpikTimer对每次哈希运算进行计时然后累加。这样做可能引入EpikTimer本身带来的损耗,但不影响结论的相对比较价值。
  2. 32-bit的Hash中Murmur2的性能最好,依此推断,Murmur3的性能可能还要好一点。
  3. CRC32的性能相当不错,从简便性上看,它应该是最优选择了,因为FP天然就支持了。
  4. FP的CRC32使用了查表法,基本上是软件所能达到的CRC32最好性能了。但肯定比用SSE4.2的硬件指令的要慢。另外听说CityHash也会利用硬件特性来提速,这里就不加以测试了。
  5. 128-bit的算法“单位速度”明显好于32-bit的。例如MD5算法按32-bit的速度算只需1.507秒,远高于任何32-bit算法。在BloomFilter应用中可以将大HASH切分成若干小HASH使用,因此应该尽可能选择“单位速度”高的算法。
  6. 所测试的算法中单位速度最高的几个依次是:MD5、CRC128、SHA1、Murmur2、CRC32。综合考虑性能和使用的方便性、各种场合下的不同需求等,应使用FP内建支持的MD5、SHA1、Murmur2(或Murmur3)三种算法,若对速度要求不是很高,也可以使用CRC32。

 

后记

 

本文发布后一天,我继续进行HASH性能的研究,找到了smhasher项目。虽然它包含了详细的测试数据,但我还是想自己测一下。于是改写了它里面的MurmurHash3代码。得出的结果如下:

  1. Murmur3的32bit版本性能介乎CRC32和Murmur2之间,为2.5秒多一点。
  2. Murmur3的128bit版本性能惊人,比32bit更快一点,也就是说单位速度达32bit版本的4到5倍,可惜我改写的代码中还有BUG,和C的原版计算出来的值不同。暂时不能用。
  3. 从这次研究我的经验教训是,测试程序必须自己写而不能依赖他人公开的测试。以我这次为例,性能和公开可以查询到的结果有比较大的不同的原因我认为主要不是Pascal和C的区别,而是数据特性和统计方法所决定的。不管这种猜测是否正确,最后反应到实际应用中还是以硬的耗时指标说话,而不是每个hash运算消耗多少个CPU指令循环这样高深而学术化的衡量。

此次测试后,我仍然决定在未来的项目中优先使用FP内置的CRC32/MD5/SHA1系列算法。但会考虑研究测试一下基于SSE4.2指令集的版本,看看是否有性能优势。

© 著作权归作者所有

共有 人打赏支持
mickelfeng

mickelfeng

粉丝 226
博文 963
码字总数 548356
作品 0
成都
高级程序员
双数组字典树关键词查询匹配和替换

大家在进行关键词匹配和替换的时候都是用的什么算法?很多人都可能有这样的需求,比如聊天文本中的敏感词替换、html文本中的关键词加超链接等。不深入技术算法和时刻关注程序性能的人来说,就...

BoXuan ⋅ 2016/12/24 ⋅ 1

PHP中HASH函数的优化技巧

Hash数据结构是一种非常常见的数据结构,作为一个程序员,你可能每天都在和它接触, 尽管很多时候你可能没有意识到。Hash在PHP内核中扮演了非常重要的角色,数组、变量作用域、函数参数列表等...

ChefXu ⋅ 2015/12/04 ⋅ 4

索引初识一 MySql

1 mysql索引类型【主要分4类索引】 创建索引: 1.添加PRIMARY KEY(主键索引) 【主键:一种唯一性索引,必须指定为primary key 】 mysql> ALTER TABLE ADD PRIMARY KEY ( ) 2.添加UNIQUE(唯...

技术林工 ⋅ 2017/05/18 ⋅ 0

哈希结构是如何找到相对应的键-值对?

哈希结构作为一种抽象数据结构,Hash表的实现思路如下: 通过某种算法,在 键--值对的存储地址和 键--值对中的key之间,建立一种映射,使得每一个key,都有一个确定的存储地址于之对应。这种...

付翔 ⋅ 2009/09/10 ⋅ 0

Message Authentication Code_消息认证码算法

Message Authentication Code_消息认证码算法 内容来源于网络 部分内容摘自博客:http://blog.csdn.net/zzminer/article/details/8574287 MAC算法结合了MD5和SHA算法的优势,并加入密钥的支持...

秋风醉了 ⋅ 2014/07/14 ⋅ 1

hash算法总结收集

hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),这样可以快速在数组等条件中里...

GeorgeBrown ⋅ 2015/06/06 ⋅ 0

SQL Server Join方式

0.参考文献 Microsoft SQL Server企业级平台管理实践 看懂SqlServer查询计划 1.测试数据准备 参考:Sql Server中的表访问方式Table Scan, Index Scan, Index Seek 这篇博客中的实验数据准备。...

嗯哼9925 ⋅ 2017/12/21 ⋅ 0

深入HashCode方法

为什么HashCode对于对象是如此的重要? 一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的Hash算法相比还不能叫真正的算法,它如何实现它,不仅仅是程序员的编程水平...

teacheryang ⋅ 2010/09/17 ⋅ 0

为什么HashCode对于对象是如此的重要?

为什么HashCode对于对象是如此的重要? 一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的Hash算法相比还不能叫真正的算法,它如何实现它,不仅仅是程序员的编程水平...

唐玄奘 ⋅ 2017/12/05 ⋅ 0

为什么HashCode对于对象是如此的重要?

为什么HashCode对于对象是如此的重要? 一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的Hash算法相比还不能叫真正的算法,它如何实现它,不仅仅是程序员的编程水平...

青夜之衫 ⋅ 2017/12/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

spring Email

使用spring发Email其实就是使用spring自己封装携带的一个javamail.JavaMailSenderImpl类而已。这个类可以当一个普通的java对象来使用,也可以通过把它配置变成spring Bean的方式然后注入使用...

BobwithB ⋅ 22分钟前 ⋅ 0

spark 整理的一些知识

Spark 知识点 请描述spark RDD原理与特征? RDD全称是resilient distributed dataset(具有弹性的分布式数据集)。一个RDD仅仅是一个分布式的元素集合。在Spark中,所有工作都表示为创建新的...

tuoleisi77 ⋅ 25分钟前 ⋅ 0

思考

时间一天天过感觉自己有在成长吗?最怕的是时光匆匆而过,自己没有收获!下面总结下最近自己的思考。 认识自己 认识另一个自己,人们常说要虚心听取别人意见和建议。然而人往往是很难做到的,...

hello_hp ⋅ 26分钟前 ⋅ 0

IT行业的变革就像世界杯德国对战墨西哥一样难以预测[图]

最近在观看世界杯,尤其是昨天的比赛,上一届卫冕冠军德国队居然0:1告负墨西哥,这创造了历史,首先是墨西哥从来没赢过德国队,其次是德国队36年来首站没输过,再差也是打平,而这次,德国队...

原创小博客 ⋅ 45分钟前 ⋅ 0

解决CentOS6、7,/etc/sysconfig/下没有iptables的问题

一、Centos 6版本解决办法: 1.任意运行一条iptables防火墙规则配置命令: iptables -P OUTPUT ACCEPT 2.对iptables服务进行保存: service iptables save 3.重启iptables服务: service ...

寰宇01 ⋅ 55分钟前 ⋅ 2

数据库备份和恢复

备份:mysqldump -u root -p 数据库>磁盘路径 恢复:mysql -u root -p 数据库<sql脚本的磁盘路径

anlve ⋅ 今天 ⋅ 0

发生了什么?Linus 又发怒了?

在一个 Linux 内核 4.18-rc1 的 Pull Request 中,开发者 Andy Shevchenko 表示其在对设备属性框架进行更新时,移除了 union 别名,这引发了 Linus 的暴怒。 这一次 Linus Torvalds 发怒的原...

问题终结者 ⋅ 今天 ⋅ 0

在树莓派上搭建一个maven仓库

在树莓派上搭建一个maven仓库 20180618 lambo init 项目说明 家里有台树莓派性能太慢。想搭建一个maven私服, 使用nexus或者 jfrog-artifactory 运行的够呛。怎么办呢,手写一个吧.所在这个...

林小宝 ⋅ 今天 ⋅ 0

Spring发展历程总结

转自与 https://www.cnblogs.com/RunForLove/p/4641672.html 目前很多公司的架构,从Struts2迁移到了SpringMVC。你有想过为什么不使用Servlet+JSP来构建Java web项目,而是采用SpringMVC呢?...

onedotdot ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部