随笔 - 89  文章 - 118  trackbacks - 0
<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

设计高效算法往往需要使用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,不过已被中国学者找到碰撞检测的破解算法
posted on 2012-12-26 17:08 胡满超 阅读(3046) 评论(0)  编辑 收藏 引用 所属分类: 算法转载

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理