C++哈希表之閉散列方法的模擬實(shí)現(xiàn)詳解

更新時(shí)間：2022年11月10日 11:46:22 作者：Gaze！

閉散列指（開(kāi)放定址法）發(fā)生沖突時(shí)，如果哈希表沒(méi)有被填滿，則表內(nèi)一定還有其他空閑位置，可以把沖突值放到下一個(gè)沒(méi)有被占用的空余位置上。本文將模擬實(shí)現(xiàn)閉散列方法，需要的可以參考一下

哈希

概念

可以不經(jīng)過(guò)任何比較，直接從表中得到要搜索的元素。關(guān)鍵在于通過(guò)某種函數(shù)，使元素的存儲(chǔ)位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系。這樣就可以通過(guò)o(1)的時(shí)間復(fù)雜度來(lái)尋找到元素。

例如數(shù)據(jù)集合{1,7,4,5,9,6}，哈希函數(shù)hash(key)=key&capacity

沖突

hash(7)=7 hash(17)=7,兩個(gè)不同的數(shù)通過(guò)哈希函數(shù)映射到了一個(gè)位置，產(chǎn)生了沖突。哈希函數(shù)設(shè)計(jì)的越精妙，產(chǎn)生沖突的可能性就越低，但無(wú)法避免。

解決方法：

閉散列（開(kāi)放定址法）
開(kāi)散列（拉鏈法）

閉散列

閉散列，（開(kāi)放定址法）發(fā)生沖突時(shí)，如果哈希表沒(méi)有被填滿，則表內(nèi)一定還有其他空閑位置，可以把沖突值放到下一個(gè)沒(méi)有被占用的空余位置上。

如何找到下一個(gè)沒(méi)有被占用的空位？答：采用線性探測(cè)方法。從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到尋找到下一個(gè)空位置為止。

線性探測(cè)

線性探測(cè)的插入

如：在上述的哈希表中插入元素44，由于下標(biāo)為4的位置放入了元素4，于是從該位置往后++，找到第一個(gè)不為空的位置，將44放入。

線性探測(cè)的刪除

在尋找要?jiǎng)h除的元素時(shí)，依然會(huì)根據(jù)存放在哈希表的下標(biāo)開(kāi)始尋找，比如在上述哈希表中尋找4，在4下標(biāo)位置直接就可以找到該元素。但如果直接將其刪除，那后續(xù)尋找元素44時(shí)，就會(huì)因?yàn)?下標(biāo)沒(méi)有元素，而認(rèn)為元素44不存在于這張哈希表。所以我們需要設(shè)置一個(gè)狀態(tài)來(lái)表示刪除。

哈希表閉散列的模擬實(shí)現(xiàn)

我們寫(xiě)在一個(gè)自定義類域 Closehash 里面

準(zhǔn)備工作

哈希表中元素狀態(tài)

namespace Closehash
{
    //哈希表中元素的狀態(tài)
    enum State
    {
        EMPTY,
        EXIT,
        DELETE
    };    
}

存儲(chǔ)類型用pair即可，但是數(shù)據(jù)中要包含狀態(tài)，我們進(jìn)行一次封裝

//由于數(shù)據(jù)需要一個(gè)狀態(tài)，所以需要將pair<K,V>封裝一層
    template<class K,class V>
    struct HashDate
    {
        pair<K, V>_kv;
        State _state;
    };

開(kāi)始（畫(huà)餅）構(gòu)建哈希表的內(nèi)容

template<class K,class V>
    class HashTable
    {
    public:
        bool Insert(const pair<K,V>& kv);
        HashDate<K, V>* find(const K& key);
        bool Erase(const K& key);
    private:
        vector<HashDate<K,V>> _tables;
        size_t _size = 0;
    };

閉散列的插入

        bool Insert(const pair<K, V>& kv)
        {
            //if (Find(kv.first)) return false; 
            //Find實(shí)現(xiàn)了再去掉注釋
 
            if (_tables.size() == 0 
                || 10 * _size / _tables.size() >= 7)//相當(dāng)于存了70%
            {
                //開(kāi)始擴(kuò)容
                size_t newsize = _tables.size()== 0 ? 10 : _tables.size() * 2;
                HashTable<K, V> newHash;
                newHash._tables.resize(newsize);
                for (auto e: _tables)//注意_tables是HashDate類型 里面有_kv 和_state
                {
                    if (e._state == EXIST)
                    {
                        newHash.Insert(e._kv);
                    }
                }
                //資本家拷貝方法
                _tables.swap(newHash._tables);
            }
            //走到這里擴(kuò)容完成 或者空間足夠大
            size_t hashi = kv.first % _tables.size();//尋找在表中對(duì)應(yīng)的下標(biāo)是什么
            while (_tables[hashi]._state==EXIST)
            {
                hashi++;
                //走到頭了得回來(lái)
                hashi%=_tables.size();
            }
            _tables[hashi]._kv = kv;
            _tables[hashi]._state = EXIST;
            _size++;
            return true;
        }

測(cè)試用例

void TestHT1()
    {
        int a[] = { 1, 11, 4, 15, 26, 7, 44 };
        HashTable<int, int> ht;
        for (auto e : a)
        {
            ht.Insert(make_pair(e, e));
        }
 
        ht.Print();
    }

添加個(gè)99以驗(yàn)證擴(kuò)容功能

閉散列的查找

HashDate<K, V>* Find(const K& key)
        {
            if (_tables.size() == 0) return nullptr;
            size_t hashi = key % _tables.size();
            while (_tables[hashi]._state != EMPTY)
            {
                if (_tables[hashi]._state != DELETE 
                    && _tables[hashi]._kv.first == key)
                {
                    return &_tables[hashi];
                }
                hashi++;
                hashi% _tables.size();
            }
            return nullptr;
        }

測(cè)試用例

    cout << ht.Find(4)->_kv.first << endl;

閉散列的刪除

bool Erase(const K& key)
        {
            HashDate<K,V>* ret = Find(key);
            if (ret)
            {
                ret->_state = DELETE;
                --_size;
                return true;
            }
            else
            {
                return false;
            }
        }

模擬實(shí)現(xiàn)的閉散列中的問(wèn)題與改進(jìn)

上述測(cè)試用例中使用的是pair<int,int>那我要是用pair<string,int>呢？我的key還可以直接對(duì)數(shù)組長(zhǎng)度取模嗎？

文檔中對(duì)這一問(wèn)題采用了仿函數(shù)的解決方法，我們這里也按照該方法模擬一個(gè)。

    template<class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };
 
    // 特化  
    template<>
    struct HashFunc<string>
    {
        // BKDR
        size_t operator()(const string& key)
        {
            size_t val = 0;
            for (auto ch : key)
            {
                val *= 131;
                val += ch;
            }
 
            return val;
        }
    };
 
    template<class K,class V,class Hash=HashFunc<K>>
    class HashTable
    {
    public:
        bool Insert(const pair<K,V>& kv);
        HashDate<K, V>* find(const K& key);
        bool Erase(const K& key);
    private:
        vector<HashDate<K,V>> _tables;
        size_t _size = 0;
    };

在每次求在哈希表中位置的前面添加

Hash hash;
size_t hashi = hash(kv.first) % _tables.size()

測(cè)試用例

void TestHT2()
    {
        string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };
 
        //HashTable<string, int, HashFuncString> countHT;
        HashTable<string, int> countHT;
        for (auto& str : arr)
        {
            auto ptr = countHT.Find(str);
            if (ptr)
            {
                ptr->_kv.second++;
            }
            else
            {
                countHT.Insert(make_pair(str, 1));
            }
        }
    }

測(cè)試用例沒(méi)加打印...讓我來(lái)回看了好幾遍代碼...蠢到無(wú)語(yǔ)