无我

让内心永远燃烧着伟大的光明的精神之火!
灵活的思考,严谨的实现
豪迈的气魄、顽强的意志和周全的思考

剖析eSNACC的hash函数

我们前面已经写了一篇文章剖析eSNACC哈希结构的设计和实现 剖析eSNACC哈希结构的设计和实现 ,而本篇我们专门剖析eSNACC中的hash函数。

我们先看看eSNACC求hash函数的实现:

typedef unsigned int Hash;
/*
 *
 * From sdbm, an ndbm work-alike hashed database library
 * Author: oz@nexus.yorku.ca
 * Status: public domain.
 *
 * polynomial conversion ignoring overflows
 * [this seems to work remarkably well, in fact better
 * then the ndbm hash function. Replace at your own risk]
 * use: 65599   nice.
 *      65587   even better.
 *
 * [In one experiment, this function hashed 84165 symbols (English words
 * plus symbol table values) with no collisions. -bjb]
 *
 
*/


Hash    MakeHash (
const char *str, size_t len)
{
    register Hash n 
= 0;

#define HASHC   n = *str++ + 65587 * n

    
if (len > 0)
    
{
        
int loop;
        loop 
= (len + 8 - 1>> 3;
        
switch (len & (8 - 1))
    
{
          
case 0:          

            do
        
{
                HASHC;
              
case 7: HASHC;
              
case 6: HASHC;
              
case 5: HASHC;
              
case 4: HASHC;
              
case 3: HASHC;
              
case 2: HASHC;
              
case 1: HASHC;
        }
 while (--loop);
    }

    }

    
return n;
}

 看到这个代码,我想先请问读者您有什么想法?如果您没来得及总结,可以参考我下面给的选项:

1、一定是本人粗心大意,copy代码时弄错了。

2、写这个代码的人是不是临时工?基本的语法都没过关。

3、大师,不愧为大师!

4、雕虫小巧,小菜一碟,一目了然嘛~

 

=============================Please give your answers first=================

 

好了,我对您的选项作答:

1、我保证我做事一丝不苟、严谨踏实。此代码是一字一句来自于源码(除了空格的调整),如假包换、假一罚十!

2、我不能确定他是不是临时工,但是我保证语法完全正确。

3、maybe...

4、那我只能说我太佩服您了!因为至少我是第一次看到case套在do-while里面的写法。对您这样的高人前来,有失远迎,万请恕罪!

 

==================================================================

好了,作为技术研究,我们下面就要深入剖析这个hash函数了。

首先,为了清楚,我把头文件中的typedef也移到了代码前。eSNACC的hash值用unsigned int表示。

然后,在说明代码逻辑之前,我们不妨先看看函数的注释:作者说本函数来自于sdbm,其中的修改就是把原来的magic number 65599改为了65587,因为他说明:65599 nice ,65587   even better.哪个魔数是better,我们就不在本文讨论了。我们只研究算法。

既然是来自于sdbm,那么sdbm是什么呢?我的另一篇博客专门转录了这些信息,有兴趣可以参见hash函数——djb2、sdbm、lose lose

这里只简单介绍一下sdbm:

sdbm哈希函数的算法:对一个字符串str,分别求出hash(i) = hash(i - 1) * 65599 + str[i],hash值就是所有hash(i)的和。其实现为:

  static unsigned long    sdbm( unsigned char *str)
  {
        unsigned long hash = 0;
        int c;

        while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;

        return hash;
    }

 

然后我们再回到eSNACC中的MakeHash函数,看那种让人崩溃的代码是不是就是这个算法:

先看这个宏#define HASHC   n = *str++ + 65587 * n,这好像表达的就是hash(i) = hash(i - 1) * 65599 + str[i],只是65599->65587.这个让我们很满意,那么后面的switch等是不是就是一个遍历呢?

loop = (len + 8 - 1) >> 3   ==> loop=(len+8-1)/8 ==> loop=(len-1)/8 + 1  :其实算出来的loop就是len除以8的值,如果有余数,那值加1。

len & (8 - 1) :这里算出来的恰恰就是len%8的值。

我们再仔细分析switch-case和do-while结构:

其算法是这样的:比如len=28,

1.计算loop=4.

2.算出len%8的值,然后先执行该值次数的HASHC;本例中len%8=4,那么在switch时会到case 4:然后依次执行了4次HASHC;

3.进while,--loop,这样这个do-while还会执行3次,每次HASHC会运行8次。

所以,最终就是3*8 + 4 =28,也就是说这与上面的sdbm的算法时完全一样的!只是魔数变了,然后写法上有些匪夷所思了。

 

/***********************************休息一下**************************************

好了,对MakeHash函数的分析是完成了,但是我觉得很有必要来思考一下这个函数的效率。

我们设计hash函数,一方面希望使函数产生的哈希值尽量分散减少冲突,另一方面就是希望保证这个函数效率很高,因为每次加入值,查找值时都要计算hash,如果函数效率不高,对整个系统也会是一种负担。

结合这两个因素,第一、我们发现作者将65599改成65587,他说明这样生成hash的效果更好。但是第二条就实在无法让人乐观了!我们看到hash函数——djb2、sdbm、lose lose 中给的hash函数都为了提高性能都已经把对魔数的运算改成了移位操作,但是在MakeHash中,就是死硬的乘法!对字符串的每一个字节算一次乘法!说实话,想起如果字符串比较长,我真有点毛骨悚然...

 

所以,就让我们就仿照sdbm中的实现,把乘法优化掉来做一个MakeHash的优化版吧:

Hash MakeHashOpt (const char *str, size_t len)
{
    register Hash n 
= 0;

#define HASHCOPT   n = *str++ + (n << 16) + (n << 5) +  (n << 4) + (n << 1) + n

    
if (len > 0)
    
{
        
int loop;
        loop 
= (len + 8 - 1>> 3;
        
switch (len & (8 - 1))
        
{
        
case 0:        
            
do
            
{
                HASHCOPT;
        
case 7: HASHCOPT;
        
case 6: HASHCOPT;
        
case 5: HASHCOPT;
        
case 4: HASHCOPT;
        
case 3: HASHCOPT;
        
case 2: HASHCOPT;
        
case 1: HASHCOPT;
            }
 while (--loop);
        }

    }

    
return n;
}

 

最后,让我们来分析一下作者设计成这种看起来很别扭的实现形式的目的吧。

正如前面的分析,这样做事先求出len对8的倍数,然后除了需要对余数做switch-case判断来宏调用1-8次以为,其他的就是每次固定做8次宏调用。我认为:他这样做,就是希望减少用while或for遍历串的判断次数,因为那样要判断len+1次。现在就只要len/8 + 1 + len%8次了。

 

好了,对eSNACC的hash函数剖析就到此了。

 

 

posted on 2012-04-26 15:37 Tim 阅读(1622) 评论(2)  编辑 收藏 引用 所属分类: eSNACC学习

评论

# re: 剖析eSNACC的hash函数 2012-04-26 15:55 Tim

呵呵,谢谢支持~@嵌入式培训
  回复  更多评论   

# re: 剖析eSNACC的hash函数[未登录] 2012-04-27 09:29 Tina

不懂技术,还是支持一下!加油!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

公告

本博客原创文章,欢迎转载和交流。不过请注明以下信息:
作者:TimWu
邮箱:timfly@yeah.net
来源:www.cppblog.com/Tim
感谢您对我的支持!

留言簿(9)

随笔分类(173)

IT

Life

搜索

积分与排名

最新随笔

最新评论

阅读排行榜