C++數(shù)據(jù)結(jié)構(gòu)之哈希表的實現(xiàn)

更新時間：2023年03月11日 10:16:15 作者：叫我小秦就好了

哈希表，即散列表，可以快速地存儲和查詢記錄。這篇文章主要為大家詳細介紹了C++數(shù)據(jù)結(jié)構(gòu)中哈希表的實現(xiàn)，感興趣的小伙伴可以了解一下

哈希表概念

二叉搜索樹具有對數(shù)時間的表現(xiàn)，但這樣的表現(xiàn)建立在一個假設(shè)上：輸入的數(shù)據(jù)有足夠的隨機性。哈希表又名散列表，在插入、刪除、搜索等操作上具有「常數(shù)平均時間」的表現(xiàn)，而且這種表現(xiàn)是以統(tǒng)計為基礎(chǔ)，不需依賴輸入元素的隨機性。

聽起來似乎不可能，倒也不是，例如：

假設(shè)所有元素都是 8-bits 的正整數(shù)，范圍 0~255，那么簡單得使用一個數(shù)組就可以滿足上述要求。首先配置一個數(shù)組 Q，擁有 256 個元素，索引號碼 0~255，初始值全部為 0。每一個元素值代表相應(yīng)的元素的出現(xiàn)次數(shù)。如果插入元素 i，就執(zhí)行 Q[i]++，如果刪除元素 i，就執(zhí)行 Q[i]--，如果查找元素 i，就看 Q[i] 是否為 0。

這個方法有兩個很嚴重的問題。

如果元素是 32-bits，數(shù)組的大小就是2³²=4GB，這就太大了，更不用說 64-bits 的數(shù)了
如果元素類型是字符串而非整數(shù)，就需要某種方法，使其可用作數(shù)組的索引

散列函數(shù)

如何避免使用一個太大的數(shù)組，以及如何將字符串轉(zhuǎn)化為數(shù)組的索引呢？一種常見的方法就是使用某種映射函數(shù)，將某一元素映射為一個「大小可接受的索引」，這樣的函數(shù)稱為散列函數(shù)。

散列函數(shù)應(yīng)有以下特性：

函數(shù)的定義域必須包含需要存儲的全部關(guān)鍵字，當散列表有 m 個地址時，其值域在 0 到 m - 1 之間
函數(shù)計算出來的地址能均勻分布在整個空間

直接定址法

取關(guān)鍵字的某個線性函數(shù)為散列地址：Hash(Key)=A∗Key+B

優(yōu)點：簡單、均勻

缺點：需要事先知道關(guān)鍵字的分布情況

使用場景：數(shù)據(jù)范圍比較集中的情況

除留余數(shù)法

設(shè)散列表的索引個數(shù)為 m，取一個不大于 m，但最接近 m 的質(zhì)數(shù) p 最為除數(shù)，按照散列函數(shù)：Hash(Key)=key，將關(guān)鍵字轉(zhuǎn)化為哈希地址

平方取中法

假設(shè)關(guān)鍵字為 1230，它的平方是 1512900，取中間的 3 位 129 作為哈希地址；

再比如關(guān)鍵字為 321，它的平方是 103041，取中間的 3 位 304（或 30）作為哈希地址。

哈希沖突

使用散列函數(shù)會帶來一個問題：可能有不同的元素被映射到相同的位置。這無法避免，因為元素個數(shù)大于數(shù)組的容量，這便是「哈希沖突」。解決沖突問題的方法有很有，包括線性探測、二次探測、開散列等。

線性探測

當散列函數(shù)計算出某個元素的插入位置，而該位置上已有其他元素了。最簡單的方法就是向下一一尋找（到達尾端，就從頭開始找），直到找到一個可用位置。

進行元素搜索時同理，如果散列函數(shù)計算出來的位置上的元素值與目標不符，就向下一一尋找，直到找到目標值或遇到空。

至于元素的刪除，必須采用偽刪除，即只標記刪除記號，實際刪除操作在哈希表重新整理時再進行。這是因為哈希表中的每一個元素不僅表示它自己，也影響到其他元素的位置。

從上述插入過程我們可以看出，當哈希表中元素變多時，發(fā)生沖突的概率也變大了。由此，我們引出哈希表一個重要概念：負載因子。

負載因子定義為：Q = 表中元素個數(shù) / 哈希表的長度

負載因子越大，剩余可用空間越少，發(fā)生沖突可能越大
負載因子越小，剩余可用空間越多，發(fā)生沖突可能越小，同時空間浪費更多

因此，控制負載因子是個非常重要的事。對于開放定址法（發(fā)生了沖突，就找下一個可用位置），負載因子應(yīng)控制在 0.7~0.8 以下。超過 0.8，查找時的 CPU 緩存不命中按照指數(shù)曲線上升。

二次探測

線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)會堆在一起，這與其找下一個空位置的方式有關(guān)，它找空位置的方式是挨著往后逐個去找。二次探測主要用來解決數(shù)據(jù)堆積的問題，其命名由來是因為解決碰撞問題的方程式F(i)=i²是個二次方程式。

更具體地說，如果散列函數(shù)計算出新元素的位置為 H，而該位置實際已被使用，那么將嘗試H+1²,H+2²,H+3²,...,H+i²，而不是像線性探測那樣依次嘗試H+1,H+2,H+3,...,H+i。

大量實驗表明：當表格大小為質(zhì)數(shù)，而且保持負載因子在 0.5 以下（超過 0.5 就重新配置），那么就可以確定每插入一個新元素所需要的探測次數(shù)不超過 2。

鏈地址法

這種方法是在每一個表格元素中維護一個鏈表，在呢個鏈表上執(zhí)行元素的插入、查詢、刪除等操作。這時表格內(nèi)的每個單元不再只有一個節(jié)點，而可能有多個節(jié)點。

節(jié)點的定義：

template <class Value>
struct __hashtable_node {
	__hashtable_node* next;
    Value val;
};

哈希表的實現(xiàn)

閉散列

接口總覽

template <class K, class V>
class HashTable {
	struct Elem {
		pair<K, V> _kv;
		State _state = EMPTY;
	};
public:
	Elem* Find(const K& key);
	bool Insert(const pair<K, V>& kv);
	bool Erase(const K& key);
private:
	vector<Elem> _table;
	size_t _n = 0;
};

節(jié)點的結(jié)構(gòu)

因為在閉散列的哈希表中的每一個元素不僅表示它自己，也影響到其他元素的位置。所以要使用偽刪除，我們使用一個變量來表示。

/// @brief 標記每個位置狀態(tài)
enum State {
    EMPTY,    // 空
    EXIST,    // 有數(shù)據(jù)
    DELETE    // 有數(shù)據(jù)，但已被刪除
};

哈希表的節(jié)點結(jié)構(gòu)，不僅存儲數(shù)據(jù)，還存儲狀態(tài)。

/// @brief 哈希表的節(jié)點
struct Elem {
    pair<K, V> _kv;    // 存儲數(shù)據(jù)
    State _state;    // 存儲狀態(tài)    
};

查找

查找的思路比較簡單：

利用散列函數(shù)獲取映射后的索引
遍歷數(shù)組看是否存在，直到遇到空表示查找失敗

/// @brief 查找指定 key
/// @param key 待查找節(jié)點的 key 值
/// @return 找到返回節(jié)點的指針，沒找到返回空指針
Elem* Find(const K& key) {
    if (_table.empty()) {
        return nullptr;
    }

    // 使用除留余數(shù)法的簡化版本，并沒有尋找質(zhì)數(shù)
    // 同時，該版本只能用于正整數(shù)，對于字符串等需使用其他散列函數(shù)
    size_t start = key % _table.size();	
    size_t index = start;
    size_t i = 1;

    // 直到找到空位置停止
    while (_table[index]._state != EMPTY) {
        if (_table[index]._state == EXIST && _table[index]._kv.first == key) {
            return &_table[index];
        }

        index = start + i;
        index %= _table.size();
        ++i;
        // 判斷是否重復(fù)查找
        if (index == start) {
			return nullptr;
        }
    }
    return nullptr;
}

在上面代碼的查找過程中，加了句用于判斷是否重復(fù)查找的代碼。理論上上述代碼不會出現(xiàn)所有的位置都有數(shù)據(jù)，查找不存在的數(shù)據(jù)陷入死循環(huán)的情況，因為哈希表會擴容，閉散列下負載因子不會到 1。

但假如，我們插入了 5 個數(shù)據(jù)，又刪除了它們，之后又插入了 5 個數(shù)據(jù)，將 10 個初始位置都變?yōu)榉?EMPTY。此時我們查找的值不存在的話，是會陷入死循環(huán)的。

插入

插入的過程稍微復(fù)雜一些：

1.首先檢查待插入的 key 值是否存在

2.其次需要檢查是否需要擴容

3.使用線性探測方式將節(jié)點插入

/// @brief 插入節(jié)點
/// @param kv 待插入的節(jié)點
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
    // 檢查是否已經(jīng)存在
    Elem* res = Find(kv.first);
    if (res != nullptr) {
        return false;
    }

    // 看是否需要擴容
    if (_table.empty()) {
        _table.resize(10);
    } else if (_n > 0.7 * _table.size()) {	// 變化一下負載因子計算，可以避免使用除法
        HashTable backUp;
        backUp._table.resize(2 * _table.size());
        for (auto& [k, s] : _table) {
            // C++ 17 的結(jié)構(gòu)化綁定
            // k 綁定 _kv，s 綁定 _state
            if (s == EXIST) {
                backUp.Insert(k);
            }
        }
        // 交換這兩個哈希表，現(xiàn)代寫法
        _table.swap(backUp._table);
    }

    // 將數(shù)據(jù)插入
    size_t start = kv.first % _table.size();
    size_t index = start;
    size_t i = 1;

    // 找一個可以插入的位置
    while (_table[index]._state == EXIST) {
        index = start + i;
        index %= _table.size();
        ++i;
    }
    _table[index]._kv = kv;
    _table[index]._state = EXIST;
    ++_n;
    return true;
}

刪除

刪除的過程非常簡單：

1.查找指定 key

2.找到了就將其狀態(tài)設(shè)為 DELETE，并減少表中元素個數(shù)

/// @brief 刪除指定 key 值
/// @param key 待刪除節(jié)點的 key
/// @return 刪除成功返回 true，失敗返回 false
bool Erase(const K& key) {
    Elem* res = Find(key);
    if (res != nullptr) {
        res->_state = DELETE;
        --_n;
        return true;
    }
    return false;
}

開散列

接口總覽

template <class K, class V>
class HashTable {
	struct Elem {
		Elem(const pair<K, V>& kv) 
			: _kv(kv)
			, _next(nullptr)
		{}

		pair<K, V> _kv;
		Elem* _next;
	};
public:
	Elem* Find(const K& key);
	bool Insert(const pair<K, V>& kv);
	bool Erase(const K& key);
private:
	vector<Elem*> _table;
	size_t _n = 0;
};

節(jié)點的結(jié)構(gòu)

使用鏈地址法解決哈希沖突就不再需要偽刪除了，但需要一個指針，指向相同索引的下一個節(jié)點。

/// @brief 哈希表的節(jié)點
struct Elem {
    Elem(const pair<K, V>& kv) 
        : _kv(kv)
            , _next(nullptr)
        {}

???????    pair<K, V> _kv;    // 存儲數(shù)據(jù)
    Elem* _next;    // 存在下一節(jié)點地址
};

查找

查找的實現(xiàn)比較簡單：

1.利用散列函數(shù)獲取映射后的索引

2.遍歷該索引位置的鏈表

/// @brief 查找指定 key
/// @param key 待查找節(jié)點的 key 值
/// @return 找到返回節(jié)點的指針，沒找到返回空指針
Elem* Find(const K& key) {
    if (_table.empty()) {
        return nullptr;
    }

    size_t index = key % _table.size();
    Elem* cur = _table[index];
    // 遍歷該位置鏈表
    while (cur != nullptr) {
        if (cur->_kv.first == key) {
            return cur;
        }
        cur = cur->_next;
    }
    return nullptr;
}

插入

開散列下的插入比閉散列簡單：

1.首先檢查待插入的 key 值是否存在

2.其次需要檢查是否需要擴容

3.將新節(jié)點以頭插方式插入

/// @brief 插入節(jié)點
/// @param kv 待插入的節(jié)點
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
    // 檢查是否已經(jīng)存在
    Elem* res = Find(kv.first);
    if (res != nullptr) {
        return false;
    }

    // 檢查是否需要擴容
    if (_table.size() == _n) {
        vector<Elem*> backUp;
        size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
        backUp.resize(newSize);

        // 遍歷原哈希表，將所有節(jié)點插入新表
        for (int i = 0; i < _table.size(); ++i) {
            Elem* cur = _table[i];
            while (cur != nullptr) {
                // 取原哈希表的節(jié)點放在新表上，不用重新申請節(jié)點
                Elem* tmp = cur->_next;
                size_t index = cur->_kv.first % backUp.size();
                cur->_next = backUp[index];
                backUp[index] = cur;
                cur = tmp;
            }
            _table[i] = nullptr;
        }
        _table.swap(backUp);
    }

    // 將新節(jié)點以頭插的方式插入
    size_t index = kv.first % _table.size();
    Elem* newElem = new Elem(kv);
    newElem->_next = _table[index];
    _table[index] = newElem;
    ++_n;
    return true;
}

刪除

開散列的刪除與閉散列有些許不同：

1.獲取 key 對應(yīng)的索引

2.遍歷該位置鏈表，找到就刪除

/// @brief 刪除指定 key 值
/// @param key 待刪除節(jié)點的 key
/// @return 刪除成功返回 true，失敗返回 false
bool Erase(const K& key) {
    size_t index = key % _table.size();
    Elem* prev = nullptr;
    Elem* cur = _table[index];
    while (cur != nullptr) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                // 是該位置第一個節(jié)點
                _table[index] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;	// 釋放該節(jié)點
            --_n;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之哈希表的實現(xiàn)的文章就介紹到這了,更多相關(guān)C++哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: