免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12
最近访问板块 发新帖
楼主: 印随

[C] Snort中的HASH表实现 [复制链接]

论坛徽章:
0
发表于 2010-07-13 10:52 |显示全部楼层
看到C的东西顺眼多了,脱离MS的VC

论坛徽章:
0
发表于 2010-07-13 11:20 |显示全部楼层
再hash法效率怎么样呢?

论坛徽章:
0
发表于 2010-07-13 13:37 |显示全部楼层
测试结果(空间利用)

节点数:46028
hash桶:46028

碰撞深度:7
hash使用率:50.65%

测试了10次,误差小于1.

为什么测试十次?
因为hash函数是动态生成的,所以每次的hash函数都不一样

论坛徽章:
0
发表于 2010-07-13 13:59 |显示全部楼层
回复 13# 印随


    测试代码也发一下,学习一下。

论坛徽章:
0
发表于 2010-07-13 14:04 |显示全部楼层
回复 14# peidright


    其实就是从数据文件中读取字符串然后插入hash表中,数据文件在1楼下载
  1.     /* Add Nodes to the Hash Table */
  2.     fp = fopen("word_line.txt", "r");
  3.     if(!fp)
  4.     {
  5.         printf("open file failed!\n");
  6.         exit(0);
  7.     }
  8.     for(;;)
  9.     {
  10.         ret = fgets(buf, 1024, fp);
  11.         if(ret == NULL)
  12.                 break;
  13.         sfxhash_add( t, buf/* key */,  buf /* data */ );
  14.     }
  15.     fclose(fp);
复制代码

论坛徽章:
0
发表于 2010-07-13 14:10 |显示全部楼层
hash表空间使用率:
  1. double sfxhash_used_rate( SFXHASH * t )
  2. {
  3.     unsigned i;
  4.     double used = 0;

  5.     SFXHASH_NODE * hnode;

  6.     for( i=0; i<t->nrows; i++ )
  7.     {

  8.         hnode = t->table[i];
  9.         if(hnode != NULL)
  10.                 used++;
  11.     }

  12.     return used/(t->nrows);
  13. }
复制代码

论坛徽章:
0
发表于 2010-07-13 14:19 |显示全部楼层
顺便记录一个经典HASH函数:time33(PHP中的实现)
  1. // DJB Hash Function

  2. //It is one of the most efficient hash functions ever published.

  3. unsigned int DJBHash(char *str)
  4. {
  5.         unsigned int hash = 5381;
  6.         while (*str)
  7.         {
  8.                 hash += (hash << 5) + (*str++);
  9.         }
  10.         return (hash & 0x7FFFFFFF);
  11. }
复制代码

论坛徽章:
0
发表于 2010-07-13 19:22 |显示全部楼层
又是GPL2的,只能拿来学习了,谢谢分享。

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2010-07-14 08:39 |显示全部楼层
嗯,我回去做一下测评,晚上把结果给你~~

论坛徽章:
5
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆
日期:2024-02-21 10:00:53
发表于 2010-07-14 08:42 |显示全部楼层
"dereference" 的具体含义是?

我还是最喜欢简单的冲突解决方法。。,否则感觉还不如用其他数据结构,或者某种混合的数据结构。

有个疑问,就是, vimhash "2幂次递增+开放定址法" 意思是没有任何情况,需要用连表法解决冲突?
如果hash表数组充满了呢?   或者说,hash表,不适合用于存储,内容大于数组的情况?, 我个人觉得,vimhash 只适合要存储的内容,小于数组长度2/3,3/4 的情况,某种角度,也不存在是否浪费空间,不浪费空间了。
peidright 发表于 2010-07-12 19:39



    如果存满了或者填充率过高,直接申请一片大空间全部rehash。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP