首页 手机软件 手机游戏 单机游戏 资讯文章 专题下载 游戏合集 文章合集 php下载 php教程 电脑软件
+ -
当前位置：首页 → 问答吧 → 大侠们救命----关于二次探测再散列的C语言实现

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

时间：2010-08-31

来源：互联网

针对开放地址哈希表结构，采用线性探测再散列处理冲突过程中会发生的两个第一个哈希地址不同的记录争夺一个后续哈希地址的“二次聚集”的现象。
例：
用线性探测再散列法处理冲突： 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>

  5. #define MAXSIZE 99999
  6. #define YES 1
  7. #define NO 0
  8. #define HK(key) ((key)%(MAXSIZE))

  10. typedef struct uid_e {
  11.         uid_t uid;
  12.         unsigned int njobs;
  13. } uid_e_t;

  15. typedef struct uid_hash {
  16.         uid_e_t elem[MAXSIZE];
  17.         int used[MAXSIZE];
  18. } uid_hash_t;

  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);

  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.                 }

  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);

  99.         return 0;
  100. }
复制代码
二次探测再散列公式产生的key值如下：


QUOTE:
[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   发布时间: 2010-08-31

作者: syoubin_sai   发布时间: 2010-08-31

相关阅读 更多

热门阅读

热门下载

更多
关于本站 免责申明 联系我们

Copyright 2006-2020 php爱好者(phpfans.net) All Rights Reserved.备案号：湘ICP备2023016114号-2

本站为非盈利性网站，不接受任何广告。本站所有资源均由网友上传，如有侵权，请发邮件至 [email protected] phpfans.net