关于散列函数的构造问题
本帖最后由 代码农民 于 2016-11-14 17:37 编辑见 《数据结构与算法分析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 + 27*key + 729*key) % tableSize;
}
以下是我看不懂的段落，请大家教教我、、、、
“这个hash函数假设key至少有3个字符。值27表示英文字母表的字母个数外加一个空格，而729是27的平方。虽然该函数只考察了前三个字符，但是，假如字符出现的概率是随机的，而表的大小还是1 0007，那么我们就会得到一个合理的均衡分布。”
引号中的话实在搞不明白是什么意思。。。。第二个版本的函数是引号中的含意构造的。。。我一直不理解(key + 27*key + 729*key)到底是什么意思。。
可以理解为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 发表于 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次 本帖最后由 代码农民 于 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），而且空格与字母也不相临（并且还有大小写的区分）。
为了理解您回复里的“权重”二字的含义，我百度了，但还是不能解开我的疑惑...
只有高中文化，所以里面有些句子可能表达的不够专业...还望您能见谅...
家人催了..先下了 代码农民 发表于 2016-11-10 22:15
很感谢您，美女。
你的意思我理解了。
其中有些地方还是不太明白，还希望您能不吝赐教...
您要的，只要一道转换就得到了：
int result = key==0x32?0:key-'A'+1;
把result分别代回到第二个函数里的key,key,key一样满足hash table的需求，同时也
满足您的需求，想想为何不做转换？因为不转换就可以满足hash table的需求，何必多费工夫去转？ 呆鸭 发表于 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 16:28 编辑
呆鸭 发表于 2016-11-11 09:20
您要的，只要一道转换就得到了：
int result = key==0x32?0:key-'A'+1;
把result分别代回到第二个函数 ...
似乎绕过来这个弯了，我来说一下我的看法。
类比十六进制表示方法，比如 b 1 0 0 H 这个十六进制数, 其实就是[ b ](*16^3)(*16^2)(*16^1)(*16^0)。在这里面我们规定了各个符号的值（比如b是11）。
而这些规定都是人为的，我可以按照我的规定让符号b是任何值，也可以让符号0成为任何值，等等。最终的结果是1个16的倍数的数再加上一个余数（这个余数可能比16大，也可能比16小，这取决于对符号定义的值）。
单看b100这几个符号，可以是任意进制的格式的表示方法，比如可以让这些符号的值按27进制计算。即[ b ](*27^3)(*27^2)(*27^1)(*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进制 ...
很感谢，我的想法回复给呆鸭了，还望指正。 本帖最后由 代码农民 于 2016-11-11 16:50 编辑
书上最后的一个散列函数如下：
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的数，在计算机运算是最快的，不用一般的乘法运算，直接往 ...
很感谢你
页:
[1]