MyException - 我的异常网
当前位置:我的异常网» C++ » 求大神指点迷津 —— 经典哈希函数SDBMHash解决办法

求大神指点迷津 —— 经典哈希函数SDBMHash解决办法

www.MyException.Cn  网友分享于:2013-12-27  浏览:11次
求大神指点迷津 —— 经典哈希函数SDBMHash
unsigned int SDBMHash(char *str)
{
   unsigned int hash = 0;

    while (*str)
    {
       //equivalent to: hash = 65599*hash + (*str++);
       hash = (*str++) + (hash << 6) + (hash << 16) - hash;

}
    return (hash &  0x7FFFFFFF);
}

请问 hash = (*str++) + (hash << 6) + (hash << 16) - hash;这个语句的作用是什么,这样计算出来的哈希地址很大,不会浪费很大的存储空间吗?
 return (hash &  0x7FFFFFFF);还有这个语句的功能是什么啊?
求高手指点!!!

------解决方案--------------------
大就对了,hash函数的目的就是用最简单高效的方式达到一个整数域的散列度。这个算法在低位域应该也有较好的散列度。最终,在hash表里还是需要&或者%来取某些位的。

hash算法一般都是经验性函数,有些能说出点数学价值,有些就是纯经验。一般选择哪个hash算法,考虑2个方面,一个方面是运算效率,一个方面是冲突率(一般是低位)。有时候需要自己去试试。

我曾经以为crc32的散列度非常好,当然这是不考虑计算效率的情况下。但是后来,发现当hash长度在2^N的时候,N的某些情况下冲突率非常的高。

至于说最后那行,确实不理解为啥。
------解决方案--------------------
没关系,大家只是在探讨。我的见解是hash算法首先要保障一定的效率。比如说,很多字符串hash只计算头几个字符和末尾几个字符。hash算法是为hash表服务的,hash表大多数操作需要首先算出key的hash然后&或者%计算出数组偏移,最后爬表。如果hash算法的开销过大,就算它再散列整体性能还是下降。

 (hash << 16) - hash

根据求值顺序你要从左向右看它的计算顺序。上面这段保障了高位的混杂度。

 (*str++) + (hash << 6)

这一段保障了低位的混杂度。一般我们都是会去&或者% hash值。这段代码尤其重要。

一般hash的结果都是unsigned int,所以我说hash的目的是用最小的开销达到一个整数域范围内的散列。
------解决方案--------------------
写错了,2了,从右向左读。
------解决方案--------------------
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
这句前面有个注释:
//equivalent to: hash = 65599*hash + (*str++);
这就是这个语句的作用
只用很大,有什么关系么?hash是个unsigned int类型,怎么算也就unsigned int那么大;
至于存储空间,算出了hash也不是直接用hash去索引地址,而是对桶大小求%,然后去索引。
至于(hash &  0x7FFFFFFF)
不过是把hash限制到31位而已(unsigned int有32位)

如果<< &这些操作的意思不懂,请另行自学。
------解决方案--------------------
这个吧,人家小盆友问,能解答咱们就解答下。

标准算法是没最后一行的,估计出去后用signed算的,加上这个。

自扩展hash大多还真不是用%的,都是2^N -1作为数组长度,一般用&。不过说太多就跑题了。
------解决方案--------------------
注释是关键,移位操作只是为了效率,65599是一个非常大的质数

文章评论

老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
旅行,写作,编程
旅行,写作,编程
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员的鄙视链
程序员的鄙视链
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我是如何打败拖延症的
我是如何打败拖延症的
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
我的丈夫是个程序员
我的丈夫是个程序员
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员和编码员之间的区别
程序员和编码员之间的区别
老程序员的下场
老程序员的下场
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
 程序员的样子
程序员的样子
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
10个调试和排错的小建议
10个调试和排错的小建议
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
一个程序员的时间管理
一个程序员的时间管理
中美印日四国程序员比较
中美印日四国程序员比较
鲜为人知的编程真相
鲜为人知的编程真相
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
那些争议最大的编程观点
那些争议最大的编程观点
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
如何成为一名黑客
如何成为一名黑客
程序员必看的十大电影
程序员必看的十大电影
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
代码女神横空出世
代码女神横空出世
程序员应该关注的一些事儿
程序员应该关注的一些事儿
每天工作4小时的程序员
每天工作4小时的程序员
为什么程序员都是夜猫子
为什么程序员都是夜猫子
编程语言是女人
编程语言是女人
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员都该阅读的书
程序员都该阅读的书
漫画:程序员的工作
漫画:程序员的工作
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有