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

Code@Pig Home

喜欢背着一袋Code傻笑的Pig .. 忧美.欢笑.记忆.忘却 .之. 角落

 
 
 

日志

 
 

[Game Dev] 也谈 Hash Func  

2008-03-07 17:42:22|  分类: 网游设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
hash func 是我们将 string 作为 map key 时常用的技巧。今天碰巧看到一个 webpage 上介绍了几个 hash func。

http://www.cse.yorku.ca/~oz/hash.html
文中作者推荐 djb2 hash func,号称是最快的 string hash algorithm 了。比目前项目中用的 Peter K. Pearson 还快上几分。

下面是两个算法对同一个字符串,运算了 9,999,999 次的耗时比较。不过自己仅仅做了性能测试,对于不同的字符串,哪个算法能得到更分散的值,就没测试了。(也不知道如何测试 - -#)

Peter K. Pearson
real    0m0.633s
user    0m0.633s
sys     0m0.001s

djb2
real    0m0.519s
user    0m0.519s
sys     0m0.000s

----------------------
将 djb2 补贴一下,以防万一,嘿嘿~

djb2

this algorithm (k=33) was first reported by dan bernstein many years ago in comp.lang.c. another version of this algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.
    unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;

while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;
}

------------------------------------------
其他资料
http://en.wikipedia.org/wiki/Hash_function
http://www.azillionmonkeys.com/qed/hash.html
  评论这张
 
阅读(752)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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