面对现实,超越自己
逆水行舟,不进则退
posts - 269,comments - 32,trackbacks - 0
设计高效算法往往需要使用Hash表,O(1)级的查找速度是任何别的算法无法比拟的。
所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"pack"成一个整数,这个数称为Hash,当然,一个整数是无法对应一个字符串的。
所以Hash函数是Hash表最核心的部分,对于一个Hash函数,评价其优劣的标准应为随机性或离散性,即对任意一组标本,进入Hash表每一个单元(cell)之概率的平均程度,因为这个概率越平均,两个字符串计算出的Hash值相等hash collision的可能越小,数据在表中的分布就越平均,表的空间利用率就越高。

Hash表的构造和冲突的不同实现方法对执行效率也有一定的影响.

DJBHash是一种非常流行的算法,俗称"Times33"算法。Times33的算法很简单,就是不断的乘33,原型如下

hash(i) = hash(i-1) * 33 + str[i]

Time33在效率和随机性两方面上俱佳。

其它常用字符串哈希函数有:
BKDRHash,APHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等。BKDRHash和APHash也是比较优秀的算法。当然要根据具体应用选择合适的Hash算法,比如字符集的考虑。

APHash作者Arash Partow有一个页面很有参考价值,包括了各种Hash的介绍及代码。

http://www.partow.net/programming/hashfunctions/#RSHashFunction

Blizzard使用的算法比较精妙,被称为"One-Way Hash",并且在Hash表中使用了三个哈希值(一个用来确定位置,另外两个用来校验)。

MD5等加密算法也属于hash,不过已被中国学者找到碰撞检测的破解算法

本文转自:http://www.cppblog.com/humanchao/archive/2012/12/26/196690.html
posted on 2013-01-07 16:29 王海光 阅读(506) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理