hash的目的就是速度快，而且冲突低，Dobbs博士的这个hash算法代码量少，而且处理一般规模的数据都是不错的选择,著名的memcached当初抛弃了Judy后选择的就是这个hash算法了。http://burtleburtle.net/bob/hash/doobs.html

贴一下使用该hash的代码：

#include<stdio.h>
  #include<string.h>
 
  typedef  unsigned long  int  ub4;  
  typedef  unsigned       char ub1;  
 
 
  #define HASHPOWER  20
 
  #define hashsize(n) ((ub4)1<<(n))
  #define hashmask(n) (hashsize(n)-1)
 
  #define mix(a,b,c)
  {
    a -= b; a -= c; a ^= (c>>13);
    b -= c; b -= a; b ^= (a<<8);
    c -= a; c -= b; c ^= (b>>13);
    a -= b; a -= c; a ^= (c>>12);  
    b -= c; b -= a; b ^= (a<<16);
    c -= a; c -= b; c ^= (b>>5);
    a -= b; a -= c; a ^= (c>>3);  
    b -= c; b -= a; b ^= (a<<10);
    c -= a; c -= b; c ^= (b>>15);
  }

ub4 hash( k, length, initval)
       register ub1 *k;       
       register ub4  length;  
       register ub4  initval; 
  {
      register ub4 a,b,c,len;
 
     
      len = length;
      a = b = 0x9e3779b9; 
      c = initval;        
 
     
      while (len >= 12)
          {
              a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
              b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
              c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
              mix(a,b,c);
              k += 12; len -= 12;
          }
 
     
      c += length;

     switch(len)             
          {
          case 11: c+=((ub4)k[10]<<24);
          case 10: c+=((ub4)k[9]<<16);
          case 9 : c+=((ub4)k[8]<<8);
             
          case 8 : b+=((ub4)k[7]<<24);
          case 7 : b+=((ub4)k[6]<<16);
          case 6 : b+=((ub4)k[5]<<8);
          case 5 : b+=k[4];
          case 4 : a+=((ub4)k[3]<<24);
          case 3 : a+=((ub4)k[2]<<16);
          case 2 : a+=((ub4)k[1]<<8);
          case 1 : a+=k[0];
             
          }
      mix(a,b,c);
     
      return c;
  }
 
  int main(int argc,char **argv){
 
      ub4 hash_value;
      char *key1 = "liufuqiang";
      hash_value = hash(key1,strlen(key1),0);
      printf("%s's hash is :%lun",key1,hash_value);
      char *key2 = "liufuqiang2";
      hash_value = hash(key2,strlen(key2),0);
      printf("%s's hash is :%lun",key2,hash_value);
      return 0;
  }

 输出结果是连个无符号长整型的数字，如：

liufuqiang's hash is :8197653076439130864
liufuqiang2's hash is :13585834058072564895

类别:技术文章 | 阅读:206079 | 评论:0 | 标签:hash