读书人

请问数据结构中除留余数法的一个有关问

发布时间: 2012-04-22 18:34:46 作者: rapoo

请教数据结构中除留余数法的一个问题?
这段内容按套路来说应该发在数据结构区的,但是那里实在有点冷清,于是乎我有想到了C++专区,想到了以前那些曾经给予我帮助的一些高手,如tomxxx(具体拼写想不起来了)还有星羽等。总感觉C++专区给人的感觉很温暖。

好了,言归正传。我在看严蔚敏版《数据结构》时,255页有一些话我不太明白,还希望大家指点一下。

5、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即
H(key) = key MOD p, p<=m

<下面内容不懂>
值得注意的时,在使用除留余数法时,对p的选择很重要。若p选的不好,容易产生同义词。
假设取标识符在计算机中的二进制表示为它的关键子(标识符中每个字母均用两位八进制数表示),然后对p=2的6次访取模。这个运算在计算机中只要移位便可实现,将关键字左移直至只留下最低的6位二进制。这等于将关键字的所有高位值都忽略不计。因而使得所有最后一个字符相同的标识符,如al,il,templ,cpl等均成为同义词。



能不能把具体的过程帮我详细地描述一下,谢谢!!!

[解决办法]
取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即

H(key) = key MOD p, p <=m

解释

key: 关键字
m : 哈希表表长
p : 小于等于 m 的一个 数

哈希地址 H =key % p (即key 被 p 除的余数)

假设取标识符在计算机中的二进制表示为它的关键子(标识符中每个字母均用两位八进制数表示),然后对p=2的6次访取模。这个运算在计算机中只要移位便可实现,将关键字左移直至只留下最低的6位二进制。这等于将关键字的所有高位值都忽略不计。因而使得所有最后一个字符相同的标识符,如al,il,templ,cpl等均成为同义词。

解释

每个字母用两位八进制数表示 : 即 一个八进制数(0-7) 占 3 位, 则一个 字符 占 6 位

则 al 占 12 位,il 占 12 位,templ 占30 位,cpl 占 18位,

取 p 为 2的6 次方,对上面这些关键字 求余 则结果为 关键字的末6 位,即 'l' 的二进制表示(两个八进制数)

因而 上面几个 关键词 都是同义词,具有相同的哈希地址.所以这个 p 是不好的

读书人网 >VC/MFC

热点推荐