用C++實現高效的哈希表

一、哈希表的介紹

哈希表是一種數據結構，通過將關鍵字映射到哈希表中的位置來實現快速查找和插入。哈希表通常具有常數時間複雜度，在實際應用中經常用於快速存儲和查找數據。

二、哈希函數的設計

哈希函數的設計是哈希表實現中非常關鍵的一步。一個好的哈希函數能使關鍵字儘可能地平均地分散在哈希表中，從而降低哈希碰撞的概率。

哈希函數的設計需要滿足以下幾點要求：

1. 哈希函數應該能夠將任意長度的輸入映射到固定大小的輸出。

2. 哈希函數應該儘可能地簡單，以提升哈希運算的速度。

3. 哈希函數應該能夠將關鍵字均勻地映射到哈希表的各個位置。

unsigned int hashFunction(const std::string& str)
{
    unsigned int hash = 5381;
    for (char c : str)
    {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

三、哈希衝突的解決

哈希衝突指的是兩個不同的關鍵字被哈希函數映射到同一位置的情況。解決哈希衝突的方法通常有開放定址法和鏈表法兩種。

開放定址法是指當發生哈希衝突時，從衝突的位置開始依次往下查找空閑的位置，並將元素插入到第一個空閑的位置中。

void insert(const std::string& key, const T& value)
{
    const unsigned int hash = hashFunction(key);
    unsigned int index = hash % m_tableSize;

    while (m_elements[index].first != "")
    {
        if (m_elements[index].first == key)
        {
            m_elements[index].second = value;
            return;
        }
        index = (index + 1) % m_tableSize;
    }

    m_elements[index] = std::make_pair(key, value);
    ++m_size;
}

鏈表法是指將哈希衝突的元素插入到同一個位置上的一個鏈表中。當查找哈希表中的元素時，需要依次遍歷鏈表上的每個元素。

void insert(const std::string& key, const T& value)
{
    const unsigned int hash = hashFunction(key);
    unsigned int index = hash % m_tableSize;
    for (auto& element : m_elements[index])
    {
        if (element.first == key)
        {
            element.second = value;
            return;
        }
    }
    m_elements[index].emplace_back(key, value);
    ++m_size;
}

四、哈希表的性能優化

哈希表的性能優化包括哈希函數的優化、哈希表的容量、哈希衝突的解決等。

1. 哈希函數的優化可以通過合理的設計哈希函數和鏡像哈希等技術來提高哈希表的查找效率。

2. 哈希表的容量需要合理設置，通常設置為質數能夠提高哈希表的性能。

3. 哈希衝突的解決需要選擇合適的方法來解決，不同的解決方案適用於不同的場景。

五、完整代碼示例

#include 
#include 
#include 

template 
class HashTable
{
public:
    HashTable(unsigned int tableSize)
        : m_tableSize(tableSize)
        , m_size(0)
        , m_elements(tableSize)
    {}

    void insert(const std::string& key, const T& value)
    {
        const unsigned int hash = hashFunction(key);
        unsigned int index = hash % m_tableSize;
        for (auto& element : m_elements[index])
        {
            if (element.first == key)
            {
                element.second = value;
                return;
            }
        }
        m_elements[index].emplace_back(key, value);
        ++m_size;
    }

    bool get(const std::string& key, T& value) const
    {
        const unsigned int hash = hashFunction(key);
        const unsigned int index = hash % m_tableSize;
        for (const auto& element : m_elements[index])
        {
            if (element.first == key)
            {
                value = element.second;
                return true;
            }
        }
        return false;
    }

    bool remove(const std::string& key)
    {
        const unsigned int hash = hashFunction(key);
        const unsigned int index = hash % m_tableSize;
        auto& chain = m_elements[index];
        for (auto it = chain.begin(); it != chain.end(); ++it)
        {
            if (it->first == key)
            {
                chain.erase(it);
                --m_size;
                return true;
            }
        }
        return false;
    }

    unsigned int size() const
    {
        return m_size;
    }

private:
    std::vector<std::vector<std::pair>> m_elements;
    const unsigned int m_tableSize;
    unsigned int m_size;

    unsigned int hashFunction(const std::string& str) const
    {
        unsigned int hash = 5381;
        for (char c : str)
        {
            hash = ((hash << 5) + hash) + c;
        }
        return hash;
    }
};