关于散列函数的构造问题

代码农民

见 《数据结构与算法分析C语言描述—第二版》 112页：
        为 关键字是字符串 构造的几个散列函数：（假设表的大小是1 0007）
        第一种版本：

unsigned int
hash(const char *key, unsigned int tableSize)  
{  
    unsigned int hashVal;  
  
    while(*key != '\0')  
        hashVal += *key++;  
  
    return (hashVal % tableSize);  
}  

         

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

        第二种版本：

unsigned int
hash(const char *key, unsigned int tableSize)  
{  
    return (key[0] + 27*key[1] + 729*key[2]) % tableSize;  
}  

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

引号中的话实在搞不明白是什么意思。。。。第二个版本的函数是引号中的含意构造的。。。我一直不理解(key[0] + 27*key[1] + 729*key[2])到底是什么意思。。

zhy755788055

可以理解为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，所以比较均衡

zhy755788055

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次

代码农民

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），而且空格与字母也不相临（并且还有大小写的区分）。

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

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

家人催了..先下了

呆鸭

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

您要的，只要一道转换就得到了：
int result = key[i]==0x32?0:key[i]-'A'+1;
把result分别代回到第二个函数里的key[0],key[1],key[2]一样满足hash table的需求，同时也
满足您的需求，想想为何不做转换？因为不转换就可以满足hash table的需求，何必多费工夫去转？

zhy755788055

呆鸭 发表于 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倍？这个没有研究。

代码农民

呆鸭 发表于 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)。而这个范围能完全覆盖散列表（冲突了再说）。
   不知道我分析的对不对...还望指正....

代码农民

zhy755788055 发表于 2016-11-11 14:33
27进制就是里面有27个不同标志，如8进制里有0-7共八个，逢8进1。这8个标志是等概率分布的。我们的27进制 ...

很感谢，我的想法回复给呆鸭了，还望指正。

代码农民

书上最后的一个散列函数如下：

unsigned int hash(const char *key,unsigned int tableSize)  
{  
    unsigned int hashVal;  
  
    while(*key != '\0')  
        hashVal = (hashVal << 5) + *key++;  
  
    return (hashVal % tableSize);  
}  

如果以上我的分析正确，那么3个32进制数（32^3个）当然也可以完全覆盖散列表，用32而不用27，书上说是为了计算方便，这个式子先放这，因为这里面还有一些疑问。

呆鸭

代码农民 发表于 2016-11-11 16:44
书上最后的一个散列函数如下：

用32而不用27，书上说是为了计算方便
乘以2^n的数，在计算机运算是最快的，不用一般的乘法运算，直接往左移n位即可，速度远比一般乘法运算的速度快。

代码农民

呆鸭 发表于 2016-11-11 17:00
用32而不用27，书上说是为了计算方便
乘以2^n的数，在计算机运算是最快的，不用一般的乘法运算，直接往 ...

恩，这个我能理解。
但是hashVal只有16位...书上说加号可以用异或运算符来代替，我有点不能理解。
而且对于  hashVal = (hashVal << 5) ^ *key++; 这条语句的执行,会把hashVal的位数一直往左推，它的结果与hashVal*32的结果会一样吗.....

代码农民

呆鸭 发表于 2016-11-11 17:00
用32而不用27，书上说是为了计算方便
乘以2^n的数，在计算机运算是最快的，不用一般的乘法运算，直接往 ...

很感谢你