posts - 6, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Wild Magic 中 Hash Table实现

Posted on 2010-05-02 20:18 Current 阅读(2146) 评论(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

Feedback

# re: Wild Magic 中 Hash Table实现[未登录]  回复  更多评论   

2010-05-03 13:33 by megax
这个HashClass应用太局限了。

# re: Wild Magic 中 Hash Table实现  回复  更多评论   

2012-08-04 14:07 by 是否
能给注释一下吗

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理