免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 16016 | 回复: 19

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

论坛徽章:
0
发表于 2010-07-12 18:09 |显示全部楼层
本帖最后由 印随 于 2010-07-15 13:44 编辑

也是从Snort2.8.5摘出来的。
1:删除无用的头文件
2:修改了几个包装函数(关于内存分配和字符串的)


研究了将近3个小时,代码结构非常好,Hash函数是依赖一个大素数表,效果怎么样不知道,
俗话说的好:谁用谁知道

sfxhash.zip

242.9 KB, 下载次数: 648

包含测试数据

论坛徽章:
0
发表于 2010-07-12 18:13 |显示全部楼层
本帖最后由 印随 于 2010-07-12 19:09 编辑
  1. SFXHASH * sfxhash_new( int nrows, int keysize, int datasize, int maxmem,
  2.                        int anr_flag,
  3.                        int (*anrfree)(void * key, void * data),
  4.                        int (*usrfree)(void * key, void * data),
  5.                        int recycle_flag )
复制代码
对sfxhash_new的参数做一下解释,刚开始我看的时候,代码注释没能让我明白确切的含义,所以有必要解释一下:

nrows:hash表中“桶”的个数
keysize:key的长度,就是说作为hash函数的参数的长度(字节)
datasize:0:表示用户不需要关心data的内存管理,!0表示用户自己管理data内存的申请和释放

anr_flag:是否自动回收节点。当内存达到上限时,把最老旧点重新利用
anrfree():释放函数,返回零,可以重新利用。返回非零,不重新利用最旧节点

recycle_flag:节点不释放,存在在free_list中,加入新节点的时候,直接从free_list中取,而不是malloc

论坛徽章:
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-12 18:13 |显示全部楼层
拉链法都比较慢……

论坛徽章:
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-12 18:14 |显示全部楼层
有没有做过profile?我这几天把VimE的hashtab调出来,我们做一下效率对比如何?

论坛徽章:
0
发表于 2010-07-12 18:49 |显示全部楼层
回复 3# starwing83


    是说 hash表实现慢? 还是 有“拉链法”的hash函数? 没听过“拉链法” 这种说法。

弱弱问下,VimE的hash,又大概是怎么实现的?

论坛徽章:
0
发表于 2010-07-12 19:11 |显示全部楼层
本帖最后由 印随 于 2010-07-12 19:23 编辑

回复 4# starwing83


    恩,是需要实际测试一下,不然在项目中使用心里没底

论坛徽章:
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-12 19:15 |显示全部楼层
拉链法是哈希表的实现方法,不是哈希函数的实现方法。不同的哈希表实现方法和不同的哈希函数实现方法造成的效果不同。

拉链法优点在于编程简单。不需多次计算hash值,缺点在于浪费内存,减少填充率。

如果计算新的hash函数能和dereference一样快,那么拉链法就没有任何优势了。

所以理论上开放定址法比拉链法要高效。

另外,质数递增对减少碰撞的确有优势,但是好的hash函数应该也可以避免这一点。所以,还是很多函数使用了2次幂递增。

sfxhash:质数递增+拉链法
vimhash:2幂次递增+开放定址法

hash函数没比较,一般情况下times33效率比较高,Vim是times33的变种,不知道sfxhash是什么hash函数。

论坛徽章:
0
发表于 2010-07-12 19:27 |显示全部楼层
  1. void sfhashfcn_static( SFHASHFCN * p )
  2. {
  3.     p->seed     = 3193;
  4.     p->scale    = 719;
  5.     p->hardener = 133824503;
  6. }

  7. unsigned sfhashfcn_hash( SFHASHFCN * p, unsigned char *d, int n )
  8. {
  9.     unsigned hash = p->seed;
  10.     while( n )
  11.     {
  12.         hash *=  p->scale;
  13.         hash += *d++;
  14.         n--;
  15.     }
  16.     return hash ^ p->hardener;
  17. }
复制代码

论坛徽章:
0
发表于 2010-07-12 19:39 |显示全部楼层
"dereference" 的具体含义是?

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

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

论坛徽章:
12
巳蛇
日期:2013-09-16 15:32:242015年辞旧岁徽章
日期:2015-03-03 16:54:152015年亚洲杯之约旦
日期:2015-02-11 14:38:37双鱼座
日期:2015-01-05 11:05:47戌狗
日期:2014-12-08 09:41:18戌狗
日期:2014-08-15 09:29:29双子座
日期:2014-08-05 09:17:17卯兔
日期:2014-06-08 15:32:18巳蛇
日期:2014-01-27 08:47:08白羊座
日期:2013-11-28 21:04:15巨蟹座
日期:2013-11-13 21:58:012015年亚洲杯之科威特
日期:2015-04-17 16:51:51
发表于 2010-07-12 22:02 |显示全部楼层
坐等测试,我最喜欢看这个了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP