HASH GAME - Online Skill Game GET 300

　　如果事先知道关键字集合,并且每个关键字的位数比哈希表的地址码位数多时,可以从关键字中选出分布较均匀的若干位,构成哈希地址。例如,有80个记录,关键字为8位十进制整数d1d2d3…(7d8)如哈希表长度取为100,则哈希表的地址空间为,0~99。假设经过分析,各关键字中d4和d7的取值分布较均匀,则哈希函数为,H(key)=H(d1d2d3…,7d8)=d4d7。例如,H(81346532)=43,H(81301367)=06。相反,假设经过分析,各关键字中d1和d8的取值分布极不均匀,d1都等于5,d8都等于2,此时,如果哈希函数为,H(key)=H(d1d2d3…,7d8)=d1d8,则所有关键字的地址码都是52,显然不可取。

　　这种方法是按哈希表地址位数将关键字分成位数相等的几部分,最后一部分可以较短,,然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加,折叠法是从一端向另一端沿分割界来回折叠,奇数段为正序,偶数段为倒序,,然后将各段相加。例如,key=65,哈希表长度为1000,则应把关键字分成3位一段,在此舍去最低的两位65,分别进行移位叠加和折叠叠加,求得哈希地址为105和907,如下图所示。

　　从上述例子可以看出,线性探测再散列容易产生“二次聚集” , 即在处理同义词的冲突时又导致非同义词的冲突。 例如, 当表中 i , i+1 , i+2三个单元已满时, 下一个哈希地址为 i ,或i+1 ,或i+2,或i+3的元素,都将填入 i+3这同一个单元,而这四个元素并非同义词。线性探测再散列的优点是, 只要哈希表不满, 就一定能找到一个不冲突的哈希地址, 而二次探测再散列和伪随机探测再散列则不一定。