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