一道哈希表用二次探测再散列法解决冲突的有关问题
一道哈希表用二次探测再散列法解决冲突的问题
设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】
A．8 B．3 C．5 D．9
答案为A,为什么我计算出来是D呢?
我的计算步骤如下:
15，38，61，84用哈希函数H(key)=key%11计算后得地址:4,5,6,7
49计算后为5,发生冲突.
用二次探测再散列法解决冲突:
1:(key+1^2)%11=(49+1)%11=6,仍然发生冲突.
2:(key-1^2)%11=(49-1)%11=4,仍然发生冲突.
3:(key+2^2)%11=(49+4)%11=9,不再发生冲突.
得出结果为D
------解决方案--------------------
答案A是正确的
(key+1^2)%14=(49+1)%14=6,仍然发生冲突.
Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列
这里m=14 不是11
------解决方案--------------------
在《算法导论》中，Hash函数实现采用取余法时，哈希表长m即为除数p。一般根据装载因子（开放地址法我一般选0.7，链接法我一般选2-3左右，欢迎大家给我更合理的值）选取合适的槽的大小，通常为一个不接近2的整数次幂的质数。如：53, 97, 193, 389, 769, 1543, 3079, 6151,
12289, 24593, 49157, 98317,
196613, 393241, 786433, 1572869,
3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189,
805306457, 1610612741
参考严蔚敏老师书上写的
用二次探测再散列法处理冲突： Hi = (H(key) + di)MOD m; 其中m为哈希表长度
我做题过程如下：
插入前15，38，61，84的H(key)分别为:4,5,6,7 存放地址为4,5,6,7
49的H(key)为5,发生冲突.
用二次探测再散列法解决冲突:
1:(5+1^2)%14=(5+1)%14=6,仍然发生冲突.
2:(5-1^2)%14=(5-1)%14=4,仍然发生冲突.
3:(5+2^2)%14=(5+4)%11=9,不再发生冲突.
得出结果为D。 和楼主一样
设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】
A．8 B．3 C．5 D．9
答案为A,为什么我计算出来是D呢?
我的计算步骤如下:
15，38，61，84用哈希函数H(key)=key%11计算后得地址:4,5,6,7
49计算后为5,发生冲突.
用二次探测再散列法解决冲突:
1:(key+1^2)%11=(49+1)%11=6,仍然发生冲突.
2:(key-1^2)%11=(49-1)%11=4,仍然发生冲突.
3:(key+2^2)%11=(49+4)%11=9,不再发生冲突.
得出结果为D
------解决方案--------------------
答案A是正确的
(key+1^2)%14=(49+1)%14=6,仍然发生冲突.
Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列
这里m=14 不是11
------解决方案--------------------
在《算法导论》中，Hash函数实现采用取余法时，哈希表长m即为除数p。一般根据装载因子（开放地址法我一般选0.7，链接法我一般选2-3左右，欢迎大家给我更合理的值）选取合适的槽的大小，通常为一个不接近2的整数次幂的质数。如：53, 97, 193, 389, 769, 1543, 3079, 6151,
12289, 24593, 49157, 98317,
196613, 393241, 786433, 1572869,
3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189,
805306457, 1610612741
参考严蔚敏老师书上写的
用二次探测再散列法处理冲突： Hi = (H(key) + di)MOD m; 其中m为哈希表长度
我做题过程如下：
插入前15，38，61，84的H(key)分别为:4,5,6,7 存放地址为4,5,6,7
49的H(key)为5,发生冲突.
用二次探测再散列法解决冲突:
1:(5+1^2)%14=(5+1)%14=6,仍然发生冲突.
2:(5-1^2)%14=(5-1)%14=4,仍然发生冲突.
3:(5+2^2)%14=(5+4)%11=9,不再发生冲突.
得出结果为D。 和楼主一样