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来确保在多线程环境下的线程安全。

这个简单的实现可以根据需要进行扩展和优化，例如使用开放寻址法解决哈希冲突，或者使用更高效的哈希函数。