本文共 6082 字，大约阅读时间需要 20 分钟。

暴雪Hash算法：

#include 
   
         #include 
    
       using namespace std;      #define nTableSize 99991  #define nMaxStrLen 30    //函数prepareCryptTable以下的函数生成一个长度为0x500（合10进制数：1280）的cryptTable[0x500]    unsigned long 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 );             }         }     }     //函数HashString以下函数计算lpszFileName 字符串的hash值，其中dwHashType 为hash的类型，    unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )    {        unsigned char *key  = (unsigned char *)lpszkeyName;        unsigned long seed1 = 0x7FED7FED;        unsigned long seed2 = 0xEEEEEEEE;        int ch;            while( *key != 0 )        {            ch = *key++;            seed1 = cryptTable[(dwHashType<<8) + ch] ^ (seed1 + seed2);            seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;        }        return seed1;    }    typedef struct    {        int nHashA;        int nHashB;        char bExists;    } MPQHASHTABLE;    //一种可能的结构体定义？    typedef struct{      char *pkey;      int weight;  }KEYNODE, *key_list;    //函数GetHashTablePos中，lpszString 为要在hash表中查找的字符串；lpTable 为存储字符串hash值的hash表；nTableSize 为hash表的长度：     int GetHashTablePos(const char *lpszString, MPQHASHTABLE *lpTable )    {        const int  HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;             int  nHash = HashString( lpszString, HASH_OFFSET );        int  nHashA = HashString( lpszString, HASH_A );        int  nHashB = HashString( lpszString, HASH_B );        int  nHashStart = nHash % nTableSize;        int  nHashPos = nHashStart;             while ( lpTable[nHashPos].bExists )       {    //     如果仅仅是判断在该表中时候存在这个字符串，就比较这两个hash值就可以了，不用对结构体中的字符串进行比较。    //         这样会加快运行的速度？减少hash表占用的空间？这种方法一般应用在什么场合？            if (lpTable[nHashPos].nHashA == nHashA            &&  lpTable[nHashPos].nHashB == nHashB )           {                return nHashPos;           }           else           {                nHashPos = (nHashPos + 1) % nTableSize;           }                 if (nHashPos == nHashStart)                  break;        }         return -1;    }    /    //function: 哈希词典 编码    //parameter:    //author: lei.zhou    //time: 2011-12-14    /    MPQHASHTABLE TestHashTable[nTableSize];    int TestHashCTable[nTableSize];    int TestHashDTable[nTableSize];    key_list test_data[nTableSize];        //按关键字查询，如果成功返回hash表中索引位置  key_list SearchByString(const char *string_in)  {      const int HASH_OFFSET = 0, HASH_C = 1, HASH_D = 2;      unsigned int nHash = HashString(string_in, HASH_OFFSET);      unsigned int nHashC = HashString(string_in, HASH_C);      unsigned int nHashD = HashString(string_in, HASH_D);      unsigned int nHashStart = nHash % nTableSize;      unsigned int nHashPos = nHashStart;        while (TestHashTable[nHashPos].bExists)       {          if (TestHashCTable[nHashPos] == (int) nHashC && TestHashDTable[nHashPos] == (int) nHashD)           {              break;              //查询与插入不同，此处不需修改          }           else           {              nHashPos = (nHashPos + 1) % nTableSize;          }            if (nHashPos == nHashStart)           {              break;          }      }        if( test_data[nHashPos] && strlen(test_data[nHashPos]->pkey))       {          return test_data[nHashPos];      }         return NULL;  }    //直接调用上面的hashstring，nHashPos就是对应的HASH值。    int insert_string(const char *string_in)    {        const int HASH_OFFSET = 0, HASH_C = 1, HASH_D = 2;        unsigned int nHash = HashString(string_in, HASH_OFFSET);        unsigned int nHashC = HashString(string_in, HASH_C);        unsigned int nHashD = HashString(string_in, HASH_D);        unsigned int nHashStart = nHash % nTableSize;        unsigned int nHashPos = nHashStart;        int ln, ires = 0;            while (TestHashTable[nHashPos].bExists)        {    //      if (TestHashCTable[nHashPos]  == (int) nHashC && TestHashDTable[nHashPos] == (int) nHashD)    //          break;    //      //...    //      else            //如之前所提示读者的那般，暴雪的Hash算法对于查询那样处理可以，但对插入就不能那么解决                nHashPos = (nHashPos + 1) % nTableSize;                if (nHashPos == nHashStart)                break;        }            ln = strlen(string_in);        if (!TestHashTable[nHashPos].bExists && (ln < nMaxStrLen))        {             TestHashCTable[nHashPos] = nHashC;            TestHashDTable[nHashPos] = nHashD;                test_data[nHashPos] = (KEYNODE *) malloc (sizeof(KEYNODE) * 1);            if(test_data[nHashPos] == NULL)            {                printf("10000 EMS ERROR !!!!\n");                return 0;            }                test_data[nHashPos]->pkey = (char *)malloc(ln+1);            if(test_data[nHashPos]->pkey == NULL)            {                printf("10000 EMS ERROR !!!!\n");                return 0;            }                memset(test_data[nHashPos]->pkey, 0, ln+1);            strncpy(test_data[nHashPos]->pkey, string_in, ln);            *((test_data[nHashPos]->pkey)+ln) = 0;            test_data[nHashPos]->weight = nHashPos;                TestHashTable[nHashPos].bExists = 1;           TestHashTable[nHashPos].nHashA=nHashC;          TestHashTable[nHashPos].nHashB=nHashD;      }        else        {            if(TestHashTable[nHashPos].bExists)                printf("30000 in the hash table %s !!!\n", string_in);            else                printf("90000 strkey error !!!\n");        }        return nHashPos;    }    int main()    {        prepareCryptTable();      int i=insert_string("abcdefghijklmnopqrst");      int j=insert_string("abcdefghijklmnopqrt");      cout<
     <<"  "<
      
       <
       
        pkey<
       
      
    
   

转载地址：http://obvvi.baihongyu.com/