C++ Hash表與哈希桶設計

在C++中，哈希表（HashTable）和哈希桶（Hash Bucket）是兩種常見的數據結構，用于實現高效的數據存儲和查找

1. 哈希表（HashTable）： 哈希表是一種使用哈希函數將鍵（Key）映射到值（Value）的數據結構。它支持快速插入、刪除和查找操作。哈希表的主要優點是在大多數情況下，這些操作的時間復雜度接近O(1)。然而，在最壞的情況下，例如當所有鍵都發生沖突時，這些操作的時間復雜度可能會退化為O(n)。

2. 哈希桶（Hash Bucket）： 哈希桶是哈希表中存儲數據的基本單元。它是一個數組，用于存儲具有相同哈希值的鍵值對。哈希桶的數量決定了哈希表的大小。當插入一個新的鍵值對時，首先計算其哈希值，然后根據該哈希值將鍵值對存儲到相應的哈希桶中。

哈希桶的設計要點：

• 桶的數量：選擇一個合適的桶數量可以降低沖突的概率，從而提高查詢效率。通常，可以根據預期的數據量和可接受的負載因子（Load Factor）來確定桶的數量。負載因子是哈希表中已存儲元素數量與桶數量的比值。當負載因子過大時，可能需要增加桶的數量以降低沖突概率。

• 動態調整：當哈希表的負載因子超過某個閾值時，可以通過重新哈希（Rehashing）操作來調整哈希表的大小和桶的數量。這樣可以降低沖突概率，提高查詢效率。重新哈希操作通常涉及創建一個新的哈希表，將原哈希表中的鍵值對重新計算哈希值并存儲到新的哈希桶中。

• 沖突解決策略：當兩個或多個鍵具有相同的哈希值時，會發生沖突。常見的沖突解決策略有開放尋址法（Open Addressing）和鏈地址法（Separate Chaining）。開放尋址法通過線性探測、二次探測或雙散列等方法在哈希表中尋找空閑的桶來存儲沖突的鍵值對。鏈地址法則是將具有相同哈希值的鍵值對存儲在一個鏈表中，每個桶對應一個鏈表。

下面是一個簡單的C++哈希表實現示例，使用鏈地址法解決沖突：

#include <iostream>
#include <list>
#include <vector>
#include <functional>

template<typename Key, typename Value>
class HashTable {
public:
    HashTable(size_t bucket_count) : buckets(bucket_count), load_factor(0.75) {}

    void insert(const Key& key, const Value& value) {
        if (load_factor * buckets.size() < buckets.size()) {
            rehash();
        }

        size_t index = hash(key) % buckets.size();
        auto& bucket = buckets[index];
        for (auto& entry : bucket) {
            if (entry.first == key) {
                entry.second = value;
                return;
            }
        }
        bucket.emplace_back(key, value);
    }

    bool find(const Key& key, Value& value) const {
        size_t index = hash(key) % buckets.size();
        const auto& bucket = buckets[index];
        for (const auto& entry : bucket) {
            if (entry.first == key) {
                value = entry.second;
                return true;
            }
        }
        return false;
    }

    void remove(const Key& key) {
        size_t index = hash(key) % buckets.size();
        auto& bucket = buckets[index];
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->first == key) {
                bucket.erase(it);
                return;
            }
        }
    }

private:
    size_t hash(const Key& key) const {
        return std::hash<Key>{}(key);
    }

    void rehash() {
        size_t new_bucket_count = buckets.size() * 2;
        std::vector<std::list<std::pair<Key, Value>>> new_buckets(new_bucket_count);

        for (const auto& bucket : buckets) {
            for (const auto& entry : bucket) {
                size_t new_index = hash(entry.first) % new_bucket_count;
                new_buckets[new_index].push_back(entry);
            }
        }

        buckets = std::move(new_buckets);
    }

    std::vector<std::list<std::pair<Key, Value>>> buckets;
    double load_factor;
};

int main() {
    HashTable<int, std::string> table(10);
    table.insert(1, "one");
    table.insert(11, "eleven");
    table.insert(21, "twenty-one");

    std::string value;
    if (table.find(1, value)) {
        std::cout << "Found: " << value << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    table.remove(1);

    if (table.find(1, value)) {
        std::cout << "Found: " << value << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}

這個示例中，我們使用std::list作為哈希桶的數據結構，存儲具有相同哈希值的鍵值對。當需要調整哈希表的大小時，我們創建一個新的哈希表，并將原哈希表中的鍵值對重新計算哈希值并存儲到新的哈希桶中。