自定義C++ Hash表設計思路

設計一個自定義的C++哈希表需要考慮以下幾個關鍵點：

1. 哈希函數：一個好的哈希函數應該能夠將輸入的鍵均勻地分布在整個哈希表中，以減少沖突的概率。
2. 沖突解決策略：當兩個不同的鍵映射到同一個哈希桶時，需要有一種策略來解決沖突。常見的沖突解決策略有開放尋址法（線性探測、二次探測、雙散列）和鏈地址法。
3. 動態擴容：為了保持哈希表的性能，當其負載因子超過一定閾值時，應該進行動態擴容。
4. 內存管理：需要考慮如何高效地分配和釋放內存，避免內存泄漏。
5. 線程安全：如果需要在多線程環境中使用哈希表，還需要考慮線程安全問題。

下面是一個簡單的自定義C++哈希表設計示例，使用了鏈地址法來解決沖突，并且支持動態擴容：

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

template <typename Key, typename Value>
class HashTable {
private:
    struct Entry {
        Key key;
        Value value;
        bool occupied;
        Entry() : occupied(false) {}
    };

    std::vector<std::list<Entry>> table;
    size_t size;
    size_t capacity;
    float loadFactorThreshold;

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

    void rehash(size_t newCapacity) {
        std::vector<std::list<Entry>> newTable(newCapacity);
        for (const auto& bucket : table) {
            for (const auto& entry : bucket) {
                if (entry.occupied) {
                    size_t newIndex = std::hash<Key>{}(entry.key) % newCapacity;
                    newTable[newIndex].push_back(entry);
                }
            }
        }
        table = std::move(newTable);
        capacity = newCapacity;
    }

public:
    HashTable(size_t initialCapacity = 10, float loadFactorThreshold = 0.75)
        : size(0), capacity(initialCapacity), loadFactorThreshold(loadFactorThreshold) {
        table.resize(capacity);
    }

    void insert(const Key& key, const Value& value) {
        if (static_cast<float>(size) / capacity >= loadFactorThreshold) {
            rehash(capacity * 2);
        }

        size_t index = hash(key);
        for (auto& entry : table[index]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }

        table[index].push_back({key, value, true});
        ++size;
    }

    bool remove(const Key& key) {
        size_t index = hash(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->key == key) {
                table[index].erase(it);
                --size;
                return true;
            }
        }
        return false;
    }

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

    size_t getSize() const {
        return size;
    }

    size_t getCapacity() const {
        return capacity;
    }
};

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

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

    ht.remove(11);

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

    return 0;
}

關鍵點解釋：

1. 哈希函數：使用std::hash<Key>來生成鍵的哈希值。
2. 沖突解決策略：使用鏈地址法，每個桶是一個std::list<Entry>。
3. 動態擴容：當負載因子超過loadFactorThreshold時，將容量加倍。
4. 內存管理：使用std::vector來管理桶，自動處理內存分配和釋放。
5. 線程安全：這個示例沒有考慮線程安全，如果需要在多線程環境中使用，可以考慮使用互斥鎖或其他同步機制。

這個示例是一個基礎的哈希表實現，可以根據具體需求進行擴展和優化。