从头到尾彻底解析哈希表算法4

H9enRy

　补充2、一个完整测试程序：　　哈希表的数组是定长的，如果太大，则浪费，如果太小，体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数。当然，根据不同的数据量，会有不同的哈希表的大小。对于数据量时多时少的应用，最好的设计是使用动态可变尺寸的哈希表，那么如果你发现哈希表尺寸太小了，比如其中的元素是哈希表尺寸的2倍时，我们就需要扩大哈希表尺寸，一般是扩大一倍。　　下面是哈希表尺寸大小的可能取值：　　17,            37,          79,        163,          331,
　　673,           1361,        2729,       5471,         10949,
　　21911,          43853,      87719,      175447,      350899,
　　701819,         1403641,    2807303,     5614657,     11229331,
　　22458671,       44917381,    89834777,    179669557,   359339171,
　　718678369,      1437356741,  2147483647　　以下为该程序的完整源码，已在linux下测试通过：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687#include <stdio.h>  #include <ctype.h>     //多谢citylove指正。  //crytTable[]里面保存的是HashString函数里面将会用到的一些数据，在prepareCryptTable  //函数里面初始化  unsigned long cryptTable[0x500];     //以下的函数生成一个长度为0x500（合10进制数：1280）的cryptTable[0x500]  void prepareCryptTable()  {       unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;         for( index1 = 0; index1 < 0x100; index1++ )      {           for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )          {               unsigned long temp1, temp2;                 seed = (seed * 125 + 3) % 0x2AAAAB;              temp1 = (seed & 0xFFFF) << 0x10;                 seed = (seed * 125 + 3) % 0x2AAAAB;              temp2 = (seed & 0xFFFF);                 cryptTable[index2] = ( temp1 | temp2 );          }      }   }     //以下函数计算lpszFileName 字符串的hash值，其中dwHashType 为hash的类型，  //在下面GetHashTablePos函数里面调用本函数，其可以取的值为0、1、2；该函数  //返回lpszFileName 字符串的hash值；  unsigned long HashString( char *lpszFileName, unsigned long dwHashType )  {       unsigned char *key  = (unsigned char *)lpszFileName;  unsigned long seed1 = 0x7FED7FED;  unsigned long seed2 = 0xEEEEEEEE;      int ch;         while( *key != 0 )      {           ch = toupper(*key++);             seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);          seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;       }      return seed1;   }     //在main中测试argv[1]的三个hash值：  //./hash  "arr/units.dat"  //./hash  "unit/neutral/acritter.grp"  int main( int argc, char **argv )  {      unsigned long ulHashValue;      int i = 0;         if ( argc != 2 )      {          printf("please input two arguments/n");          return -1;      }          /*初始化数组：crytTable[0x500]*/      prepareCryptTable();          /*打印数组crytTable[0x500]里面的值*/      for ( ; i < 0x500; i++ )       {           if ( i % 10 == 0 )           {               printf("/n");           }              printf("%-12X", cryptTable[i] );       }          ulHashValue = HashString( argv[1], 0 );       printf("/n----%X ----/n", ulHashValue );          ulHashValue = HashString( argv[1], 1 );       printf("----%X ----/n", ulHashValue );          ulHashValue = HashString( argv[1], 2 );       printf("----%X ----/n", ulHashValue );          return 0;  }

新浪

哇  居然没人回复下！我顶你