中法所得到的哈希地址与关键字的每一位相关，使得哈希地址具有较好的分散性。Р例如：已知表2.3中的关键字（八进制）如下，假设哈希表的长度为512。Р由于512=(1000)8，该哈希表的地址码长度为3，因此，可取中间3位作为每个记录的哈希地址。Р表2.3Р关键字Р（关键字）РHash地址Р0100Р0010000Р010Р1100Р1210000Р210РР1160Р1370400Р440Р2061Р4310541Р310Р2163Р4745651Р745Р…Р…Р…Р由此可见平方取中法适合于事先不了解关键字的全部情况，或者 关键字较短的情况。Р下面给出平方取中法的哈希函数：Р//平方取中法Hash函数，结设关键字值32位的整数Р//Hash函数将返回*key的中间10位Рint Hash(int key)Р{Р//计算key的平方Рkey *=key;Р//去掉第11位Рkey >>=11;Р//返回第10位（即key*key的中间10位）Рreturn key %1024Р}Р2.3.4 折叠法Р折叠法是按照哈希表的地址码位数，将关键字分割成位数相同的几段（最后一段可能少些），然后将这几部分相加，得到的和即为哈希地址。Р例如：假设哈希表的地址码位数为3，关键字key为：220。Р按照地址码位数，将关键字每3位分段，得到：723 203 241 112 20。然后，将他们叠加。则可得，H(key)=299。Р 所以折叠法适合于关键字较长，地址码位数较小，同时关键字中每位的取值又较扎堆的情况。Р2.3.5 除留余数法Р除留余数法的哈希函数定义为：H(key)=key MOD p（p ≤m ），其中，m为哈希表的长度，p是小于等于m的正整数。Р例如，对2.4中的关键字，如果取p=29Р 表2.4
全文预览
