青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 6, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

Wild Magic 中 Hash Table實現

Posted on 2010-05-02 20:18 Current 閱讀(2199) 評論(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 是否
能給注釋一下嗎
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲精华国产欧美| 亚洲电影免费观看高清完整版在线观看| 亚洲国产成人一区| 欧美激情麻豆| 欧美日韩国产不卡在线看| 日韩一级大片| 亚洲视频香蕉人妖| 国产午夜精品视频免费不卡69堂| 欧美专区福利在线| 老牛国产精品一区的观看方式| 91久久精品国产91性色tv| 亚洲三级视频| 国产精品一区二区三区四区| 久久精品首页| 欧美韩日一区二区| 欧美一区二区三区精品| 久久精品亚洲乱码伦伦中文 | 久久伊伊香蕉| 亚洲午夜羞羞片| 久久国产精品黑丝| 一本色道久久综合亚洲91| 亚洲无限乱码一二三四麻| 在线成人h网| 99在线|亚洲一区二区| 国内精品久久久久久久影视蜜臀| 欧美激情偷拍| 国产亚洲成av人在线观看导航| 欧美高清不卡在线| 国产喷白浆一区二区三区| 欧美激情一区二区久久久| 国产精品久久久久久亚洲毛片 | 一区二区三区视频免费在线观看| 亚洲男人的天堂在线| 亚洲精品久久| 久久精品国产精品亚洲| 亚洲欧美经典视频| 欧美精品尤物在线| 美女诱惑黄网站一区| 国产精品视频99| 日韩午夜在线播放| 最新国产成人av网站网址麻豆 | 欧美成人一区二区三区在线观看 | 精品91视频| 亚洲在线一区二区| 亚洲视频成人| 欧美精品国产一区| 亚洲国产精选| 亚洲国产日韩欧美在线动漫| 午夜亚洲福利在线老司机| 亚洲午夜伦理| 欧美日韩直播| 亚洲青色在线| 亚洲欧洲在线免费| 欧美一二三视频| 久久成人18免费网站| 国产精品免费福利| 亚洲天堂av电影| 亚洲欧美日韩精品久久亚洲区| 欧美精品成人| 日韩天堂av| 亚洲深夜激情| 国产精品嫩草久久久久| 在线一区二区日韩| 亚洲欧美影音先锋| 国产欧美日韩三级| 午夜精品久久久久久久白皮肤 | 久久这里只精品最新地址| 国产一区二区0| 久久久久一区| 亚洲国产精品久久久久秋霞影院 | 夜夜嗨av一区二区三区四区| 在线亚洲精品| 国产精品丝袜xxxxxxx| 亚洲在线国产日韩欧美| 久久夜色精品国产噜噜av| 尤物视频一区二区| 欧美黄色精品| 亚洲一区二区三区精品动漫| 久久国产精品99国产精| 韩国自拍一区| 欧美高清在线视频| 亚洲特黄一级片| 另类专区欧美制服同性| 亚洲美女黄网| 国产精品一区二区久激情瑜伽| 欧美亚洲在线视频| 亚洲国产视频一区二区| 亚洲一区二区三区免费在线观看| 国产精品美女久久久免费 | 日韩视频精品在线观看| 午夜精品国产精品大乳美女| 国产在线视频不卡二| 欧美成人69av| 亚洲一区二区综合| 欧美好吊妞视频| 亚洲欧美日韩国产综合在线 | 欧美日韩国产美| 午夜一区二区三视频在线观看| 欧美国产欧美亚州国产日韩mv天天看完整 | 亚洲欧美久久久| 亚洲第一精品夜夜躁人人爽| 在线视频你懂得一区| 韩国精品在线观看| 欧美三级资源在线| 美女精品在线观看| 香蕉久久国产| 亚洲视频免费在线| 亚洲人成毛片在线播放| 久久久综合激的五月天| 一区二区不卡在线视频 午夜欧美不卡在 | 免费久久精品视频| 午夜伦欧美伦电影理论片| 亚洲国产精品视频一区| 久久se精品一区精品二区| 一二三区精品福利视频| 亚洲成人影音| 国产在线视频欧美一区二区三区| 欧美体内she精视频| 久久婷婷国产麻豆91天堂| 亚洲制服欧美中文字幕中文字幕| 亚洲国产精品小视频| 美女网站久久| 久久久午夜精品| 欧美一区国产一区| 亚洲欧美色一区| 国产精品99久久99久久久二8| 黄色成人在线网址| 国产一区二区三区不卡在线观看| 欧美精品色综合| 欧美激情成人在线视频| 美女国产精品| 欧美成人一二三| 另类av导航| 欧美~级网站不卡| 免费成人性网站| 欧美本精品男人aⅴ天堂| 久热这里只精品99re8久| 久久久久久电影| 久久人人爽人人爽爽久久| 欧美一区二区三区四区视频| 午夜精品一区二区三区在线| 亚洲一区二区三区中文字幕 | 老牛嫩草一区二区三区日本| 午夜性色一区二区三区免费视频| 亚洲婷婷综合久久一本伊一区| 亚洲国产成人久久| 亚洲欧美伊人| 午夜精品av| 久久精品亚洲一区二区三区浴池| 性欧美超级视频| 久久精品国产视频| 久久性天堂网| 欧美成va人片在线观看| 欧美国产精品中文字幕| 亚洲国产精品成人精品| 欧美激情中文不卡| 亚洲精品偷拍| 亚洲午夜精品久久久久久浪潮| 亚洲午夜精品一区二区| 午夜精品久久久久久久白皮肤 | 亚洲欧洲日本国产| 一区二区三区四区精品| 亚洲欧美色一区| 久久久水蜜桃av免费网站| 欧美激情综合在线| 国产精品区一区二区三| 激情六月综合| 中文国产一区| 老鸭窝亚洲一区二区三区| 亚洲韩国一区二区三区| 亚洲一区二区三区免费视频| 久久爱91午夜羞羞| 欧美日韩国产高清视频| 国产真实乱偷精品视频免| 亚洲三级免费电影| 久久福利资源站| 亚洲激情视频在线播放| 亚洲欧美中文在线视频| 欧美gay视频激情| 国产亚洲精品v| 亚洲一区在线直播| 欧美成人久久| 亚洲尤物在线| 欧美激情综合五月色丁香| 国产亚洲人成a一在线v站| 日韩亚洲一区在线播放| 久久亚洲电影| 亚洲欧美国产三级| 欧美日韩免费区域视频在线观看| 韩国三级电影久久久久久| 一区二区三区四区精品| 欧美肥婆在线| 欧美一区二区精品在线| 国产精品99免费看| 亚洲精品小视频在线观看| 久久久久久久久久久久久女国产乱| 日韩一区二区电影网| 欧美www视频| 亚洲国产清纯| 免费一级欧美片在线观看|