Hash算法在C++中實現高性能數據結構

在C++中實現高性能數據結構時，哈希表（Hash Table）是一種非常實用的數據結構

#include <iostream>
#include <vector>
#include <list>
#include <mutex>

class HashTable {
public:
    HashTable(size_t size) : table(size), mutexes(size) {}

    template <typename Key, typename Value>
    bool insert(const Key& key, const Value& value) {
        size_t index = hash(key) % table.size();
        std::lock_guard<std::mutex> lock(mutexes[index]);
        auto& bucket = table[index];
        for (auto& entry : bucket) {
            if (entry.first == key) {
                entry.second = value;
                return true;
            }
        }
        bucket.emplace_back(key, value);
        return true;
    }

    template <typename Key, typename Value>
    bool find(const Key& key, Value& value) const {
        size_t index = hash(key) % table.size();
        std::lock_guard<std::mutex> lock(mutexes[index]);
        const auto& bucket = table[index];
        for (const auto& entry : bucket) {
            if (entry.first == key) {
                value = entry.second;
                return true;
            }
        }
        return false;
    }

    template <typename Key>
    bool remove(const Key& key) {
        size_t index = hash(key) % table.size();
        std::lock_guard<std::mutex> lock(mutexes[index]);
        auto& bucket = table[index];
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->first == key) {
                bucket.erase(it);
                return true;
            }
        }
        return false;
    }

private:
    std::vector<std::list<std::pair<Key, Value>>> table;
    std::vector<std::mutex> mutexes;

    template <typename T>
    size_t hash(const T& value) const {
        std::hash<T> hasher;
        return hasher(value);
    }
};

int main() {
    HashTable ht(10);
    ht.insert("one", 1);
    ht.insert("two", 2);
    ht.insert("three", 3);

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

    if (ht.remove("two")) {
        std::cout << "Removed 'two'" << std::endl;
    } else {
        std::cout << "'two' not found" << std::endl;
    }

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

    return 0;
}

這個實現使用了std::vector來存儲桶（bucket），每個桶是一個std::list，用于存儲具有相同哈希值的鍵值對。我們還使用了std::mutex來確保在多線程環境下的線程安全。

這個簡單的實現可以根據需要進行擴展和優化，例如使用開放尋址法解決哈希沖突，或者使用更高效的哈希函數。