Hash存储、查找中Hash表构造方法、冲突率问题

C语言 码拜 9年前 (2016-04-13) 1136次浏览
#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;  
}

从网上看到这个很经典的Hash算法,但是有几点没有明白:
1. prepareCryptTable和HashString函数中构造cryptTable、Hash值时这些参数和公式是怎么选择出来的呢?例如:seed = 0x00100001,seed = (seed * 125 + 3) % 0x2AAAAB;
这里又是怎么样保证构造的cryptTable表中没有重复呢?
2. 这个Hash算法中的冲突率是怎么计算来的呢?

解决方案

20

冲突率就可以简单理解成重复率吧
重复率从原理上说,假如结果为1字节,那么当输入数据超过256种时,必然产生重复。
当输入数据小于256时,也有可能产生重复,这与算法设计有关,真正的算法是由数学证明过的,不是拍脑门想出来的。

40

hash的计算应该尽量避免重复,但过程也不要太复杂,否则效率也未必会提高

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Hash存储、查找中Hash表构造方法、冲突率问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)