设计高效算法往往需要使用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/#RSHashFunctionBlizzard使用的算法比较精妙，被称为"One-Way Hash"，并且在Hash表中使用了三个哈希值(一个用来确定位置，另外两个用来校验)。MD5等加密算法也属于hash，不过已被中国学者找到碰撞检测的破解算法
本文转自：http://www.cppblog.com/humanchao/archive/2012/12/26/196690.html
posted on 2013-01-07 16:29
王海光 阅读(1755)
评论(0) 编辑 收藏 引用 所属分类:
算法