返回

看了Wiki里面的一个hash代码,试了一下发现很容易发生碰撞例如"daming" 和 "kuking"这两个的Hash值就是一样的这个是怎么回事情?

unsigned long hash(const char *name,size_t len){ unsigned long h=(unsigned long)len; size_t step = (len>>5)+1; for (size_t i=len; i>=step; i-=step) h = h ^ ((h<<5)+(h>>2)+(unsigned long)name[i-1]); return h;}

名字: 自动排版 密码:

• 我觉得单个冲突的案例说明不了什么太多问题，尤其这个 hash 函数的目标是计算速度。有更详尽的测试吗？"比如一个比较大规模的字典里冲突的概� 『More』 - 回复 | (1047) | 云风 | 2006-04-07 02:10:18

  • 没记错的话，lua使用的是这个吧？ - 回复 | (1062) | dawndu | 2006-04-15 10:50:07

    • lua 用的正是这个，wiki 上标明了 :D - 回复 | (1063) | 云风 | 2006-04-15 11:05:55

  • 谢谢回复, 后来试了好几个hash算法, 发现冲突的概率和这个算法差不多.测试了5个hash算法(都是返回一个32位的整形), 一共133557 个字符串,冲突的字符串个� 『More』 - 回复 | (1048) | kokk | 2006-04-07 08:43:32

    • wiki 顶上可以登陆，输入用户名和密码确认就可以注册。注册后，留言菜单就出来了。 - 回复 | (1049) | 云风 | 2006-04-08 04:32:04

      • 上面我测试的结果是错误的,今天突然发现里面有9000字符串是重复的所以才会有这么多相冲突重新测试了一下124289条没有重复全大写字符串你那个算法有7条是冲突的,这样冲突的几率还是很小的 - 回复 | (1053) | kokk | 2006-04-10 06:05:00