首页 手机软件 手机游戏 单机游戏 资讯文章 专题下载 游戏合集 文章合集 php下载 php教程 电脑软件
+ -
当前位置：首页 → 问答吧 → 很好的HASH表实现

很好的HASH表实现

时间：2010-07-12

来源：互联网

本帖最后由 印随 于 2010-07-13 14:31 编辑

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


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

sfxhash.zip (242.9 KB)

下载次数:32

2010-07-13 14:31

包含测试数据

作者: 印随   发布时间: 2010-07-12

本帖最后由 印随 于 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

作者: 印随   发布时间: 2010-07-12

拉链法都比较慢……

作者: starwing83   发布时间: 2010-07-12

有没有做过profile？我这几天把VimE的hashtab调出来，我们做一下效率对比如何？

作者: starwing83   发布时间: 2010-07-12

回复 starwing83


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

弱弱问下，VimE的hash，又大概是怎么实现的？

作者: peidright   发布时间: 2010-07-12

本帖最后由 印随 于 2010-07-12 19:23 编辑

回复 starwing83


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

作者: 印随   发布时间: 2010-07-12

拉链法是哈希表的实现方法，不是哈希函数的实现方法。不同的哈希表实现方法和不同的哈希函数实现方法造成的效果不同。

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

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

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

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

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

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

作者: starwing83   发布时间: 2010-07-12

  1. void sfhashfcn_static( SFHASHFCN * p )
  2. {
  3.     p->seed     = 3193;
  4.     p->scale    = 719;
  5.     p->hardener = 133824503;
  6. }

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

作者: 印随   发布时间: 2010-07-12

"dereference" 的具体含义是？

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

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

作者: peidright   发布时间: 2010-07-12

坐等测试，我最喜欢看这个了。

作者: zhaohongjian000   发布时间: 2010-07-12

看到C的东西顺眼多了，脱离MS的VC

作者: owood   发布时间: 2010-07-13

再hash法效率怎么样呢?

作者: liexusong   发布时间: 2010-07-13

测试结果（空间利用）

节点数：46028
hash桶：46028

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

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

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

作者: 印随   发布时间: 2010-07-13

回复 印随


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

作者: peidright   发布时间: 2010-07-13

回复 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);
复制代码

作者: 印随   发布时间: 2010-07-13

hash表空间使用率：
  1. double sfxhash_used_rate( SFXHASH * t )
  2. {
  3.     unsigned i;
  4.     double used = 0;

  6.     SFXHASH_NODE * hnode;

  8.     for( i=0; i<t->nrows; i++ )
  9.     {

  11.         hnode = t->table[i];
  12.         if(hnode != NULL)
  13.                 used++;
  14.     }

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

作者: 印随   发布时间: 2010-07-13

顺便记录一个经典HASH函数：time33（PHP中的实现）
  1. // DJB Hash Function

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

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

作者: 印随   发布时间: 2010-07-13

相关阅读 更多

热门阅读

热门下载

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

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

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