| 学裕 的个人资料土拨鼠照片日志列表 | 帮助 |
|
10月21日 一组用于hash table 的素数表在写hash表的时候,要选择一个素数作为桶的大小,当桶太小时则要对其扩展。
合适扩展呢?设置一个桶和节点的比例因子factor,当节点个数nNode/桶的大小nBucket > factor时扩展。 如何扩展呢?偶的方法是下一个桶的大小就选择 nBucket/factor得到,于是建立了一个表,查表得到下一个桶的大小 表的数据如下:
static const size_t g_hash_prime_list[] = { 61, 83, 113, 151, 211, 281, 379, 509, 683, 911, 1217, 1627, 2179, 2909, 3881, 5179, 6907, 9209, 12281, 16381, 21841, 29123, 38833, 51787, 69061, 92083, 122777, 163729, 218357, 291143, 388211, 517619, 690163, 920219, 1226959, 1635947, 2181271, 2908361, 3877817, 5170427, 6893911, 9191891, 12255871, 16341163, 21788233, 29050993, 38734667, 51646229, 68861641, 91815541,122420729,163227661,217636919,290182597,386910137,515880193, 687840301,917120411,1222827239,1610612741, 3221225473ul, 4294967291ul }; static const int g_hash_primes_num = ARRAY_SIZE(g_hash_prime_list);生成这个表的程序如下:
#include<stdio.h> #include<math.h> bool IsPrime(unsigned int iN)
{ int n; for(n=2;n<=(int)sqrt(iN);n++) if(iN%n==0) break; if(n==(int)sqrt(iN)+1) return true; return false; } #define HASH_FACTOR 4/3 void main() { unsigned int i, iNext; for(i=62;i<=0xffffffff && i>1;++i) { if (IsPrime(i)) { printf("%9d,",i); iNext = i*HASH_FACTOR - 1; if (iNext < i) i = 0; else i = iNext; //printf("(%d)",i+1); } } putchar('\n'); }建立表可以适当减少计算素数所需时间 |
|
|