当前位置：首页 > article >正文

算法学习第十七天：LRU缓存与布隆过滤器

article 2025/3/31 14:33:36

LRU缓存与布隆过滤器

LRU缓存

基本概念

LRU（Least Recently Used）：最近最少使用策略，当缓存空间不足时，淘汰最久未被访问的数据。
缓存特点：快速访问、容量有限、易失性。
应用场景：CPU缓存、数据库查询缓存、内存管理。

实现原理

双向链表：维护数据的访问顺序，最近访问的节点靠近头部，最久未访问的靠近尾部。
哈希表：存储键到链表节点的映射，实现O(1)时间复杂度的查找。
操作逻辑：
- Get：若键存在，将对应节点移到链表头部并返回值。
- Put：若键存在，更新值并移到头部；若不存在，插入新节点。若缓存满，删除尾部节点。

C++代码实现

#include <unordered_map>
#include <list>

class LRUCache {
private:
    int capacity;
    std::list<std::pair<int, int>> cacheList;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = cacheMap.find(key);
        if (it == cacheMap.end()) return -1;
        // 将节点移到链表头部
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = cacheMap.find(key);
        if (it != cacheMap.end()) {
            // 更新值并移到头部
            it->second->second = value;
            cacheList.splice(cacheList.begin(), cacheList, it->second);
            return;
        }
        // 插入新节点，若满则删除尾部
        if (cacheMap.size() == capacity) {
            int lastKey = cacheList.back().first;
            cacheMap.erase(lastKey);
            cacheList.pop_back();
        }
        cacheList.emplace_front(key, value);
        cacheMap[key] = cacheList.begin();
    }
};

布隆过滤器

基本概念

作用：高效判断元素是否存在于集合中，适用于允许误判的场景。
特点：
- 空间效率高：使用位数组存储。
- 查询快：O(k)时间复杂度（k为哈希函数数量）。
- 误判率：可能存在假阳性（判断存在但实际不存在），但无假阴性。

实现原理

位数组：初始化为全0，插入元素时通过多个哈希函数映射到多个位置并置1。
哈希函数：选择k个独立哈希函数，减少冲突概率。
查询流程：计算元素对应的k个位，若所有位均为1则判定存在，否则不存在。

C++代码实现

#include <bitset>
#include <functional>
#include <vector>

class BloomFilter {
private:
    std::bitset<1000> bits; // 位数组大小可根据需求调整
    std::vector<std::function<size_t(const std::string&)>> hashFunctions;

public:
    BloomFilter() {
        // 添加3个哈希函数示例
        hashFunctions.push_back(std::hash<std::string>());
        hashFunctions.push_back([](const std::string& s) {
            size_t hash = 0;
            for (char c : s) hash = (hash * 131) + c;
            return hash;
        });
        hashFunctions.push_back([](const std::string& s) {
            size_t hash = 0;
            for (char c : s) hash = (hash * 31) + c;
            return hash;
        });
    }

    void add(const std::string& element) {
        for (auto& hashFunc : hashFunctions) {
            size_t pos = hashFunc(element) % bits.size();
            bits.set(pos, true);
        }
    }

    bool contains(const std::string& element) {
        for (auto& hashFunc : hashFunctions) {
            size_t pos = hashFunc(element) % bits.size();
            if (!bits.test(pos)) return false;
        }
        return true;
    }
};