查找字符串的哈希方法

比较经典的字符串hash,相信很多使用C的都使用过了吧。



转贴同学redor的一篇文章,感觉很有用。

//  RS Hash Function
unsigned  int  RSHash( char   * str)
{
        unsigned  int  b  =   378551 ;
        unsigned  int  a  =   63689 ;
        unsigned  int  hash  =   0 ;

         while  ( * str)
         {
                hash  =  hash  *  a  +  ( * str ++ );
                a  *=  b;
        }

         return  (hash  &   0x7FFFFFFF );
}

//  JS Hash Function
unsigned  int  JSHash( char   * str)
{
        unsigned  int  hash  =   1315423911 ;

         while  ( * str)
         {
                hash  ^=  ((hash  <<   5 )  +  ( * str ++ )  +  (hash  >>   2 ));
        }

         return  (hash  &   0x7FFFFFFF );
}

//  P. J. Weinberger Hash Function
unsigned  int  PJWHash( char   * str)
{
        unsigned  int  BitsInUnignedInt  =  (unsigned  int )( sizeof (unsigned  int )  *
8 );
        unsigned  int  ThreeQuarters     =  (unsigned  int )((BitsInUnignedInt   *   3 )
  /   4 );
        unsigned  int  OneEighth         =  (unsigned  int )(BitsInUnignedInt  /   8 );

        unsigned  int  HighBits          =  (unsigned  int )( 0xFFFFFFFF )  <<  (BitsInU
nignedInt  -  OneEighth);
        unsigned  int  hash              =   0 ;
        unsigned  int  test              =   0 ;

         while  ( * str)
         {
                hash  =  (hash  <<  OneEighth)  +  ( * str ++ );
                 if  ((test  =  hash  &  HighBits)  !=   0 )
                 {
                        hash  =  ((hash  ^  (test  >>  ThreeQuarters))  &  ( ~ HighBits)
);
                }
        }

         return  (hash  &   0x7FFFFFFF );
}

//  ELF Hash Function
unsigned  int  ELFHash( char   * str)
{
        unsigned  int  hash  =   0 ;
        unsigned  int  x     =   0 ;

         while  ( * str)
         {
                hash  =  (hash  <<   4 )  +  ( * str ++ );
                 if  ((x  =  hash  &   0xF0000000L )  !=   0 )
                 {
                        hash  ^=  (x  >>   24 );
                        hash  &=   ~ x;
                }
        }

         return  (hash  &   0x7FFFFFFF );
}

//  BKDR Hash Function
unsigned  int  BKDRHash( char   * str)
{
        unsigned  int  seed  =   131 ;  //  31 131 1313 13131 131313 etc..
        unsigned  int  hash  =   0 ;

         while  ( * str)
         {
                hash  =  hash  *  seed  +  ( * str ++ );
        }

         return  (hash  &   0x7FFFFFFF );
}

//  SDBM Hash Function
unsigned  int  SDBMHash( char   * str)
{
        unsigned  int  hash  =   0 ;

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

         return  (hash  &   0x7FFFFFFF );
}

//  DJB Hash Function
unsigned  int  DJBHash( char   * str)
{
        unsigned  int  hash  =   5381 ;

         while  ( * str)
         {
                hash  +=  (hash  <<   5 )  +  ( * str ++ );
        }

         return  (hash  &   0x7FFFFFFF );
}

//  AP Hash Function
unsigned  int  APHash( char   * str)
{
        unsigned  int  hash  =   0 ;
         int  i;

         for  (i = 0 ;  * str; i ++ )
         {
                 if  ((i  &   1 )  ==   0 )
                 {
                        hash  ^=  ((hash  <<   7 )  ^  ( * str ++ )  ^  (hash  >>   3 ));
                }
                 else
                 {
                        hash  ^=  ( ~ ((hash  <<   11 )  ^  ( * str ++ )  ^  (hash  >>   5 )));
                }
        }

         return  (hash  &   0x7FFFFFFF );
}
比较经典的字符串hash就这些了吧,"ELF Hash Function" <-这个比较常用..

Monthly Archives

Pages

Powered by Movable Type 7.7.2

About this Entry

This page contains a single entry by Cnangel published on July 17, 2007 1:03 PM.

青岛之行 was the previous entry in this blog.

十年之约 is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.