注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

中吴南顾惟一笑

成功法则就是那19个字

 
 
 

日志

 
 

经典的String Hash算法  

2010-12-03 19:44:39|  分类: R&D |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
设计高效算法往往需要使用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,不过已被中国学者找到碰撞检测的破解算法
  评论这张
 
阅读(6480)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017