1 //StringHash.h 2  3 #ifndef __STRINGHASH__                                                                                              4 #define __STRINGHASH__ 5  6 #define MAXTABLELEN 1024 //默认哈希索引表大小 7  8 //哈希索引表定义 9 typedef struct _HASHTABLE10 {11     long nHashA; 12     long nHashB; 13     bool bExists;14 }HASHTABLE, *PHASHTABLE;15 16 class StringHash17 {18     private:19         unsigned long cryptTable[0x500];20         unsigned long m_tablelength;21         HASHTABLE *m_HashIndexTable;22     23     private:24         InitCryptTable(); //对哈希索引表预处理25 26         unsigned long HashString(const char* lpszString, unsigned long dwHashType); //求取哈希值27     28     public: 29         StringHash(const long nTableLength = MAXTABLELEN);30         ~StringHash(void);31 32         bool Hash(const char* url);33         unsigned long Hashed(const char* url); //检测url是否被hash过34 };35 36 #endif

 

1 //StringHash.cpp  2   3 #include 
     
                                                                                                    4   5 StringHash::StringHash(const long nTableLength)  6 {  7     InitCryptTable();  8     m_tablelength = nTableLength;  9  10     //初始化hash表 11     m_HashIndexTabel = new HASHTABLE[nTableLength]; 12     for(int i = 0; i < nTableLength; i++) 13     { 14         m_HashIndexTable[i].nHashA = -1; 15         m_HashIndexTable[i].nHashB = -1; 16         m_HashIndexTable[i].bExists = false; 17     } 18 } 19  20 StringHash::~StringHash(void) 21 { 22     //清理内存 23     if(NULL != m_HashIndexTable) 24     { 25         delete []m_HashIndexTable; 26         m_HashIndexTable = NULL;  27         m_tablelength = 0; 28     } 29 } 30  31 /* 32  *函数名：InitCryptTable 33  *功  能：对哈希索引表预处理 34  *返回值：无 35  */ 36 void StringHash::InitCryptTable(void) 37 { 38     unsigned long sedd = 0x00100001, 39                   index1 = 0, 40                   index2 = 0, 41                   i = 0;   42     for(index1 = 0; index1 < 0x100; index1++) 43     { 44         for(index2 = index1, i = 0; i < 5; i++, index2 += 0x100) 45         { 46             unsigned long temp1, temp2; 47             seed = (seed * 125 + 3) % 0X2AAAAB; 48             temp1 = (seed & 0XFFFF) << 0X10; 49             seed = (seed * 125 + 3) % 0X2AAAAB; 50             temp2 = (seed & 0XFFFF); 51             cryptTable[index2] = (temp1 | temp2); 52         } 53     } 54 } 55  56 /* 57  *函数名：HashString 58  *功  能：求取哈希值 59  *返回值：返回hash值 60  */ 61 unsigned long StringHash::HashString(const char* lpszString, unsigned long dwHashType) 62 { 63     unsigned char* key = lpszString; 64     unsigned long seed1 = 0X7FED7FED, 65                   seed2 = 0XEEEEEEEE; 66     int ch = 0; 67     while(*key != 0) 68     { 69         ch = toupper(*key++); 70         seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2); 71         seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 72     } 73     return seed1; 74 } 75  76 /* 77  *函数名：Hashed 78  *功  能：检测一个字符串是否被hash过 79  *返回值：如果存在，返回位置；否则，返回-1 80  */ 81 unsigned long StringHash::Hashed(const char* lpszString) 82 { 83     const unsigned long HASH__OFFSET = 0, HASH_A = 1, HASH_B = 2; 84     //不同的字符串三次hash还会碰撞的概率无限接近于0 85     unsigned long nHash = HashString(lpszString, HASH_OFFSET); 86     unsigned long nHashA = HashString(lpszString, HASH_A); 87     unsigned long nHashB = HashString(lpszString, HASH_B); 88     unsigned long nHashStart = nHash % m_tablelength; 89     unsigned long nHashPos = nHashStart; 90  91     while(m_HashIndexTable[nHashPos].bExists) 92     { 93         if(m_HashIndexTable[nHashPos].nHashA == nHashA && 94            m_HashIndexTable[nHashPos].nHashB == nHashB) 95             return nHashPos; 96         else 97             nHashPos = (nHashPos + 1) % m_tablelength; 98  99         if(nHashPos == nHashStart)100             break;101     }102 103     return -1;104 }105 106 /*107  *函数名：Hash108  *功  能：hash一个字符串109  *返回值：成功，返回true; 失败, 返回false110  */111 bool StringHash::Hash(const char* lpszString)112 {113     const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;114     unsigned long nHash = HashString(lpszString, HASH_OFFSET);115     unsigned long nHashA = HashString(lpszString, HASH_A);116     unsigned long nHashB = HashString(lpszString, HASH_B);117     unsigned long nHashStart = nHash % m_tablelength;118     unsigned long nHashPos = nHashStart;119 120     while(m_HashIndexTable[nHashPos].bExists)121     { 122         nHashPos = (nHashPos + 1) % m_tablelength;123         if(nHashPos == nHashStart) //一个轮回124         {125             //hash表中没有空余的位置了，无法完成hash126             return false;127         }128     }129 130     m_HashIndexTable[nHashPos].bExists = true;131     m_HashIndexTable[nHashPos].nHashA = nHashA;132     m_HashIndexTable[nHashPos].nHashB = nHashB;133 134     return true;135 }