本文主要是介绍第二十四章：不重复Hash编码暴雪Hash算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
暴雪Hash算法：
#include <iostream>
#include <ctype.h>
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<<i<<" "<<j<<endl; cout<<test_data[i]->pkey<<endl; cout<<GetHashTablePos("abcdefghijklmnopqrt",TestHashTable)<<endl;
}
这篇关于第二十四章：不重复Hash编码暴雪Hash算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
