哈希算法篇 |
您所在的位置:网站首页 › 哈希函数的p怎么选 › 哈希算法篇 |
之前写了个布隆过滤器,用于千万级新闻 url 去重。如果不了解可以看这里: 布隆过滤器:公众号地址随时看 如果建立写了布隆过滤器,大家在面试的时候,肯定都会被问到Hash的知识,以下是面试场景: 你用的哈希函数是什么?你还知道哪些哈希函数? 文章目录 前言多种哈希函数介绍代码C代码Java代码:BKDR HashELF Hash详细分析 前言本文继上一篇布隆过滤器续写 : 布隆过滤器:公众号地址随时看 多种哈希函数介绍常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。 常用字符串哈希函数有 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash 等等。对于以上几种哈希函数,我对其进行了一个小小的评测。
经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。 在信息修竞赛中,要本着易于编码调试的原则,个人认为BKDRHash是最适合记忆和使用的。 代码 C代码附:各种哈希函数的C语言程序代码 unsigned int SDBMHash(char *str) { unsigned int hash = 0; while (*str) { // equivalent to: hash = 65599*hash + (*str++); hash = (*str++) + (hash |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |