鱼C论坛

 找回密码
 立即注册
查看: 2724|回复: 11

关于散列函数的构造问题

[复制链接]
发表于 2016-11-9 07:36:02 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 代码农民 于 2016-11-14 17:37 编辑

见 《数据结构与算法分析C语言描述—第二版》 112页:
        为 关键字是字符串 构造的几个散列函数:(假设表的大小是1 0007)
        第一种版本:
  1. unsigned int
  2. hash(const char *key, unsigned int tableSize)  
  3. {  
  4.     unsigned int hashVal;  
  5.   
  6.     while(*key != '\0')  
  7.         hashVal += *key++;  
  8.   
  9.     return (hashVal % tableSize);  
  10. }  

  11.          
复制代码

这个算法比较简单,但是对表的利用率不高。

        第二种版本:
  1. unsigned int
  2. hash(const char *key, unsigned int tableSize)  
  3. {  
  4.     return (key[0] + 27*key[1] + 729*key[2]) % tableSize;  
  5. }  
复制代码


以下是我看不懂的段落,请大家教教我、、、、
“  这个hash函数假设key至少有3个字符。值27表示英文字母表的字母个数外加一个空格,而729是27的平方。虽然该函数只考察了前三个字符,但是,假如字符出现的概率是随机的,而表的大小还是1 0007,那么我们就会得到一个合理的均衡分布。”

引号中的话实在搞不明白是什么意思。。。。第二个版本的函数是引号中的含意构造的。。。我一直不理解(key[0] + 27*key[1] + 729*key[2])到底是什么意思。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-11-9 19:23:06 | 显示全部楼层
可以理解为27进制,第0位的权重是27^0, 第1位为27^1,第2位为27^2,就像0b111二进制表示7也就是1*2^0+1*2^1+1*2^2一样。前三位数字组成的27进制的数字正好覆盖了所有的27进制里面的三位数,总数为27^4-1,比10007大,为53余1,所以比较均衡
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-11-9 19:28:11 | 显示全部楼层
zhy755788055 发表于 2016-11-9 19:23
可以理解为27进制,第0位的权重是27^0, 第1位为27^1,第2位为27^2,就像0b111二进制表示7也就是1*2^0+1*2^1+ ...

余1069,比10007小很多,可以理解为均匀覆盖10007中的数字,碰撞平均53次
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-10 22:15:48 | 显示全部楼层
本帖最后由 代码农民 于 2016-11-10 22:22 编辑
zhy755788055 发表于 2016-11-9 19:28
余1069,比10007小很多,可以理解为均匀覆盖10007中的数字,碰撞平均53次


很感谢您,美女。
你的意思我理解了。
其中有些地方还是不太明白,还希望您能不吝赐教...

二进制单元(0,1)是满2向高位进1,十进制单元(0,1,2,3,4,5,6,7,8,9)是满10向高位进1,而它们的单元里的数都是小于进制的数(比如小于2,10),而且各个相临都差1。

在第二个函数里,我们用的是27进制,按照上述我的理解....27进制单元里的数不是都该小于27么...而字符串中的字符编码最低也是空格(32H),而且空格与字母也不相临(并且还有大小写的区分)。

为了理解您回复里的“权重”二字的含义,我百度了,但还是不能解开我的疑惑...

只有高中文化,所以里面有些句子可能表达的不够专业...还望您能见谅...

家人催了..先下了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-11-11 09:20:08 | 显示全部楼层
代码农民 发表于 2016-11-10 22:15
很感谢您,美女。
你的意思我理解了。
其中有些地方还是不太明白,还希望您能不吝赐教...

您要的,只要一道转换就得到了:
int result = key==0x32?0:key-'A'+1;
把result分别代回到第二个函数里的key[0],key[1],key[2]一样满足hash table的需求,同时也
满足您的需求,想想为何不做转换?因为不转换就可以满足hash table的需求,何必多费工夫去转?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-11-11 14:33:36 | 显示全部楼层
呆鸭 发表于 2016-11-11 09:20
您要的,只要一道转换就得到了:
int result = key==0x32?0:key-'A'+1;
把result分别代回到第二个函数 ...

27进制就是里面有27个不同标志,如8进制里有0-7共八个,逢8进1。这8个标志是等概率分布的。我们的27进制里面,他说了每个字符是等概率的,就是为了表达这个情况。现在的问题就是如何把27个ascii码等概率的表示就行了,定义空格为0,a为1,就行了,这个只是一个规定。就是呆鸭说的这个算法。书上写的算法是吧这个结果放大了吗?放到了0x32倍?这个没有研究。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-11 16:26:13 | 显示全部楼层
本帖最后由 代码农民 于 2016-11-11 16:28 编辑
呆鸭 发表于 2016-11-11 09:20
您要的,只要一道转换就得到了:
int result = key==0x32?0:key-'A'+1;
把result分别代回到第二个函数 ...


  似乎绕过来这个弯了,我来说一下我的看法。

  类比十六进制表示方法,比如 b 1 0 0 H 这个十六进制数, 其实就是[ b ](*16^3)  [1](*16^2)  [0](*16^1)  [0](*16^0)。在这里面我们规定了各个符号的值(比如b是11)。
  而这些规定都是人为的,我可以按照我的规定让符号b是任何值,也可以让符号0成为任何值,等等。最终的结果是1个16的倍数的数再加上一个余数(这个余数可能比16大,也可能比16小,这取决于对符号定义的值)。
  单看b100这几个符号,可以是任意进制的格式的表示方法,比如可以让这些符号的值按27进制计算。即[ b ](*27^3)  [1](*27^2)  [0](*27^1)  [0](*27^0)。而这个值是4个27进制数所能表示的取值范围中的一个值。

  根椐上面的想法,在那个散列函数中,3个27进制的格式符号串的取值范围是由这个符号表中的最大值决定,即  [符号表里的最大值](*27^2)+ [符号表里的最大值](*27^1)+ [符号表里的最大值](27^0)。而这个范围能完全覆盖散列表(冲突了再说)。
   不知道我分析的对不对...还望指正....
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-11 16:27:38 | 显示全部楼层
zhy755788055 发表于 2016-11-11 14:33
27进制就是里面有27个不同标志,如8进制里有0-7共八个,逢8进1。这8个标志是等概率分布的。我们的27进制 ...

很感谢,我的想法回复给呆鸭了,还望指正。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-11 16:44:45 | 显示全部楼层
本帖最后由 代码农民 于 2016-11-11 16:50 编辑

书上最后的一个散列函数如下:
  1. unsigned int hash(const char *key,unsigned int tableSize)  
  2. {  
  3.     unsigned int hashVal;  
  4.   
  5.     while(*key != '\0')  
  6.         hashVal = (hashVal << 5) + *key++;  
  7.   
  8.     return (hashVal % tableSize);  
  9. }  
复制代码


如果以上我的分析正确,那么3个32进制数(32^3个)当然也可以完全覆盖散列表,用32而不用27,书上说是为了计算方便,这个式子先放这,因为这里面还有一些疑问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-11-11 17:00:00 | 显示全部楼层
代码农民 发表于 2016-11-11 16:44
书上最后的一个散列函数如下:

用32而不用27,书上说是为了计算方便
乘以2^n的数,在计算机运算是最快的,不用一般的乘法运算,直接往左移n位即可,速度远比一般乘法运算的速度快。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-11 17:25:59 | 显示全部楼层
呆鸭 发表于 2016-11-11 17:00
用32而不用27,书上说是为了计算方便
乘以2^n的数,在计算机运算是最快的,不用一般的乘法运算,直接往 ...


恩,这个我能理解。
但是hashVal只有16位...书上说加号可以用异或运算符来代替,我有点不能理解。
而且对于  hashVal = (hashVal << 5) ^ *key++; 这条语句的执行,会把hashVal的位数一直往左推,它的结果与hashVal*32的结果会一样吗.....
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-11-14 17:36:56 | 显示全部楼层
呆鸭 发表于 2016-11-11 17:00
用32而不用27,书上说是为了计算方便
乘以2^n的数,在计算机运算是最快的,不用一般的乘法运算,直接往 ...

很感谢你
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 12:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表