C++并发编程之无锁哈希表的设计与实现

捕鲸叉

567人浏览 · 2025-01-14 20:48:24

捕鲸叉 · 2025-01-14 20:48:24 发布

在C++中实现一个多线程环境下的无锁哈希表同样是一个复杂且具有挑战性的任务，因为需要确保在多线程并发访问时的数据一致性和线程安全性。无锁哈希表通过使用原子操作来避免传统锁机制带来的性能瓶颈。这种数据结构在高并发场景下具有广泛的应用，如高性能服务器、缓存系统、实时数据处理等。

下面将介绍一个简单的无锁哈希表的设计思路和C++实现，同时指出其可能的应用场景。

设计思路

哈希桶：每个哈希桶是一个无锁链表，链表中的每个节点包含键值对。
原子操作：使用 std::atomic 提供的原子操作来读取、修改哈希表的指针。
插入操作：通过原子操作将新节点插入到正确的哈希桶中。
删除操作：通过原子操作标记节点为已删除状态。
查找操作：通过原子操作遍历哈希桶中的节点，查找目标键值对。

C++实现

#include <iostream>
#include <vector>
#include <atomic>
#include <memory>
#include <functional>  // std::hash

// 节点结构
template<typename Key, typename Value>
struct Node {
    Key key;
    Value value;
    std::atomic<Node*> next;

    Node(const Key& k, const Value& v) : key(k), value(v), next(nullptr) {}
};

// 无锁链表
template<typename Key, typename Value>
class LockFreeList {
private:
    std::atomic<Node<Key, Value>*> head;

public:
    LockFreeList() : head(nullptr) {}

    // 插入操作
    bool insert(const Key& key, const Value& value) {
        Node<Key, Value>* new_node = new Node<Key, Value>(key, value);
        while (true) {
            Node<Key, Value>* current = head.load();
            if (current == nullptr) {
                // 如果链表为空，尝试插入到头部
                if (head.compare_exchange_weak(current, new_node)) {
                    return true;
                }
            } else {
                // 检查是否存在相同的键
                Node<Key, Value>* prev = nullptr;
                while (current != nullptr && current->key != key) {
                    prev = current;
                    current = current->next.load();
                }
                if (current != nullptr) {
                    // 键已存在，更新值
                    current->value = value;
                    delete new_node;
                    return false;
                }
                // 插入到链表尾部
                if (prev->next.compare_exchange_weak(current, new_node)) {
                    new_node->next.store(current);
                    return true;
                }
            }
        }
    }

    // 查找操作
    bool find(const Key& key, Value& value) const {
        Node<Key, Value>* current = head.load();
        while (current != nullptr) {
            if (current->key == key) {
                value = current->value;
                return true;
            }
            current = current->next.load();
        }
        return false;
    }

    // 删除操作
    bool remove(const Key& key) {
        while (true) {
            Node<Key, Value>* current = head.load();
            Node<Key, Value>* prev = nullptr;
            while (current != nullptr && current->key != key) {
                prev = current;
                current = current->next.load();
            }
            if (current == nullptr) {
                return false;  // 未找到
            }
            // 找到目标节点，尝试删除
            Node<Key, Value>* next_node = current->next.load();
            if (prev != nullptr) {
                if (prev->next.compare_exchange_weak(current, next_node)) {
                    delete current;
                    return true;
                }
            } else {
                if (head.compare_exchange_weak(current, next_node)) {
                    delete current;
                    return true;
                }
            }
        }
    }
};

// 无锁哈希表
template<typename Key, typename Value>
class LockFreeHashTable {
private:
    std::vector<LockFreeList<Key, Value>> buckets;
    std::hash<Key> hash_fn;

public:
    LockFreeHashTable(size_t bucket_count) : buckets(bucket_count) {}

    // 插入操作
    void insert(const Key& key, const Value& value) {
        size_t bucket_index = hash_fn(key) % buckets.size();
        buckets[bucket_index].insert(key, value);
    }

    // 查找操作
    bool find(const Key& key, Value& value) const {
        size_t bucket_index = hash_fn(key) % buckets.size();
        return buckets[bucket_index].find(key, value);
    }

    // 删除操作
    bool remove(const Key& key) {
        size_t bucket_index = hash_fn(key) % buckets.size();
        return buckets[bucket_index].remove(key);
    }
};

// 测试代码
int main() {
    LockFreeHashTable<int, std::string> hash_table(10);
    hash_table.insert(1, "one");
    hash_table.insert(2, "two");

    std::string value;
    if (hash_table.find(1, value)) {
        std::cout << "Found: " << value << std::endl;  // 输出: one
    }

    hash_table.remove(1);
    if (!hash_table.find(1, value)) {
        std::cout << "Key 1 not found" << std::endl;  // 输出: Key 1 not found
    }

    return 0;
}