大侠们救命----关于二次探测再散列的C语言实现

syoubin_sai

针对开放地址哈希表结构，采用线性探测再散列处理冲突过程中会发生的两个第一个哈希地址不同的记录争夺一个后续哈希地址的“二次聚集”的现象。
例：
用线性探测再散列法处理冲突： Hi = key MOD m; 其中m=10为哈希表长度,插入前15，16，17，18，19的H(key)分别为:5,6,7,8,9存放地址为:5,6,7,8,9
46的H(key)为6,发生冲突，连续向下探测4次，出现“二次聚集”的现象.

用二次探测再散列法处理冲突： Hi = (H(key) + di)MOD m; 其中m为哈希表长度,di=12,-12,22,-22,32,....k2(k <=m/2)，插入前15，16，17，18，19的H(key)分别为:5,6,7,8,9 存放地址为:5,6,7,8,9  
46的H(key)为6,发生冲突. 用二次探测再散列法解决冲突:  
16+12)%10=(6+1)%10=7,仍然发生冲突.  
26-12)%10=(6-1)%10=5,仍然发生冲突.  
36+22)%10=(6+4)%10=0,不再发生冲突.  
则46放置于位置0。

用二次探测再散列法处理冲突时，查找算法如下：

1. #include <stdio.h>
   
2. #include <sys/types.h>
   
3. #include <assert.h>
   
4. 
   
5. #define MAXSIZE 99999
   
6. #define YES 1
   
7. #define NO 0
   
8. #define HK(key) ((key)%(MAXSIZE))
   
9. 
   
10. typedef struct uid_e {
    
11.         uid_t uid;
    
12.         unsigned int njobs;
    
13. } uid_e_t;
    
14. 
    
15. typedef struct uid_hash {
    
16.         uid_e_t elem[MAXSIZE];
    
17.         int used[MAXSIZE];
    
18. } uid_hash_t;
    
19. 
    
20. void init_uid_hash (uid_hash_t *H) {
    
21.         assert (H != NULL);
    
22.         int i = 0;
    
23.         for (i = 0; i < MAXSIZE; i++) {
    
24.                 H->elem[i].uid = 0;
    
25.                 H->elem[i].njobs = 0;
    
26.                 H->used[i] = NO;
    
27.         }
    
28. }
    
29. int insert_uid_hash(uid_hash_t *H, const uid_e_t *e) {
    
30.         assert (H != NULL);
    
31.         assert (e != NULL);
    
32. 
    
33.         unsigned int key = HK(e->uid);
    
34.         int di = 1;
    
35.         if (H->elem[key].uid == e->uid && H->used[key] == YES ) {
    
36.                 return -1;
    
37.         }
    
38.         while (H->used[key] == YES) {
    
39.                //这里输出key
    
40.                 printf ("%u\n", key);
    
41.                 if (di > MAXSIZE/2) {
    
42.                         return -1;
    
43.                 }
    
44.                 else if (di > 0) {
    
45.                         key= HK(HK(e->uid) + (di*di));
    
46.                         di = -di;
    
47.                         if (key < 0) key = MAXSIZE + key;
    
48.                 } else {
    
49.                         key= HK(HK(e->uid) - (di*di));
    
50.                         di = -di;
    
51.                         di ++;
    
52.                         if (key < 0) key = MAXSIZE + key;
    
53.                 }
    
54. 
    
55.         }
    
56.         if (key <= MAXSIZE) {
    
57.                 H->elem[key] = *e;
    
58.                 H->used[key] = YES;
    
59.                 return key;
    
60.         }
    
61.         return -1;
    
62. }
    
63. int getpos (const uid_hash_t *H, uid_t uid, uid_e_t *e) {
    
64.         unsigned int key = HK(uid);
    
65.         int di = 1;
    
66.         if (H->used[key] == NO) {
    
67.                 return -1;
    
68.         } else {
    
69.                 while (H->used[key] == NO || H->elem[key].uid != uid) {
    
70.                         if (di > MAXSIZE/2) {
    
71.                                 return -1;
    
72.                         }
    
73.                         else if (di > 0) {
    
74.                                 key = HK(HK(uid) + (di*di));
    
75.                                 di = -di;
    
76.                                 if (key < 0) key = MAXSIZE + key;
    
77.                         } else {
    
78.                                 key = HK(HK(uid) - (di*di));
    
79.                                 if (key < 0) key = MAXSIZE + key;
    
80.                                 di = -di;
    
81.                                 di ++;
    
82.                         }
    
83.                 }
    
84.         }
    
85.         *e = H->elem[key];
    
86.         return key;
    
87. }
    
88. int main ()
    
89. {
    
90.         int i = 0;
    
91.         uid_hash_t H;
    
92.         //设置所有位置已经使用
    
93.         for (i = 0; i < MAXSIZE; i ++) {
    
94.                 H.used[i] = YES;
    
95.         }
    
96.         uid_e_t e1 = {1, 1};
    
97.         insert_uid_hash(&H, &e1);
    
98. 
    
99.         return 0;
    
100. }
     

复制代码

二次探测再散列公式产生的key值如下：

[root@hpc-rm c_test]# ./a.out | sort -n |less
0
1
1
1
1
1
1
2
2
2
2
5
5
5
5
7
7
7
7
10
10
10
10
10
10
11

为什么会出现重复的key值呢？是不是我的公式不对？
如果公式正确的话，如何才能产生不重复的key值呢？

有建议说把MAXSIZE改为素数就不会出现重复的key了，但我修改后照样会出现重复的key值？为什么呢？
是我算法不对？

求大侠们指点，项目逼得紧！

syoubin_sai

syoubin_sai

貌似二次哈希再散列存在key重复的问题是正常的。
但有没有其他哈希函数不存在key重复呢？
另外，线性探测除外。

alainwii

回复 1# syoubin_sai


    貌似很难，期待解决中……

davelv

貌似二次哈希再散列存在key重复的问题是正常的。
但有没有其他哈希函数不存在key重复呢？
另外，线性探测 ...
syoubin_sai 发表于 2010-09-01 08:29

在有限的数据下，不重复的KEY是可能，但不一定是可行的。

daybreakcx

发现你的程序会没完没了地重新探测，不是说你的算法有什么问题，而是你的程序自己没调试过吧，问题出在93行
刚开始的时候为什么是把所有的used全部设置为YES？这样所有位置的key都是0，而都假设被0占用了，这样你insert的1不管怎么探测都是已被占用的位置，所以除非你第一次插入0，否则都是没完没了地输出
再者就是关于MAXSIZE的问题，之所以选择素数，是因为如果使用合数就可能形成“结”，比如说吧MAXSIZE=12的时候，你初识是3，然后每次加上4，这时候会进行探测的位置是3，7，11，3，7，11...，即某些位置无法访问到，而用素数就没有这个问题，或者说你每次固定加上与MAXSIZE互素的数值都没这个问题（比如对于12你可以选5啊7啊这些的），但是貌似在你的方法中没有这个问题，所以你怎么弄个人观点是无所谓，这点上我保留意见
还有就是你的41行，你确定大于MAXSIZE/2就一定不会有新的可访问结点？这点我仍然保留意见
除此之外56行，既然取hash你是直接取余，那么MAXSIZE是不可能取得的，所以那个等号加的也太累赘了吧
然后还有要说的，其实现在很多都是直接链地址了，再散列的确很简单，容易实现，但是当元素个数大于MAXSIZE的时候就怎么也无法插入了，所以用链地址的比较多点，建议你可以试试看
最后一点：下次贴代码的时候无关的就别贴了，既然你init_uid_hash和getpos都没使用，那么就在贴的时候去掉，太大篇幅大家都不太愿意认真看完，被回答的机会就少了，这个只是个忠告而已~~~

syoubin_sai

发现你的程序会没完没了地重新探测，不是说你的算法有什么问题，而是你的程序自己没调试过吧，问题出在93行 ...
daybreakcx 发表于 2010-09-01 09:28

93行完全设置为YES是为了测试方便故意占位的，设置YES方便查看整个探测过程中key值的变化。
探测MAXSIZE/2次结束完全是按照二次探测结束条件设置的，所以未做过多的考虑。
帖代码时比较仓促直接就全帖上来了，请大虾见谅。

另外大虾的回答对我解决问题的意义不大，也不去深究啦。
但还是多谢大虾了。

问题已经解决，谢谢大家。

shmild

貌似二次哈希再散列存在key重复的问题是正常的。
但有没有其他哈希函数不存在key重复呢？
另外，线性探测 ...
syoubin_sai 发表于 2010-09-01 08:29

为什么排斥线性探测呢，对自己的hash函数不自信，会有很坏的情况？
不存在key重复的哈希函数理论上是不可能，如果key和value一一对应，那还要哈希做什么，直接下标索引就是了

syoubin_sai

为什么排斥线性探测呢，对自己的hash函数不自信，会有很坏的情况？
不存在key重复的哈希函数理论上是 ...
shmild 发表于 2010-09-01 10:50

    的确是不存在这样的哈希函数。
当时考虑线性探测时，存在二次聚集现象。所以没多想就直接采用了二次探测在散列的方式解决冲突，但测试的时候发现这个方式不能解决项目实际问题。
现在只能回归线性探测了。。。。
以前对哈希表理解不到位所以出了问题