C++資料結構之雜湊表的實現

2023-03-13 06:00:38

雜湊表概念

二元搜尋樹具有對數時間的表現，但這樣的表現建立在一個假設上：輸入的資料有足夠的隨機性。雜湊表又名雜湊表，在插入、刪除、搜尋等操作上具有「常數平均時間」的表現，而且這種表現是以統計為基礎，不需依賴輸入元素的隨機性。

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

假設所有元素都是 8-bits 的正整數，範圍 0~255，那麼簡單得使用一個陣列就可以滿足上述要求。首先設定一個陣列 Q，擁有 256 個元素，索引號碼 0~255，初始值全部為 0。每一個元素值代表相應的元素的出現次數。如果插入元素 i，就執行 Q[i]++，如果刪除元素 i，就執行 Q[i]--，如果查詢元素 i，就看 Q[i] 是否為 0。

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

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

雜湊函數

如何避免使用一個太大的陣列，以及如何將字串轉化為陣列的索引呢？一種常見的方法就是使用某種對映函數，將某一元素對映為一個「大小可接受的索引」，這樣的函數稱為雜湊函數。

雜湊函數應有以下特性：

函數的定義域必須包含需要儲存的全部關鍵字，當雜湊表有 m 個地址時，其值域在 0 到 m - 1 之間
函數計算出來的地址能均勻分佈在整個空間

直接定址法

取關鍵字的某個線性函數為雜湊地址：Hash(Key)=A∗Key+B

優點：簡單、均勻

缺點：需要事先知道關鍵字的分佈情況

使用場景：資料範圍比較集中的情況

除留餘數法

設雜湊表的索引個數為 m，取一個不大於 m，但最接近 m 的質數 p 最為除數，按照雜湊函數：Hash(Key)=key，將關鍵字轉化為雜湊地址

平方取中法

假設關鍵字為 1230，它的平方是 1512900，取中間的 3 位 129 作為雜湊地址；

再比如關鍵字為 321，它的平方是 103041，取中間的 3 位 304（或 30）作為雜湊地址。

雜湊衝突

使用雜湊函數會帶來一個問題：可能有不同的元素被對映到相同的位置。這無法避免，因為元素個數大於陣列的容量，這便是「雜湊衝突」。解決衝突問題的方法有很有，包括線性探測、二次探測、開雜湊等。

線性探測

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

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

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

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

負載因子定義為：Q = 表中元素個數 / 雜湊表的長度

負載因子越大，剩餘可用空間越少，發生衝突可能越大
負載因子越小，剩餘可用空間越多，發生衝突可能越小，同時空間浪費更多

因此，控制負載因子是個非常重要的事。對於開放定址法（發生了衝突，就找下一個可用位置），負載因子應控制在 0.7~0.8 以下。超過 0.8，查詢時的 CPU 快取不命中按照指數曲線上升。

二次探測

線性探測的缺陷是產生衝突的資料會堆在一起，這與其找下一個空位置的方式有關，它找空位置的方式是挨著往後逐個去找。二次探測主要用來解決資料堆積的問題，其命名由來是因為解決碰撞問題的方程式F(i)=i²是個二次方程式。

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

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

鏈地址法

這種方法是在每一個表格元素中維護一個連結串列，在呢個連結串列上執行元素的插入、查詢、刪除等操作。這時表格內的每個單元不再只有一個節點，而可能有多個節點。

節點的定義：

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

雜湊表的實現

閉雜湊

介面總覽

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;
};

節點的結構

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

/// @brief 標記每個位置狀態
enum State {
    EMPTY,    // 空
    EXIST,    // 有資料
    DELETE    // 有資料，但已被刪除
};

雜湊表的節點結構，不僅儲存資料，還儲存狀態。

/// @brief 雜湊表的節點
struct Elem {
    pair<K, V> _kv;    // 儲存資料
    State _state;    // 儲存狀態    
};

查詢

查詢的思路比較簡單：

利用雜湊函數獲取對映後的索引
遍歷陣列看是否存在，直到遇到空表示查詢失敗

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

    // 使用除留餘數法的簡化版本，並沒有尋找質數
    // 同時，該版本只能用於正整數，對於字串等需使用其他雜湊函數
    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;
        // 判斷是否重複查詢
        if (index == start) {
			return nullptr;
        }
    }
    return nullptr;
}

在上面程式碼的查詢過程中，加了句用於判斷是否重複查詢的程式碼。理論上上述程式碼不會出現所有的位置都有資料，查詢不存在的資料陷入死迴圈的情況，因為雜湊表會擴容，閉雜湊下負載因子不會到 1。

但假如，我們插入了 5 個資料，又刪除了它們，之後又插入了 5 個資料，將 10 個初始位置都變為非 EMPTY。此時我們查詢的值不存在的話，是會陷入死迴圈的。

插入

插入的過程稍微複雜一些：

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

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

3.使用線性探測方式將節點插入

/// @brief 插入節點
/// @param kv 待插入的節點
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
    // 檢查是否已經存在
    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 的結構化繫結
            // k 繫結 _kv，s 繫結 _state
            if (s == EXIST) {
                backUp.Insert(k);
            }
        }
        // 交換這兩個雜湊表，現代寫法
        _table.swap(backUp._table);
    }

    // 將資料插入
    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.找到了就將其狀態設為 DELETE，並減少表中元素個數

/// @brief 刪除指定 key 值
/// @param key 待刪除節點的 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;
};

節點的結構

使用鏈地址法解決雜湊衝突就不再需要偽刪除了，但需要一個指標，指向相同索引的下一個節點。

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

    pair<K, V> _kv;    // 儲存資料
    Elem* _next;    // 存在下一節點地址
};

查詢

查詢的實現比較簡單：

1.利用雜湊函數獲取對映後的索引

2.遍歷該索引位置的連結串列

/// @brief 查詢指定 key
/// @param key 待查詢節點的 key 值
/// @return 找到返回節點的指標，沒找到返回空指標
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.將新節點以頭插方式插入

/// @brief 插入節點
/// @param kv 待插入的節點
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
    // 檢查是否已經存在
    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);

        // 遍歷原雜湊表，將所有節點插入新表
        for (int i = 0; i < _table.size(); ++i) {
            Elem* cur = _table[i];
            while (cur != nullptr) {
                // 取原雜湊表的節點放在新表上，不用重新申請節點
                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);
    }

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

刪除

開雜湊的刪除與閉雜湊有些許不同：

1.獲取 key 對應的索引

2.遍歷該位置連結串列，找到就刪除

/// @brief 刪除指定 key 值
/// @param key 待刪除節點的 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) {
                // 是該位置第一個節點
                _table[index] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;	// 釋放該節點
            --_n;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

到此這篇關於C++資料結構之雜湊表的實現的文章就介紹到這了,更多相關C++雜湊表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！