C++哈希表使用詳解

一、哈希表基礎

哈希表是一種不同於常規數組或鏈表的數據結構，通過哈希函數將數據映射到不同的槽位上，使得數據的查找、插入和刪除操作時間複雜度為O(1)。C++ STL中提供了unordered_map和unordered_set兩個哈希表的實現，它們的底層實現都是使用哈希表。

使用哈希表時，我們通常需要關注哈希函數的設計和衝突解決方法。哈希函數應當將數據均勻地分散在不同的槽位上，並且能夠處理不同類型的數據；而衝突解決方法則需要保證數據不會重複，並且插入、刪除時不會影響其他數據。

二、unordered_map用法

unordered_map是C++ STL中實現的哈希表，其使用方法與map基本相同，但相比於map，其查找、插入、刪除的時間複雜度更低且不需要數據排序。以下是unordered_map的簡單示例：

#include 
#include 
#include 

using namespace std;

int main() {
    unordered_map m;
    m[1] = "hello";
    m[2] = "world";
    m[3] = "!";
    cout << m[2] << endl; // 輸出 world
    return 0;
}

在上述代碼中，我們使用了unordered_map來存儲int和string類型的鍵值對，通過下標訪問map中的元素，並輸出了鍵為2的元素的值。

三、哈希函數設計

哈希函數是哈希表的核心，一個好的哈希函數能夠有效地減少數據衝突。以下是一個簡單的哈希函數設計：

size_t hash_func(const string& str) {
    size_t hash_value = 0;
    for (const auto& c : str) {
        hash_value = 31 * hash_value + c;
    }
    return hash_value;
}

在上述代碼中，我們採用了djb2哈希演算法，將每個字元的ASCII碼乘以一個質數31，並加上前面字元的哈希值，最終得到一個哈希值。

四、哈希衝突解決

當兩個不同的數據被哈希函數映射到同一個槽位時，就會發生哈希衝突。為了解決哈希衝突，我們通常需要使用鏈表、開放定址等技術。以下是開放定址法的示例代碼：

template 
class OpenAddrHashTable {
public:
    explicit OpenAddrHashTable(size_t size = 1000) : size_(size) {
        table_ = new std::pair[size];
        ++size_;
    }

    ~OpenAddrHashTable() {
        delete[] table_;
    }

    OpenAddrHashTable(const OpenAddrHashTable&) = delete;

    OpenAddrHashTable& operator=(const OpenAddrHashTable&) = delete;

    void insert(const Key& key, const Value& value) {
        size_t hash_value = hash_func(key);
        size_t i = hash_value % size_;
        size_t j = i;
        while (table_[j].first != key && table_[j].first != Key()) {
            ++j;
            if (j == size_)
                j = 0;
            if (j == i)
                throw std::runtime_error("hash table full");
        }
        table_[j] = std::make_pair(key, value);
    }

    Value& search(const Key& key) const {
        size_t i = hash_func(key) % size_;
        size_t j = i;
        while (table_[j].first != key && table_[j].first != Key()) {
            ++j;
            if (j == size_)
                j = 0;
            if (j == i)
                throw std::runtime_error("key not found");
        }
        return table_[j].second;
    }

private:
    size_t size_;
    std::pair* table_;

    size_t hash_func(const Key& key) const {
        // 哈希函數的實現
    }
};

在OpenAddrHashTable中，我們使用了開放定址法來解決哈希衝突。當數據插入時，如果對應的槽位已經被佔用，就從下一個槽位開始往後查找，直到找到空槽位為止；當數據查找時，如果對應的槽位不是要查找的數據，就繼續從下一個槽位開始往後查找，直到找到要查找的數據或者槽位為空為止。

五、總結

哈希表是一種高效的數據結構，適用於需要快速查找、插入和刪除的場景。C++ STL中通過unordered_map和unordered_set提供了哈希表的實現，我們可以根據業務需求選擇不同的實現方式。同時，針對特定的問題場景，我們也可以自己實現哈希表來達到更好的效果。