VC CHashBuffer 牛逼的hash表算法，字符串查找块了100倍

  牛逼的hash表算法，字符串查找块了100倍

  1 #pragma once
  2  
  3 #include "Afxmt.h"
  4 
  5 class CQHashTNNode 
  6 {
  7 public:
  8     CQHashTNNode()
  9     {
 10         m_nValueData = 0;
 11         m_pKeyData = NULL;
 12         m_nKeyLength = 0;
 13         m_pNext = NULL;
 14         m_nKeySize = 0;
 15     }
 16     CQHashTNNode(PUINT8 pKeyData, UINT32 nKeyLength)
 17     {
 18         m_nValueData = 0;
 19         m_pKeyData = NULL;
 20         m_nKeyLength = 0;
 21         m_pNext = NULL;    
 22         m_nKeySize = 0;        
 23         if (nKeyLength > 0)
 24         {
 25             m_nKeySize = max(64, nKeyLength + 32);
 26             m_pKeyData = new UINT8[m_nKeySize];
 27             if (pKeyData != NULL)
 28             {
 29                 memcpy(m_pKeyData, pKeyData, nKeyLength);
 30                 m_nKeyLength = nKeyLength;
 31             }
 32         }
 33     }
 34     CQHashTNNode(PUINT8 pKeyData, UINT32 nKeyLength, UINT32 nValueData)
 35     {
 36         m_nValueData = nValueData;
 37         m_pKeyData = NULL;
 38         m_nKeyLength = 0;
 39         m_pNext = NULL;    
 40         m_nKeySize = 0;        
 41         if (nKeyLength > 0)
 42         {
 43             m_nKeySize = max(64, nKeyLength + 32);
 44             m_pKeyData = new UINT8[m_nKeySize];
 45             if (pKeyData != NULL)
 46             {
 47                 memcpy(m_pKeyData, pKeyData, nKeyLength);
 48                 m_nKeyLength = nKeyLength;
 49             }
 50         }
 51     }
 52     virtual ~CQHashTNNode()
 53     {
 54         if (m_pKeyData != NULL)
 55         {
 56             delete[] m_pKeyData;
 57             m_pKeyData = NULL;
 58         }
 59     }
 60     
 61 public:
 62     VOID SetValue(PUINT8 pKeyData, UINT32 nKeyLength)
 63     {
 64         m_nKeyLength = nKeyLength;
 65         if (m_nKeySize <= nKeyLength)
 66         {            
 67             m_nKeySize = max(64, nKeyLength + 32);
 68             delete[] m_pKeyData;
 69             m_pKeyData = new UINT8[m_nKeySize];
 70         }
 71         if (pKeyData != NULL)
 72         {
 73             memcpy(m_pKeyData, pKeyData, nKeyLength);
 74         }
 75     }
 76     VOID SetValue(UINT32 nValueData)
 77     {
 78         m_nValueData = nValueData;
 79     }
 80     VOID GetValue(PUINT8 & pKeyData, UINT32 & nKeySize, UINT32 & nKeyLength)
 81     {
 82         if (pKeyData == NULL)
 83         {
 84             nKeySize = m_nKeyLength + 32;
 85             pKeyData = new UINT8[nKeySize];
 86         }
 87         if (nKeySize < m_nKeyLength)
 88         {
 89             delete[] pKeyData;
 90             pKeyData = NULL;
 91             nKeySize = m_nKeyLength + 32;
 92             pKeyData = new UINT8[nKeySize];
 93         }
 94         memcpy(pKeyData, m_pKeyData, m_nKeyLength);
 95         nKeyLength = m_nKeyLength;
 96     }
 97     VOID GetValue(UINT32 & nValueData)
 98     {
 99         nValueData = m_nValueData;
100     }
101     
102 public:
103     VOID AddTailKey(UINT8 nKeyByte)
104     {
105         if (m_pKeyData == NULL)
106         {
107             m_nKeySize = 64;
108             m_pKeyData = new UINT8[m_nKeySize]; 
109             m_nKeyLength = 0;
110         }
111         else if (m_nKeyLength >= m_nKeySize)
112         {
113             m_nKeySize = m_nKeyLength + 32;
114             PUINT8 pBuffer = new UINT8[m_nKeySize]; 
115             memcpy(pBuffer, m_pKeyData, m_nKeyLength);
116             delete [] m_pKeyData;
117             m_pKeyData = pBuffer;
118         }
119         m_pKeyData[m_nKeyLength++] = nKeyByte;
120     }
121     
122 public:
123     BOOL EqualKey(PUINT8 pKeyData, UINT32 nKeyLength)
124     {
125         BOOL bResult = FALSE;
126         if (nKeyLength == m_nKeyLength)
127         {
128             bResult = TRUE;
129             for (int n = 0; n < nKeyLength; n++)
130             {
131                 if (m_pKeyData[n] != pKeyData[n])
132                 {
133                     bResult = FALSE;
134                     break;
135                 }
136             }
137         }
138         return bResult;
139     }
140 
141 public:
142     UINT32 GetHashCode()
143     {
144         UINT32 nHash = 0;    
145         for (int n = 0; n < m_nKeyLength; n++)
146         {
147             nHash = (nHash << 5) - nHash + m_pKeyData[n];
148         }
149         return nHash;
150     }
151 
152 public:
153     static UINT32 GetHashCode(PUINT8 pKeyData, UINT32 nKeyLength)
154     {
155         UINT32 nHash = 0;
156         for (int n = 0; n < nKeyLength; n++)
157         {
158             nHash = (nHash << 5) - nHash + pKeyData[n];
159         }
160         return nHash;
161     }
162 
163 public:
164     UINT32 m_nValueData;
165     PUINT8 m_pKeyData;
166     UINT32 m_nKeyLength;
167     CQHashTNNode * m_pNext;
168 
169 private:
170     UINT32 m_nKeySize;
171 };
172 
173 typedef CQHashTNNode* CQHashTNNodePtr;
174 
175 class CQHashTNBuffer 
176 {
177 private:
178     CQHashTNNodePtr * m_pHashTable;
179     UINT32 m_nTableSize;
180     UINT32 m_nNodeCount;
181     UINT32 m_nCurrentIndex;
182     CQHashTNNode * m_pCurrentNode;
183 
184 public:
185     CQHashTNBuffer()
186     {
187         m_nNodeCount = 0;
188         m_nTableSize = 0;
189         m_pHashTable = NULL;
190     }
191     CQHashTNBuffer(UINT32 nHashSize)
192     {
193         m_nNodeCount = 0;
194         m_nTableSize = nHashSize;
195         m_pHashTable = new CQHashTNNodePtr[nHashSize]();
196         for (int x = 0; x < nHashSize; x++)
197         {
198             m_pHashTable[x] = NULL;
199         }
200     }
201     virtual ~CQHashTNBuffer()
202     {
203         CQHashTNNode *pNode = NULL;
204         CQHashTNNode *pTemp = NULL;
205         for (int x = 0; x < m_nTableSize; x++)
206         {
207             pNode = m_pHashTable[x];
208             while (pNode)
209             {
210                 pTemp = pNode;
211                 pNode = pNode->m_pNext;
212                 delete pTemp;
213             }
214         }
215         delete[] m_pHashTable;
216     }
217 
218 public:
219     BOOL Lookup(PUINT8 pKeyData, UINT32 nKeyLength, UINT32 & nValueData)
220     {
221         BOOL bResult = FALSE;
222         UINT32 nIndex = CQHashTNNode::GetHashCode(pKeyData, nKeyLength) % m_nTableSize;
223         if (m_pHashTable[nIndex] != NULL)
224         {
225             CQHashTNNode * pNode = m_pHashTable[nIndex];
226             while (pNode)
227             {
228                 if (pNode->EqualKey(pKeyData, nKeyLength))
229                 {
230                     nValueData = pNode->m_nValueData;
231                     bResult = TRUE;
232                     break;
233                 }
234                 pNode = pNode->m_pNext;
235             }
236         }
237         return bResult;
238     }
239     BOOL Contains(PUINT8 pKeyData, UINT32 nKeyLength) 
240     {
241         BOOL bResult = FALSE;
242         UINT32 nIndex = CQHashTNNode::GetHashCode(pKeyData, nKeyLength) % m_nTableSize;
243         if (m_pHashTable[nIndex] != NULL)
244         {
245             CQHashTNNode * pNode = m_pHashTable[nIndex];
246             while (pNode)
247             {
248                 if (pNode->EqualKey(pKeyData, nKeyLength))
249                 {
250                     bResult = TRUE;
251                     break;
252                 }
253                 pNode = pNode->m_pNext;
254             }
255         }
256         return bResult;
257     }
258     VOID SetAt(PUINT8 pKeyData, UINT32 nKeyLength, UINT32 nValueData)
259     {
260         UINT32 nIndex = CQHashTNNode::GetHashCode(pKeyData, nKeyLength) % m_nTableSize;
261         if (m_pHashTable[nIndex] != NULL)
262         {            
263             BOOL bFind = FALSE;
264             CQHashTNNode * pNode = m_pHashTable[nIndex];
265             while (pNode)
266             {
267                 if (pNode->EqualKey(pKeyData, nKeyLength))
268                 {
269                     pNode->m_nValueData = nValueData;
270                     bFind = TRUE;
271                     break;
272                 }
273                 pNode = pNode->m_pNext;
274             }
275             if (!bFind)
276             {
277                 pNode = new CQHashTNNode(pKeyData, nKeyLength, nValueData);
278                 pNode->m_pNext = m_pHashTable[nIndex];
279                 m_pHashTable[nIndex] = pNode;
280                 m_nNodeCount += 1;
281             }
282         }
283         else
284         {
285             CQHashTNNode * pNode = new CQHashTNNode(pKeyData, nKeyLength, nValueData);
286             pNode->m_pNext = m_pHashTable[nIndex];
287             m_pHashTable[nIndex] = pNode;
288             m_nNodeCount += 1;
289         }
290     }
291     VOID Remove(PUINT8 pKeyData, UINT32 nKeyLength)
292     {
293         UINT32 nIndex = CQHashTNNode::GetHashCode(pKeyData, nKeyLength) % m_nTableSize;
294         if (m_pHashTable[nIndex] != NULL)
295         {
296             CQHashTNNode * pNode = m_pHashTable[nIndex];
297             CQHashTNNode * pPrev = NULL;
298             while (pNode != NULL)
299             {
300                 if (pNode->EqualKey(pKeyData, nKeyLength))
301                 {
302                     if (pPrev == NULL)
303                     {
304                         m_pHashTable[nIndex] = pNode->m_pNext;
305                     }
306                     else 
307                     {
308                         pPrev->m_pNext = pNode->m_pNext;
309                     }
310                     delete pNode;
311                     m_nNodeCount -= 1;
312                     break;
313                 }
314                 pNode = pNode->m_pNext;
315             }
316         }
317     }
318     VOID RemoveAll()
319     {
320         for (UINT32 n = 0; n < m_nTableSize; n++)
321         {
322             if (m_pHashTable[n] != NULL)
323             {
324                 CQHashTNNode * pNode = m_pHashTable[n];
325                 while (pNode)
326                 {
327                     m_pHashTable[n] = pNode->m_pNext;
328                     delete pNode;
329                     pNode = m_pHashTable[n];
330                 }
331             }
332         }
333         m_nNodeCount = 0;
334     }
335     UINT32 GetCount()
336     {
337         return m_nNodeCount;
338     }
339 
340 public:
341     CQHashTNNode * GetHead()
342     {
343         m_nCurrentIndex = 0;
344         m_pCurrentNode = NULL;
345         for (int n = 0; n < m_nTableSize; n++)
346         {
347             if (m_pHashTable[n] != NULL)
348             {
349                 m_nCurrentIndex = n;
350                 m_pCurrentNode = m_pHashTable[n];
351                 break;
352             }
353         }
354         return m_pCurrentNode;
355     }
356     CQHashTNNode * GetNext()
357     {
358         if (m_pCurrentNode != NULL)
359         {
360             if (m_pCurrentNode->m_pNext != NULL)
361             {
362                 m_pCurrentNode = m_pCurrentNode->m_pNext;
363             }
364             else 
365             {
366                 for (UINT32 n = m_nCurrentIndex; n < m_nTableSize; n++)
367                 {
368                     if (m_pHashTable[n] != NULL)
369                     {
370                         m_nCurrentIndex = n;
371                         m_pCurrentNode = m_pHashTable[n];
372                         break;
373                     }
374                 }
375             }
376         }
377         return m_pCurrentNode;
378     }
379 };