从头到尾彻底解析哈希表算法4
补充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（合10进制数：1280）的cryptTablevoid 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 = ( 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的三个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*/ prepareCryptTable(); /*打印数组crytTable里面的值*/ for ( ; i < 0x500; i++ ) { if ( i % 10 == 0 ) { printf("/n"); } printf("%-12X", cryptTable ); } ulHashValue = HashString( argv, 0 ); printf("/n----%X ----/n", ulHashValue ); ulHashValue = HashString( argv, 1 ); printf("----%X ----/n", ulHashValue ); ulHashValue = HashString( argv, 2 ); printf("----%X ----/n", ulHashValue ); return 0;} 哇居然没人回复下！我顶你
页:
[1]