学裕 的个人资料土拨鼠照片日志列表 工具 帮助
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');  
}建立表可以适当减少计算素数所需时间