해시 알고리즘 - 폭 설 mpq 기술

#include <iostream>
 using namespace std;
 
#define nTableSize  40000000
 #define nMaxStrLen  20
 
unsigned long cryptTable[0x1000];
 typedef struct _MPQHASHTABLE
 {    
 char bExists;
 }MPQHASHTABLE;
 
MPQHASHTABLE    HashTable[nTableSize];
 int                HashATable[nTableSize];
 int                HashBTable[nTableSize]; 
 
char            data[nTableSize][nMaxStrLen];
 
class CHashForMpq
 {

 public:
  int insert_string(const char *string_in)
  {
   const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;//      
 /*  lpszString                     */
  unsigned int nHash = HashString(string_in, HASH_OFFSET);//     hash     
 unsigned int nHashA = HashString(string_in, HASH_A);//   hashA     
 unsigned int nHashB = HashString(string_in, HASH_B);//   hashB     
 unsigned int nHashStart = nHash % nTableSize;//        
 unsigned int nHashPos = nHashStart;//           
     
  while (HashTable[nHashPos].bExists)//     
{ 
 //      
 if (HashATable[nHashPos]  == nHashA && HashBTable[nHashPos] == nHashB) 
 break; //         ，     ：1.     ，2.        
 else 
  nHashPos = (nHashPos + 1) % nTableSize;//        ，          ，           ，         
       
  if (nHashPos == nHashStart) 
  {
 cout<<"   ，      "<<endl;
  return 0; 
  }
 }
  /*     */
  if (!HashTable[nHashPos].bExists && (strlen(string_in) < nMaxStrLen))
  {   
  HashATable[nHashPos] = nHashA;
  HashBTable[nHashPos] = nHashB;
  strcpy(data[nHashPos], string_in);
  HashTable[nHashPos].bExists = 1;
            cout<<"   "<<string_in<<"    ，  "<<nHashPos<<endl;
  }
  else
  {
  if(HashTable[nHashPos].bExists)
 cout<<"   "<<string_in<<"      ，    "<<endl;
  else
 cout<<"   "<<string_in<<"    ，    "<<endl;
  }
  return nHashPos;

  }
 
  int search_string(const char *string_in)
  {
   const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;//      
 /*  lpszString                     */
  unsigned int nHash = HashString(string_in, HASH_OFFSET);//     hash     
 unsigned int nHashA = HashString(string_in, HASH_A);//   hashA     
 unsigned int nHashB = HashString(string_in, HASH_B);//   hashB     
 unsigned int nHashStart = nHash % nTableSize;//        
 unsigned int nHashPos = nHashStart;//           
         
  while (HashTable[nHashPos].bExists)//     
{ 
 //      
 if (HashATable[nHashPos]  == nHashA && HashBTable[nHashPos] == nHashB) 
 break; //         ，     ：1.     ，2.        
 else 
  nHashPos = (nHashPos + 1) % nTableSize;//        ，          ，           ，         
       
  if (nHashPos == nHashStart) 
  cout<<"   "<<string_in<<"    "<<endl;
  return 0; 
 }
  if(strlen(data[nHashPos]))
  {
  cout<<"   "<<string_in<<"   "<<nHashPos<<endl;
  return nHashPos;
  }
  else
 
 cout<<"   "<<string_in<<"    "<<endl;

  }
 



/*     */
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 ); 
 } 
  } 
 }
 private:
     /*  dwHashType          lpszFileName   hash */
unsigned long HashString(const 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 = *key++;
 seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
     seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 
  }
 
 return seed1; 
  }
 
};
 
void main()
 {
 CHashForMpq cHashForMpq;
 cHashForMpq.prepareCryptTable();
     
     cHashForMpq.insert_string("abcdefghijklmnopqrstuvwxyz");
     cHashForMpq.insert_string("abcd");
     cHashForMpq.insert_string("ab");
 cHashForMpq.insert_string("ab");
 
cHashForMpq.search_string("abcd");
 
    cHashForMpq.search_string("efd");
 
   getchar();
 }