MemoryGarden's Blog

努力 -----------大能猫
C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
hash 函数 (转载)
ELF hash是对字符串进行hash操作时的常用函数
我在网上找到的对这个算法的解释是： 将一个字符串的数组中的每个元素依次按前四位与上一个元素的低四位相与，组成一个长整形，如果长整的高四位大于零，那么就将它折回再与长整的低四位相异或，这样最后得到的长整对HASH表长取余，得到在HASH中的位置。
虽然还是不大清楚，但还是得先牢记才行。

 1 int ELFhash(char *key)
 2 {
 3     unsigned long h = 0;
 4     unsigned long g;
 5     while( *key )
 6     {
 7         h =( h<< 4) + *key++;
 8         g = h & 0xf0000000L;
 9         if( g ) h ^= g >> 24;
10         h &= ~g;
11     }
12     return h;
13 }

其他的字符串hash函数还有：
// 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 );
}

// 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 & 0x7FF FFFFF );
}
posted on 2009-09-07 18:30 memorygarden 阅读(107) 评论(0)  编辑 收藏 引用

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