Posted on 2010-05-02 20:18
Current 阅读(2173)
评论(2) 编辑 收藏 引用 所属分类:
Wild Magic 引擎解析
在维基百科中 hash 的解释为：
散列函数（或散列算法，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合，重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。
Wild Magic 中 Hash Table实现这里所指“指纹”是指：通过一个唯一的“量”（如：一个object的物理地址的指针值），在二叉树中快速的查找到相对应的变量。
具体代码：
THashTable.hpp
1
#ifndef _HASHTABLE_HPP_
2#define _HASHTABLE_HPP_
3
4#include "FoundationLIB.hpp"
5
6#include "System.hpp"
7
8
/**//*
9
* 利用hash函数 实现对链表的访问运算量达到和数组访问相当的效率
10
*/
11namespace PX2
12
{
13
/**//// 哈希表模板类
14 template<class TKEY, class TVALUE>
15 class THashTable
16 {
17 public:
18 THashTable ( int iTableSize );
19 ~THashTable ();
20
21 int GetQuantity () const;
22
23 bool Insert ( const TKEY& rtKey, const TVALUE& rtValue );
24
25 TVALUE* Find ( const TKEY& rtKey ) const;
26
27 bool Remove ( const TKEY& rtKey );
28 void RemoveAll ();
29
30 TVALUE* GetFirst ( TKEY* ptKey ) const;
31 TVALUE* GetNext ( TKEY* ptKey ) const;
32
33 int (*UserHashFunction) ( const TKEY& );
34
35 private:
36 class HashItem
37 {
38 public:
39 TKEY m_tKey;
40 TVALUE m_tValue;
41 HashItem* m_pkNext;
42
};
43
44 int HashFunction ( const TKEY& rtKey ) const;
45
46 int m_iTableSize;
47 int m_iQuantity;
48 HashItem** m_apkTable;
49
50 mutable int m_iIndex;
51 mutable HashItem* m_pkItem;
52 };
53
54#include "THashTable.inl"
55}
56#endif//_HASHTABLE_HPP_
THashTable.inl
1template <class TKEY, class TVALUE>
2THashTable <TKEY, TVALUE> ::THashTable( int iTableSize )
3{
4 assert( iTableSize > 0);
5
6 m_iTableSize = iTableSize;
7 m_iQuantity = 0;
8 m_iIndex = 0;
9 m_pkItem = 0;
10 m_apkTable = NEW HashItem*[m_iTableSize];
11
12 memset(m_apkTable, 0, m_iTableSize * sizeof(HashItem*));
13 UserHashFunction = 0;
14}
15//-------------------------------------------------------------------------------
16template <class TKEY, class TVALUE>
17THashTable<TKEY, TVALUE> ::~THashTable()
18{
19 RemoveAll();
20 DELETE [] m_apkTable;
21}
22//-------------------------------------------------------------------------------
23template <class TKEY, class TVALUE>
24int THashTable<TKEY, TVALUE> ::GetQuantity () const
25{
26 return m_iQuantity;
27}
28//-------------------------------------------------------------------------------
29template <class TKEY, class TVALUE>
30bool THashTable<TKEY, TVALUE> ::Insert( const TKEY& rtKey,
31 const TVALUE& rtValue )
32{
33 int iIndex = HashFunction( rtKey );
34 HashItem* pkItem = m_apkTable[iIndex];
35
36 while (pkItem)
37 {
38 if (rtKey == pkItem->m_tKey)
39 {
40 return false;
41 }
42
43 pkItem = pkItem->m_pkNext;
44 }
45
46 pkItem = NEW HashItem;
47 pkItem->m_tKey = rtKey;
48 pkItem->m_tValue = rtValue;
49 pkItem->m_pkNext = m_apkTable[iIndex];
50 m_apkTable[iIndex] = pkItem;
51 ++m_iQuantity;
52
53 return true;
54}
55//-------------------------------------------------------------------------------
56template <class TKEY, class TVALUE>
57TVALUE* THashTable<TKEY, TVALUE> ::Find( const TKEY& rtKey ) const
58{
59
60 int iIndex = HashFunction( rtKey );
61 HashItem* pkItem = m_apkTable[iIndex];
62
63 while( pkItem )
64 {
65 if (rtKey == pkItem->m_tKey )
66 {
67 return &pkItem->m_tValue;
68 }
69
70 pkItem = pkItem->m_pkNext;
71 }
72 return 0;
73}
74//-------------------------------------------------------------------------------
75template <class TKEY, class TVALUE>
76bool THashTable<TKEY, TVALUE> ::Remove ( const TKEY& rtKey)
77{
78 int iIndex = HashFunction( rtKey );
79 HashItem* pkItem = m_apkTable[iIndex];
80
81 if (!pkItem)
82 {
83 return false;
84 }
85
86 if (rtKey == pkItem->m_tKey)
87 {
88 HashItem* pkSave = pkItem;
89 m_apkTable[iIndex] = pkItem->m_pkNext;
90 DELETE pkSave;
91 --m_iQuantity;
92
93 return true;
94 }
95
96 HashItem* pkPrev = pkItem;
97 HashItem* pkCurr = pkItem->m_pkNext;
98 while ( pkPrev && rtKey != pkCurr->m_tKey)
99 {
100 pkPrev = pkCurr;
101 pkCurr = pkCurr->m_pkNext;
102 }
103
104 if (pkCurr)
105 {
106 pkPrev->m_pkNext = pkCurr->m_pkNext;
107 DELETE pkCurr;
108 m_iQuantity--;
109 return true;
110 }
111
112 return false;
113}
114//-------------------------------------------------------------------------------
115template <class TKEY, class TVALUE>
116void THashTable<TKEY,TVALUE> ::RemoveAll ()
117{
118 if (m_iQuantity > 0)
119 {
120 for (int iIndex = 0; iIndex < m_iTableSize; iIndex++)
121 {
122 while (m_apkTable[iIndex])
123 {
124 HashItem* pkSave = m_apkTable[iIndex];
125 m_apkTable[iIndex] = m_apkTable[iIndex]->m_pkNext;
126 DELETE pkSave;
127 if (--m_iQuantity == 0)
128 {
129 return;
130 }
131 }
132 }
133 }
134}
135//-------------------------------------------------------------------------------
136template <class TKEY, class TVALUE>
137TVALUE* THashTable<TKEY,TVALUE> ::GetFirst ( TKEY* ptKey ) const
138{
139 if (m_iQuantity > 0)
140 {
141 for (m_iIndex = 0; m_iIndex < m_iTableSize; m_iIndex++)
142 {
143 if (m_apkTable[m_iIndex])
144 {
145 m_pkItem = m_apkTable[m_iIndex];
146 *ptKey = m_pkItem->m_tKey;
147 return &m_pkItem->m_tValue;
148 }
149 }
150 }
151
152 return 0;
153}
154//-------------------------------------------------------------------------------
155template <class TKEY, class TVALUE>
156TVALUE* THashTable<TKEY,TVALUE> ::GetNext ( TKEY* ptKey ) const
157{
158 if (m_iQuantity > 0)
159 {
160 m_pkItem = m_pkItem->m_pkNext;
161 if (m_pkItem)
162 {
163 *ptKey = m_pkItem->m_tKey;
164 return &m_pkItem->m_tValue;
165 }
166
167 for (m_iIndex++; m_iIndex < m_iTableSize; m_iIndex++)
168 {
169 if (m_apkTable[m_iIndex])
170 {
171 m_pkItem = m_apkTable[m_iIndex];
172 *ptKey = m_pkItem->m_tKey;
173 return &m_pkItem->m_tValue;
174 }
175 }
176 }
177
178 return 0;
179}
180//-------------------------------------------------------------------------------
181template <class TKEY, class TVALUE>
182int THashTable<TKEY,TVALUE> ::HashFunction (const TKEY& rtKey) const
183{
184 if (UserHashFunction)
185 {
186 return (*UserHashFunction)(rtKey);
187 }
188
189 // 默认Hash 函数 采用黄金分割
190 static double s_dHashMultiplier = 0.5*(sqrt(5.0)-1.0);
191 unsigned int uiKey;
192 System::Memcpy(&uiKey, sizeof(unsigned int), &rtKey, sizeof(unsigned int));
193 uiKey %= m_iTableSize;
194 double dFraction = fmod(s_dHashMultiplier*uiKey,1.0);
195 return (int)floor(m_iTableSize*dFraction);
196}
197//-------------------------------------------------------------------------------
198
199// end